The NP Search Problems of Frege and Extended Frege Proofs

DOI10.1145/3060145zbMath1407.03071OpenAlexW2604582573WikidataQ114614088 ScholiaQ114614088MaRDI QIDQ5278209

Arnold Beckmann, Samuel R. Buss

Publication date: 13 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://cronfa.swan.ac.uk/Record/cronfa32250/Download/0032250-10032017090659.pdf

zbMATH Keywords

propositional logicbounded arithmeticproof complexityFrege proofstotal functionsNP search problemsextended Frege proofs

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items (4)

TFNP: An Update ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Towards a unified complexity theory of total functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• How easy is local search?
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Towards a unified complexity theory of total functions
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• A bounded arithmetic AID for Frege systems
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• The provably total search problems of bounded arithmetic
• The strength of sharply bounded induction
• An Optimal Parallel Algorithm for Formula Evaluation
• The relative efficiency of propositional proof systems
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• NP search problems in low fragments of bounded arithmetic
• Implicit proofs
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Logical Foundations of Proof Complexity

This page was built for publication: The NP Search Problems of Frege and Extended Frege Proofs