scientific article; zbMATH DE number 1916823
From MaRDI portal
Publication:4807964
zbMath1027.03044MaRDI QIDQ4807964
Edward A. Hirsch, Dimitrii V. Pasechnik, Dima Yu. Grigoriev
Publication date: 14 January 2004
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitylower boundsproof systemscomplexity of proofsclique-coloring tautologiessymmetric knapsack problemTseitin's tautologies
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (15)
Narrow Proofs May Be Maximally Long ⋮ Unnamed Item ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ The power of the binary value principle ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Proof Complexity Meets Algebra ⋮ Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ On the complexity of Hilbert refutations for partition ⋮ An improved semidefinite programming relaxation for the satisfiability problem ⋮ Several notes on the power of Gomory-Chvátal cuts ⋮ Resolution Width and Cutting Plane Rank Are Incomparable ⋮ Unnamed Item ⋮ Propositional proof complexity ⋮ On the Chvátal rank of the pigeonhole principle ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
This page was built for publication:
