Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
From MaRDI portal
Publication:5311724
DOI10.2178/jsl/1080938841zbMath1068.03048OpenAlexW1964394232MaRDI QIDQ5311724
Publication date: 29 August 2005
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1080938841
provabilitypropositional proof systemspseudorandom generatorscircuit lower boundcomputational hardnessNisan-Wigderson generatorinput/output ratiohard tautologies
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (17)
Substitutions into propositional tautologies ⋮ Circuit principles and weak pigeonhole variants ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ Towards NP-P via proof complexity and search ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Unnamed Item ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ Unnamed Item ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION ⋮ Hardness magnification near state-of-the-art lower bounds
Cites Work
- Unnamed Item
- Hardness vs randomness
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Tautologies from Pseudo-Random Generators
- On the weak pigeonhole principle
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
This page was built for publication: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds