Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds

DOI10.2178/jsl/1080938841zbMath1068.03048OpenAlexW1964394232MaRDI QIDQ5311724

Jan Krajíček

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

zbMATH Keywords

provabilitypropositional proof systemspseudorandom generatorscircuit lower boundcomputational hardnessNisan-Wigderson generatorinput/output ratiohard tautologies

Mathematics Subject Classification ID

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