scientific article; zbMATH DE number 2174386
From MaRDI portal
Publication:4681889
zbMath1079.03047MaRDI QIDQ4681889
M. V. Alekhnovich, Alexander A. Razborov
Publication date: 8 June 2005
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Complexity of proofs (03F20)
Related Items (13)
Space Complexity in Polynomial Calculus ⋮ 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 ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Unnamed Item ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Propositional proof complexity ⋮ Another look at degree lower bounds for polynomial calculus
This page was built for publication:
