Complete problems for monotone NP

DOI10.1016/0304-3975(94)00175-IzbMath0874.68126MaRDI QIDQ673092

Iain A. 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)

Related Items

On locating cubic subgraphs in bounded-degree connected bipartite graphs, Graph properties checkable in linear time in the number of vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Methods for proving completeness via logical reductions
• Using the Hamiltonian path operator to capture NP
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• The NP-completeness column: an ongoing guide
• A complexity theory based on Boolean algebra
• Languages that Capture Complexity Classes
• On completeness for NP via projection translations
• Logical Description of Monotone NP Problems