What are the _ 1^ b-consequences of T_ 2^ 1 and T_ 2^ 2?

DOI10.1016/0168-0072(94)00059-CMaRDI QIDQ1899145zbMATH OpenFDO

Authors Fernando Ferreira

Publication date 2 November 1995

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticprovabilitywitnessesPLS-problems

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Recommendations

• Bounded arithmetic and the polynomial hierarchy
• Fragments of bounded arithmetic and the lengths of proofs
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• scientific article; zbMATH DE number 218509

Cites work

• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Bounded arithmetic and the polynomial hierarchy
• How easy is local search?

Cited in

(5)

• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Circuit principles and weak pigeonhole variants
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• The provably total NP search problems of weak second order bounded arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem

This page was built for publication: What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?

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