Using the Hamiltonian path operator to capture NP

DOI10.1016/0022-0000(92)90043-IMaRDI QIDQ1198664zbMATH OpenOpenAlexFDO

Authors Iain 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 formfirst-order languagesexpressibilitycharacterizations of complexity classes

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 88947
• scientific article; zbMATH DE number 223337
• scientific article; zbMATH DE number 139797
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Complete problems for monotone NP

Cites work

• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 43004 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Symmetric space-bounded computation

Cited in

(11)

• On completeness for NP via projection translations
• Positive versions of polynomial time
• scientific article; zbMATH DE number 139797 (Why is no real title available?)
• Relativized logspace and generalized quantifiers over finite ordered structures
• Complete problems for monotone NP
• Program Schemes with Deep Pushdown Storage
• Context-sensitive transitive closure operators
• Succinct representation, leaf languages, and projection reductions
• On the power of deep pushdown stacks
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• scientific article; zbMATH DE number 88947 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198664)