7
$\begingroup$

Here, 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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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, IPS '99), and an exponential lower bound for the clique-colouring formula in cutting planes (Pudlák '99). Nowadays there are a few more examples to choose from.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.