Using the Hamiltonian path operator to capture NP

DOI10.1016/0022-0000(92)90043-IzbMATH Open0752.68041OpenAlexW2007569718MaRDI QIDQ1198664FDOQ1198664

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

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

zbMATH Keywords

normal formfirst-order languagesexpressibilitycharacterizations of complexity classes

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• Title not available (Why is that?)
• Languages that Capture Complexity Classes
• Title not available (Why is that?)
• Symmetric space-bounded computation
• A complexity theory based on Boolean algebra
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (11)

• On completeness for NP via projection translations
• Positive versions of polynomial time
• Relativized logspace and generalized quantifiers over finite ordered structures
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)