principleCritical
How not to solve P=NP?
Viewed 0 times
notsolvehow
Problem
There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction.
I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called barriers that many proof attemps fail to overcome.
We want to avoid investigating into dead-ends, so what are they?
I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called barriers that many proof attemps fail to overcome.
We want to avoid investigating into dead-ends, so what are they?
Solution
I'd say the most well known barriers to solving $P=NP$ are
Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.
- Relativization (as mentioned by Ran G.)
- Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs.
- Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize cannot separate $P$ and $NP$
Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.
Context
StackExchange Computer Science Q#1877, answer score: 82
Revisions (0)
No revisions yet.