ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS

DOI10.1017/bsl.2023.40arXiv2208.11642OpenAlexW4388911622MaRDI QIDQ6204144

Jan Krajíček

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

zbMATH Keywords

bounded arithmeticproof searchweak pigeonhole principletime-bounded Kolmogorov complexityfeasible disjunction propertyproof complexity generators

Mathematics Subject Classification ID

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