Bandwidth constraints on problems complete for polynomial time

AbstractA graph G=(V, E) has bandwidth k under a layout L:V →1 1{1,…,¦V¦} if, for all {x, y}∈E, ¦L(x,−L(y)¦⩽k. Bandwidth constraints on several problems that are complete for P (under long space reductions) are considered. In particular, the solvable path system problem and the and⧹or graph accessibility problem under various bandwidth constraints are used to prove results about subclasses of P. In general, restricting the bandwidth of problems complete for P results in complete problems for subclasses of P defined by simultaneous time-space bounds or defined by space bounds on alternating Turing machines. For instance, these results are used to show that the class SC, of sets accepted in polynomial time and simultaneous polylog space, can be characterized as the class reducible by log space transformations to sets accepted by one-way log log n space bounded alternating Turing machines. An upper bound on the space requirements for the solvable path system problem under various bandwidth constraints is given by SPS(t(n))∈DSPACE(f(n)log n). This yields, as a corollary, the result ASPACE(f(n)) (- ∪k→lcub0rcub) DSPACE(2kf(n)) for functions f that are suitably constructible and do not grow more rapidly than some logarithm function. This extends the known result: ASPACE(f(n)) = ∪k→lcub0rcub) DTIME(2kf(n)), which only applies to functions that grow at least as rapidly as a logarithm function