Using the Hamiltonian path operator to capture NP

DOI10.1016/0022-0000(92)90043-IzbMath0752.68041OpenAlexW2007569718MaRDI QIDQ1198664

Iain A. Stewart

Publication date: 16 January 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90043-i

zbMATH Keywords

normal formexpressibilityfirst-order languagescharacterizations of complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

On completeness for NP via projection translations ⋮ Program Schemes with Deep Pushdown Storage ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Complete problems for monotone NP ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Positive versions of polynomial time ⋮ On the power of deep pushdown stacks ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symmetric space-bounded computation
• A complexity theory based on Boolean algebra
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation

This page was built for publication: Using the Hamiltonian path operator to capture NP