On completeness for NP via projection translations
From MaRDI portal
Publication:4285624
DOI10.1007/BF01195200zbMath0794.03056MaRDI QIDQ4285624
Publication date: 24 March 1994
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Graph properties checkable in linear time in the number of vertices ⋮ Complete problems for monotone NP ⋮ Bounded-depth succinct encodings and the structure they imply on graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Graph minors. VI. Disjoint paths across a disc
- Complete problems for symmetric logspace involving free groups
- Using the Hamiltonian path operator to capture NP
- The polynomial-time hierarchy
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- Some Remarks on Generalized Spectra
- REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS