scientific article; zbMATH DE number 1775416

MaRDI QIDQ4542549zbMATH OpenFDO

Authors Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer

Publication date 1 August 2002

zbMATH Keywords

closed monadic NPcomplexity class

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The closure of monadic NP
• scientific article; zbMATH DE number 1688376
• Monotonicity and the Expressibility of NP Operators
• On monadic NP vs monadic co-NP
• Graph connectivity, monadic NP and built-in relations of moderate degree

Cited in

(14)

• The closure of monadic NP
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• On monadic NP vs monadic co-NP
• The monadic quantifier alternation hierarchy over grids and graphs
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1223637 (Why is no real title available?)
• Monotonicity and the Expressibility of NP Operators
• Subclasses of binary NP
• Graph connectivity, monadic NP and built-in relations of moderate degree
• scientific article; zbMATH DE number 910751 (Why is no real title available?)
• scientific article; zbMATH DE number 1424044 (Why is no real title available?)
• scientific article; zbMATH DE number 1424045 (Why is no real title available?)
• Expressing properties in second- and third-order logic: hypercube graphs and SATQBF
• Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This page was built for publication:

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