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}: \...
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, ...
- 13.7k
Only top scored, non community-wiki answers of a minimum length are eligible