Alternating minima and maxima, Nash equilibria and bounded arithmetic

DOI10.1016/j.apal.2011.06.014zbMath1345.03108OpenAlexW2093643669MaRDI QIDQ764279

Neil Thapen, Pavel Pudlák

Publication date: 13 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.apal.2011.06.014

zbMATH Keywords

computational complexitybounded arithmeticequilibriasearch problemsproof complexityfinite games

Mathematics Subject Classification ID

Noncooperative games (91A10) Applications of game theory (91A80) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20) Relative consistency and interpretations (03F25)

Related Items

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How easy is local search?
• The relative complexity of NP search problems
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
• The provably total search problems of bounded arithmetic
• The strength of sharply bounded induction
• The complexity of pure Nash equilibria
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• NP search problems in low fragments of bounded arithmetic
• Fragments of bounded arithmetic and the lengths of proofs
• Algorithms and Computation