Publication:4681889
From MaRDI portal
zbMath1079.03047MaRDI QIDQ4681889
M. V. Alekhnovich, Alexander A. Razborov
Publication date: 8 June 2005
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
06E30: Boolean functions
03F20: Complexity of proofs
Related Items
Proof Complexity Meets Algebra, Unnamed Item, Unnamed Item, Propositional proof complexity, Sharp Effective Finite-Field Nullstellensatz, Towards NP-P via proof complexity and search, Satisfiability, branch-width and Tseitin tautologies, Special issue in memory of Misha Alekhnovich. Foreword, Lower bounds for \(k\)-DNF resolution on random 3-CNFs, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Another look at degree lower bounds for polynomial calculus, A Framework for Space Complexity in Algebraic Proof Systems, Space Complexity in Polynomial Calculus