$P\ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle

Ran Raz

Recent results established exponential lower bounds for the length of any Resolution proof for the weak pigeonhole principle. More formally, it was proved that any Resolution proof…