Publication:4818823
From MaRDI portal
zbMath1045.03524MaRDI QIDQ4818823
Publication date: 24 September 2004
03F30: First-order arithmetic and fragments
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Natural proofs, Resolution lower bounds for the weak functional pigeonhole principle., Resolution lower bounds for perfect matching principles, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Partially definable forcing and bounded arithmetic, The complexity of the Hajós calculus for planar graphs, On the correspondence between arithmetic theories and propositional proof systems – a survey