Structure with fast elimination of quantifiers

DOI10.2178/JSL/1140641177MaRDI QIDQ5477638zbMATH OpenOpenAlexFDO

Authors Mihai Prunescu

Publication date 5 July 2006

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/jsl/1140641177

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Logical Approaches to Computational Barriers
• scientific article; zbMATH DE number 1670470
• Quantifier elimination for the reals with a predicate for the powers of two
• On relativizations of the P =? NP question for several structures
• P versus NP and computability theoretic constructions in complexity theory over algebraic structures

Cites work

• \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
• Non-effective quantifier elimination
• Outline of a Theory of Truth

Cited in

(4)

• scientific article; zbMATH DE number 1670470 (Why is no real title available?)
• On relativizations of the P =? NP question for several structures
• Logical Approaches to Computational Barriers
• The path-bifurcation hierarchy does not collapse to ^1 in infinite abelian groups

This page was built for publication: Structure with fast elimination of quantifiers

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