NP- and PSPACE- and NLOG-completeness I

14 novembro 2013, 12:30 • José Félix Costa

NP-completeness of K, SAT, CNF-SAT and CLIQUE. PSPACE-completeness of QBF. NLOG-completeness of REACHABILITY.

Context sensitive grammars. Theorem: the class of sets generable by context sensitive grammars is NSPACE(n). Consequences.

PSPACE-completeness of CSG-ACCEPTANCE.