Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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}: \...
Barış Aydınlıoğlu's 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, ...
cody's user avatar
  • 13.9k

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