The NP Search Problems of Frege and Extended Frege Proofs
From MaRDI portal
Publication:5278209
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
propositional logicbounded arithmeticproof complexityFrege proofstotal functionsNP search problemsextended Frege proofs
Related Items
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
