Monotonicity and the Expressibility of NP Operators

DOI10.1002/MALQ.19940400118MaRDI QIDQ4304159zbMATH OpenOpenAlexFDO

Authors Iain Stewart

Publication date 7 June 1995

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19940400118

zbMATH Keywords

complexity class NPexpressibilityfinite structuresfirst-order logicgeneralized quantifiers

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 4009811
• scientific article; zbMATH DE number 910751
• The closure of monadic NP
• scientific article; zbMATH DE number 1775416

Cited in

(13)

• Finite \(H\)-dimension does not imply expressive completeness
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Expressibility in _1¹
• scientific article; zbMATH DE number 4009811 (Why is no real title available?)
• scientific article; zbMATH DE number 515741 (Why is no real title available?)
• Logical Description of Monotone NP Problems
• scientific article; zbMATH DE number 2079027 (Why is no real title available?)
• scientific article; zbMATH DE number 1555193 (Why is no real title available?)
• scientific article; zbMATH DE number 1775416 (Why is no real title available?)
• scientific article; zbMATH DE number 910751 (Why is no real title available?)
• Adventures in monotone complexity and TFNP
• Universal first-order logic is superfluous for NL, P, NP and coNP
• Complete problems for monotone NP

This page was built for publication: Monotonicity and the Expressibility of NP Operators

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