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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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