20
$\begingroup$

We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$.

However assume $P=NP$ and there are wise people who believe that possibility exists. If this is indeed the case then the very fact that we have not seen any good algorithms indicates there might be barriers in this alternate universe as well. Provability of $P\ne NP$ is barrier ridden and we do not know for sure $P\ne NP$ is the truth. We do not know for sure $P= NP$ is the truth either and so is provability of $P=NP$ also barrier ridden?

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ As Kaveh pointed out, if P=NP, then the natural proofs barrier seems to disappear. The relativization and algebrization barriers already worked against both $P=NP$ and $P\neq NP$. So I guess the answer is: natural proofs seems not to apply, but algebrization & relativization still apply. $\endgroup$
    – Joshua Grochow
    Commented May 25, 2018 at 18:59
  • 5
    $\begingroup$ @ThomasKlimpel: Relativization definitely applies to P=NP: Baker-Gill-Solovay gave an oracle rel to which P=NP, and an oracle rel to which P$\neq$NP, which means that relativizing techniques cannot resolve the P vs NP question in either direction. Algebrization was introduced because the proof that IP=PSPACE (and related things like MIP=NEXP) didn't relativize. $\endgroup$
    – Joshua Grochow
    Commented May 25, 2018 at 20:20
  • 3
    $\begingroup$ @ThomasKlimpel: an example of an algebrizing technique for proving equality is the IP=PSPACE result. I believe NL=coNL relativizes. I'm sure the AUC-SPACE(poly) =PSPACE result relativizes. In fact, I'm hard-pressed to think of any equality result that doesn't either relativize or algebrize. Re: "and if you know that algorithm": if P=NP, in some sense we do, namely Levin universal search! But Levin universal search relativizes... $\endgroup$
    – Joshua Grochow
    Commented May 26, 2018 at 1:59
  • 4
    $\begingroup$ There's no real barrier to just some crazy algorithm that happens to solve Boolean satisfiability. The lack of such a barrier certainly doesn't imply truth or even likelihood. $\endgroup$
    – Lance Fortnow
    Commented May 26, 2018 at 15:43
  • 3
    $\begingroup$ @Lance: Similarly, there's no real barrier to some crazy proof that just happens to show P$\neq$NP. It's when you try to figure out the details of what the proof will look like that things get tricky. $\endgroup$
    – Peter Shor
    Commented Jun 22, 2018 at 1:06

2 Answers 2

Reset to default
18
$\begingroup$

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 by Linear Programs, by Yannakakis.

This result was improved recently by Fiorini, Massar, Pokutta, Tiwary, and De Wolf to drop the "symmetric" requirement in Yannakakis' result.

Improve this answer
$\endgroup$
2
7
$\begingroup$

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, there are propositions with no polynomial size tree resolution proofs (see, e.g. these notes)

This creates potential obstructions to $\mathrm{coNP} = \mathrm{NP}$, which, of course, are obstructions to $\mathrm{P} = \mathrm{NP}$. E.g. one can forget about using resolution or any "classical" algorithm for SAT solving to try to find polynomial algorithms for SAT: they produce resolution proofs, which we know may be superpolynomial.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Dec 15, 2021 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.