18 votes

Barriers to show $P=NP$

Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program. See the paper Expressing combinatorial optimization problems ...
14 votes

Proofs, Barriers and P vs NP

Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example, $$\tag{$\dagger$}(\exists \mathcal{C}: \...
user avatar
7 votes

Barriers to show $P=NP$

Not much of a barrier, but it's worth noting that a lot of Proof Complexity research involves finding lower bounds to the size of proofs of propositional statements in certain settings. For example, ...
user avatar
  • 13.2k

Only top scored, non community-wiki answers of a minimum length are eligible