Logical Description of Monotone NP Problems

DOI10.1093/logcom/4.4.337zbMath0809.68070OpenAlexW2091528516MaRDI QIDQ4305345

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

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

Related Items

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 ⋮ The price of query rewriting in ontology-based data access ⋮ Complete problems for monotone NP ⋮ Positive versions of polynomial time ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators