Complete problems for space bounded subclasses of NP (Q1064779)

Some problems are proved to be complete for the classes NTISP(poly,f(n)), for a function log \(n\leq f(n)\leq n\). For this purpose the notion of bandwidth of a combinatorial problem, introduced by Monien and Sudborough, is involved. For example, in case of the problem 3SAT of satisfiability of 3-CNF, denote by 3SAT(f) this problem restricted to 3- CNF, \(w=\&_{1\leq i\leq n}(y_{i,1}\vee y_{i,2}\vee y_{i,3})\) such that for any variable x occurring in i-th and j-th clauses (positively or negatively), the inequality \(| i-j| \leq f(n)\) is fulfilled. The following problems are log-space complete for NTISP(poly,f): NOT-ALL- EQUAL 3-SAT(f), DOMATIC \(NUMBER_{k=3}(f)\), MONOCHROMATIC TRIANGLE(f), CUBIC SUBGRAPH(f), DOMINATING SET(f), ONE-IN-THREE 3-SAT(f), MONOTONE 3- SAT.