Tautologies from pseudo-random generators

DOI10.2307/2687774MaRDI QIDQ2736584zbMATH OpenOpenAlexFDO

Authors Jan Krajíček

Publication date 10 September 2001

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL http://www.math.ucla.edu/~asl/bsl/0702-toc.htm

zbMATH Keywords

extended Frege systemshardnessproof complexityrandom number generatorstautologies

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

This is the introduction and guide to the author's effort to produce tautologies, hard to be shown to be so, by using random number generators. [The technical side is his ``On the weak pigeonhole principle, Fundam. Math. 170, No. 1-2, 123-140 (2001; Zbl 0987.03051)]. Here, he starts from the first step: explaining what extended Frege systems are, and why they are used. He gives concise accounts of propositional proof complexity, bounded arithmetic, random generators, and a new hardness condition (called `free'). Also, there are a conjecture, a theorem, relations with pigeonhole principles, and examples and comments. As usual, the author presents a pleasant article: informative, friendly, etc.

Recommendations

• Pseudorandom Generators in Propositional Proof Complexity
• Generating hard tautologies using predicate logic and the symmetric group
• Logical Approaches to Computational Barriers
• scientific article; zbMATH DE number 1114014
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution

Cites work

• Bounded arithmetic and the polynomial hierarchy
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds to the size of constant-depth propositional proofs
• Natural proofs
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Quantified propositional calculi and fragments of bounded arithmetic
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• The intractability of resolution
• The relative efficiency of propositional proof systems

Cited in

(12)

• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Hardness assumptions in the foundations of theoretical computer science
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• On the correspondence between arithmetic theories and propositional proof systems – a survey
• Generating hard tautologies using predicate logic and the symmetric group
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Proof complexity of non-classical logics
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Symmetric exponential time requires near-maximum circuit size
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• Substitutions into propositional tautologies

This page was built for publication: Tautologies from pseudo-random generators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2736584)