Tautologies from Pseudo-Random Generators
From MaRDI portal
Publication:2736584
DOI10.2307/2687774zbMath0983.03046OpenAlexW2074374872MaRDI QIDQ2736584
Publication date: 10 September 2001
Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: http://www.math.ucla.edu/~asl/bsl/0702-toc.htm
First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (10)
Substitutions into propositional tautologies ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ The complexity of proving that a graph is Ramsey ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Proof Complexity of Non-classical Logics ⋮ ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
Cites Work
- The intractability of resolution
- Bounded arithmetic and the polynomial hierarchy
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Quantified propositional calculi and fragments of bounded arithmetic
- The relative efficiency of propositional proof systems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Natural proofs
This page was built for publication: Tautologies from Pseudo-Random Generators
