Bandwidth contrained NP-complete problems (Q1822500)

Bandwidth restrictions are considered on several NP-complete problems, including the following: 3SATISFIABILITY, INDEPENDENT SET, VERTEX COVER, HITTING SET, SIMPLE MAX CUT, 3-DIMENSIONAL MATCHING, EXACT COVER by 3 SETS, PARTITION INTO TRIANGLES, 3-COLORABILITY (even for planar graphs with maximum vertex degree four), DIRECTED AND UNDIRECTED HAMILTONIAN CIRCUIT and BANDWIDTH MINIMIZATION. It is shown that these problems when restricted to graphs, formulae, sets of triples, etc., of bandwidth f(n) are log space hard for the class of problems solvable by polynomial time nondeterministic algorithms that use simultaneously at most f(n) space. This class is denoted by NTISP(poly,f(n)). In fact, all of these problems restricted to bandwidth f(n), except for HAMILTONIAN CIRCUIT and BANDWIDTH MINIMIZATION, are shown to be log space complete for NTISP(poly,f(n)). Since NTISP(poly,log n)\(=NSPACE(\log n)\), this means we give several new additional examples of NSPACE(log n) complete problems. It also means that \(NP=NSPACE(\log n)\) if and only if \(3SAT\leq_{\log}3SAT\) restricted to well-formed formulae with bandwidth log n.