Complete problems for monotone NP

DOI10.1016/0304-3975(94)00175-IMaRDI QIDQ673092zbMATH OpenFDO

Authors Iain Stewart

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

monotone NP

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 3921977
• On the Computational Complexity of Monotone Constraint Satisfaction Problems
• scientific article; zbMATH DE number 2079027
• Logical Description of Monotone NP Problems
• Adventures in monotone complexity and TFNP
• Monotonicity and the Expressibility of NP Operators
• The monotone Lambek calculus is NP-complete
• Completely inapproximable monotone and antimonotone parameterized problems
• scientific article; zbMATH DE number 1342209
• Complete problems for space bounded subclasses of NP

Cites work

• scientific article; zbMATH DE number 3889514 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512825 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Languages that Capture Complexity Classes
• Logical Description of Monotone NP Problems
• Methods for proving completeness via logical reductions
• On completeness for NP via projection translations
• The NP-completeness column: an ongoing guide
• Using the Hamiltonian path operator to capture NP

Cited in

(11)

• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• On the complexity of determining whether there is a unique Hamiltonian cycle or path
• Trahtenbrot-Zykov problem and NP-completeness
• Graph properties checkable in linear time in the number of vertices
• Heuristics and exact algorithms for solving the Monden problem
• Adventures in monotone complexity and TFNP
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• MPF problem over modified medial semigroup is NP-complete
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Using the Hamiltonian path operator to capture NP
• scientific article; zbMATH DE number 88947 (Why is no real title available?)

This page was built for publication: Complete problems for monotone NP

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