ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
From MaRDI portal
Publication:6204144
DOI10.1017/bsl.2023.40arXiv2208.11642OpenAlexW4388911622MaRDI QIDQ6204144
Publication date: 9 April 2024
Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.11642
bounded arithmeticproof searchweak pigeonhole principletime-bounded Kolmogorov complexityfeasible disjunction propertyproof complexity generators
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Communication complexity, information complexity (68Q11)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounded arithmetic and the polynomial hierarchy
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Tautologies from Pseudo-Random Generators
- On the weak pigeonhole principle
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Approximate counting by hashing in bounded arithmetic
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Proof Complexity
- Pseudorandom Generators in Propositional Proof Complexity
- Diagonalization in proof complexity
- INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
- Unexpected hardness results for Kolmogorov complexity under uniform reductions
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- On the computational complexity of finding hard tautologies
- Approximate counting in bounded arithmetic
This page was built for publication: ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
