Complete problems for monotone NP
From MaRDI portal
Publication:673092
DOI10.1016/0304-3975(94)00175-IzbMATH Open0874.68126MaRDI QIDQ673092FDOQ673092
Authors: Iain Stewart 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- Languages that Capture Complexity Classes
- Methods for proving completeness via logical reductions
- The NP-completeness column: an ongoing guide
- Title not available (Why is that?)
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- On completeness for NP via projection translations
- Logical Description of Monotone NP Problems
- Using the Hamiltonian path operator to capture NP
- Title not available (Why is that?)
- A complexity theory based on Boolean algebra
- Title not available (Why is that?)
Cited In (11)
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- Using the Hamiltonian path operator to capture NP
- MPF problem over modified medial semigroup is NP-complete
- Graph properties checkable in linear time in the number of vertices
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Trahtenbrot-Zykov problem and NP-completeness
- Heuristics and exact algorithms for solving the Monden problem
- On the complexity of determining whether there is a unique Hamiltonian cycle or path
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- Adventures in monotone complexity and TFNP
- Title not available (Why is that?)
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)
