Logical Description of Monotone NP Problems

DOI10.1093/LOGCOM/4.4.337MaRDI QIDQ4305345zbMATH OpenOpenAlexFDO

Authors Iain Stewart

Publication date 13 September 1994

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/4.4.337

zbMATH Keywords

computational complexityconjunctive random-access Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Logics for complexity classes
• Monotonicity and the Expressibility of NP Operators
• Complete problems for monotone NP
• scientific article; zbMATH DE number 2079027
• scientific article; zbMATH DE number 1678393

Cited in

(8)

• Positive versions of polynomial time
• Context-sensitive transitive closure operators
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• The price of query rewriting in ontology-based data access
• Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
• Graph properties checkable in linear time in the number of vertices
• Positive First-order Logic on Words and Graphs
• Complete problems for monotone NP

This page was built for publication: Logical Description of Monotone NP Problems

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