scientific article; zbMATH DE number 999649

MaRDI QIDQ3128124zbMATH OpenFDO

Authors B. Ya. Bochernikov

Publication date 3 September 1997

zbMATH Keywords

bounded arithmeticbounded formulamodel completenessmodels of arithmeticNP=co-NP problemrecursive theoryrelativized polynomial time hierarchy

Mathematics Subject Classification ID

Models of arithmetic and set theory (03C62) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Publication:4893139
• \(\text{NP}\not={co}\)-NP and models of arithmetic
• Forcing on bounded arithmetic II

Cited in

(25)

• On the structure of initial segments of models of arithmetic
• Binary models generated by their tally part
• Inconsistent models of arithmetic. I: Finite models
• On the bounded version of Hilbert's tenth problem
• Models of arithmetic in \(A\)-isols
• Structures interpretable in models of bounded arithmetic
• Existentially Closed Models and Conservation Results in Bounded Arithmetic
• scientific article; zbMATH DE number 3896918 (Why is no real title available?)
• Regularity in models of arithmetic
• scientific article; zbMATH DE number 176198 (Why is no real title available?)
• scientific article; zbMATH DE number 176204 (Why is no real title available?)
• Forcing on bounded arithmetic II
• scientific article; zbMATH DE number 1344922 (Why is no real title available?)
• A small reflection principle for bounded arithmetic
• scientific article; zbMATH DE number 1136103 (Why is no real title available?)
• A theory for Log-Space and NLIN versus co-NLIN
• scientific article; zbMATH DE number 218509 (Why is no real title available?)
• scientific article; zbMATH DE number 922619 (Why is no real title available?)
• Construction of models of bounded arithmetic by restricted reduced powers
• A finite model-theoretical proof of a property of bounded query classes within PH
• Model theory of bounded arithmetic with applications to independence results
• scientific article; zbMATH DE number 2208069 (Why is no real title available?)
• Models of Bounded Arithmetic Theories and Some Related Complexity Questions
• P, NP, Co-NP and weak systems of arithmetic
• Preservation theorems for bounded formulas

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 Q3128124)