# Barriers to show $P=NP$

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?

• 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. – Joshua Grochow May 25 '18 at 18:59
• @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. – Joshua Grochow May 25 '18 at 20:20
• @JoshuaGrochow What is a relativizing technique for proving equality? Does the proof that log(n)-AuxPDA equals P uses a relativizing technique? I believe that I read somewhere that there is an oracle relative to which log(n)-AuxPDA != P, but maybe this is more related to the subtleties of oracles for space bounded computations. However, for proving inequality, it is pretty obvious that most know methods relativize. – Thomas Klimpel May 25 '18 at 20:40
• @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... – Joshua Grochow May 26 '18 at 1:59
• 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. – Lance Fortnow May 26 '18 at 15:43