What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?

DOI10.1016/0168-0072(94)00059-CzbMath0834.03023MaRDI QIDQ1899145

Fernando Ferreira

Publication date: 2 November 1995

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

zbMATH Keywords

provabilitybounded arithmeticwitnessesPLS-problems

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Related Items (5)

Circuit principles and weak pigeonhole variants ⋮ 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 ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic

Cites Work

• How easy is local search?
• Bounded arithmetic and the polynomial hierarchy
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Unnamed Item
• Unnamed Item

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