The complexity of AUTOSAT(^i_m)

MaRDI QIDQ3086725zbMATH OpenFDO

Authors Flavio Ferrarotti, Jose Maria Turull Torres

Publication date 30 March 2011

zbMATH Keywords

completenesshardnesspolynomial-time reductionsrelational structureshigher-order logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Logics for complexity classes
• Arity and alternation in second-order logic
• Complete Problems for Higher Order Logics
• scientific article; zbMATH DE number 5041651
• The complexity of satisfiability problems

This page was built for publication: The complexity of \(\mathit{AUTOSAT}(\Sigma^i_m)\)

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