All about Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike

Notes: bounded degree, treelike, with squares

Proof Systems

• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulates Truth table
• Source: tlLSd+ → tlLS+ → tlLS → tlRes → ttp
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulates Tree-like resolution
• Source: tlLSd+ → tlLS+ → tlLS → tlRes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Regular resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike not simulated by Ordered resolution
• Source: tlLSd+ → tlLS+ → tlLS → tlRes → pearl → ordRes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Pool resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Linear resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Reversible resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Cutting Planes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Tree-like Cutting Planes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Cutting Planes with Unary Coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Semantic Cutting Planes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Cutting Planes with Saturation
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Stabbing Planes
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Stabbing Planes with Unary Coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(CP)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(LP)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(CP) with unary coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(LP) with unary coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(L\(\&\)P)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Res(L\(\&\)P) with unary coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulated by Semantic degree-k threshold system, treelike version
• Source: [subsystem]
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Polynomial Calculus over \(\mathbb{F}_2\)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Nullstellensatz over \(\mathbb{F}_2\)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] ResLin over \(\mathbb{Q}\), ResLin, Resolution over linear equations over rationals
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] unary ResLin over \(\mathbb{Q}\), ResLin, Resolution over linear equations over rationals
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] ResLin over \(\mathbb{F}_2\), Res(\(\oplus\))
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Tree-like ResLin over \(\mathbb{F}_2\), treelike Res(\(\oplus\))
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Polynomial Calculus over \(\mathbb{Q}\)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Nullstellensatz over \(\mathbb{Q}\)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulates Hitting
• Source: tlLSd+ → tlLS+ → tlLS → tlRes → hit
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Lift and Project
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Lift and Project with unary coefficients
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Positivstellensatz Calculus
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Positivstellensatz
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Lovász--Schrijver (LS)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Lovász--Schrijver with squares (LS\(_+\))
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulated by Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree
• Source: [subsystem]
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulated by Lovász--Schrijver with squares (LS\(_+^\infty\)), unbounded degree
• Source: LSn+ → LSd+ → tlLSd+
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulated by Cone Proof System
• Source: CPS → LSn+ → LSd+ → tlLSd+
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulates tl Lovász--Schrijver (LS)
• Source: tlLSd+ → tlLS+ → tlLS
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike simulates Lovász--Schrijver with squares (LS\(_+\))
• Source: [subsystem]
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] static Lovász--Schrijver (static LS)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] static Lovász--Schrijver, with squares of linear functions (static LS\(_+\))
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] static Lovász--Schrijver, with squares of linear functions (static LS\(_+^n\))
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Sum of Squares (Lasserre)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Sherali--Adams
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Circular resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Unary Sherali--Adams
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Ideal Proof System
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Extended Frege
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Extended resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Frege
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] \(\mathrm{AC}^0\)-Frege
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] k-DNF Resolution
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] \(\mathrm{TC}^0\)-Frege
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] \(\mathrm{AC}^0\)-Frege with mod 2 axioms
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] \(\mathrm{AC}^0\)-Frege with mod 2 gates
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] OBDD(join,weakening)
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] LK
• Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike [missing?] Zermelo-Fraenkl Set Theory with the Axiom of Choice

Formulas

• The size complexity of Pigeonhole principle in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Pigeonhole principle with functionality axioms in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Pigeonhole principle with functionality and onto axioms in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Weak pigeonhole principle (2n pigeons, n holes) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Weak pigeonhole principle (\(n^2\) pigeons, n holes) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Bitwise pigeonhole principle in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is exponential
• Source: bPHP → tlTH(k) → tlLSd+
• The size complexity of Relativized pigeonhole principle (n,\(n^2\),n-1) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Ordering principle in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Guarded ordering principle in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Tseitin over \(\mathbb{F}_2\) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Tseitin over \(\mathbb{F}_2\) with k-ary AND gadget in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is exponential
• Source: tseitin-and-k → tlTH(k) → tlLSd+
• The size complexity of Tseitin over \(\mathbb{Q}\) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Flow in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Tseitin \(\mathbb{F}_2\) \(\circ\) IND in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Tseitin \(\mathbb{Q}\) \(\circ\) IND in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Random CNF in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Clique-Colouring in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Clique-Colouring encoded as equalities in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Weak Clique-Colouring (2m clique, m colours) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Weak Clique-Colouring (m^1/2 clique, log^2 m colours) in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Clique-Colouring composed with a permutation in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Pebbling \(\circ\) IND in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Pebbling \(\circ\) XOR, then guarded in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of Stone formula in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]
• The size complexity of String of pearls in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is at most quasipolynomial
• Source: tlLSd+ → tlLS+ → tlLS → tlRes → pearl
• The size complexity of Sink of DAG \(\circ\) XOR in Lovász--Schrijver with squares (LS\(_+^d\)), bounded degree, treelike is [missing?]

This database is still incomplete; missing data may indicate either the information was not yet recorded or an open problem. Users are encouraged to contribute missing proof systems and/or relations at https://gitlab.com/proofcomplexityzoo/zoo.

Licensed under CC BY 4.0