scientific article; zbMATH DE number 5161489

MaRDI QIDQ3444802zbMATH OpenFDO

Authors Dmitry Itsykson, A. A. Kozhevnikov

Publication date 4 June 2007

Full work available at URL http://www.pdmi.ras.ru/znsl/2006/v340.html

Mathematics Subject Classification ID

Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
• scientific article; zbMATH DE number 3952747
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• scientific article; zbMATH DE number 2086627
• scientific article; zbMATH DE number 2102736
• A lower bound for intuitionistic logic
• scientific article; zbMATH DE number 1984264
• scientific article; zbMATH DE number 1163984
• Tameness in least fixed-point logic and McColm's conjecture

Cited in

(11)

• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• Characterizing Tseitin-formulas with short regular resolution refutations
• Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
• Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies
• Towards NP-P via proof complexity and search
• Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
• TLA +  Proofs
• scientific article; zbMATH DE number 2086627 (Why is no real title available?)
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
• The power of the binary value principle

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3444802)