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

DOI10.1016/0168-0072(94)00059-CzbMATH Open0834.03023MaRDI QIDQ1899145FDOQ1899145

Authors: Fernando Ferreira 

Publication date: 2 November 1995

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

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

zbMATH Keywords

bounded arithmeticprovabilitywitnessesPLS-problems

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Cites Work

• Title not available (Why is that?)
• How easy is local search?
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Title not available (Why is that?)

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)