ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
From MaRDI portal
Publication:3094358
DOI10.1142/S0219061311000979zbMath1259.03073MaRDI QIDQ3094358
Publication date: 24 October 2011
Published in: Journal of Mathematical Logic (Search for Journal in Brave)
propositional logicdisjunction propertyproof complexityreflection principlepropositional proof systemNisan-Wigderson generator
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (5)
ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Circuit lower bounds in bounded arithmetics ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Unnamed Item
Cites Work
- Bounded arithmetic and the polynomial hierarchy
- Hardness vs randomness
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Tautologies from Pseudo-Random Generators
- On the weak pigeonhole principle
- Nisan-Wigderson generators in proof systems with forms of interpolation
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- The relative efficiency of propositional proof systems
- Foundations of Cryptography
- Diagonalization in proof complexity
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Computational Complexity
- Logical Foundations of Proof Complexity
This page was built for publication: ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
