<p>For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the pigeonhole principle in polynomial calculus (<a href="https://dblp.org/rec/journals/cc/Razborov98" rel="noreferrer">Razborov '98</a>, <a href="https://dblp.org/rec/journals/cc/ImpagliazzoPS99" rel="noreferrer">IPS '99</a>), and an exponential lower bound for the clique-colouring formula in cutting planes (<a href="https://dblp.org/rec/journals/jsyml/Pudlak97" rel="noreferrer">Pudlák '99</a>). Nowadays there are a few more examples to choose from.</p>

CC BY-SA 4.0
2019-11-04T07:50:52.427Z
2019-11-04T07:50:52.427Z
notautogenerated
<p><a href="https://doi.org/10.1145/1562164.1562186" rel="noreferrer">Here</a>, Fortnow says (section 4.3):</p>

<blockquote>
  <p>Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on polynomials and (...)</p>
</blockquote>

<p>I am trying to find references to documents describing weaknesses for cutting planes and algebraic proof system regarding the P vs NP question. Unfortunately, Fortnow's document does not provide any.</p>

<cc.complexity-theory><cg.comp-geom><proofs><proof-complexity>
Document references describing weaknesses for cutting planes and algebraic proof system?
Jérôme Verstrynge
# Document references describing weaknesses for cutting planes and algebraic proof system?

(Asked by: username_0 on 2019-11-03)

[Here](https://doi.org/10.1145/1562164.1562186), Fortnow says (section 4.3):

> Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on polynomials and (...)

I am trying to find references to documents describing weaknesses for cutting planes and algebraic proof system regarding the P vs NP question. Unfortunately, Fortnow's document does not provide any.

**Tags:** cc.complexity-theory, cg.comp-geom, proofs, proof-complexity


---

## 1 answers

### Answer by username_1 on 2019-11-04. Score: 7 | Accepted answer

For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the pigeonhole principle in polynomial calculus ([Razborov '98](https://dblp.org/rec/journals/cc/Razborov98), [IPS '99](https://dblp.org/rec/journals/cc/ImpagliazzoPS99)), and an exponential lower bound for the clique-colouring formula in cutting planes ([Pudlák '99](https://dblp.org/rec/journals/jsyml/Pudlak97)). Nowadays there are a few more examples to choose from.


---

