A feasible interpolation for random resolution

DOI10.23638/LMCS-13(1:5)2017zbMath1448.03047arXiv1604.06560MaRDI QIDQ2980967

Jan Krajíček

Publication date: 8 May 2017

Full work available at URL: https://arxiv.org/abs/1604.06560

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items

Resolution with counting: dag-like lower bounds and different moduli ⋮ Random resolution refutations

Cites Work

• The monotone circuit complexity of Boolean functions
• FRAGMENTS OF APPROXIMATE COUNTING
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Interpolation by a Game
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Unnamed Item
• Unnamed Item