<p>Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program.</p>

<p>See the paper <a href="https://www.sciencedirect.com/science/article/pii/002200009190024Y?via%3Dihub" rel="noreferrer">Expressing combinatorial optimization problems by Linear Programs</a>, by Yannakakis.</p>

<p>This result was <a href="https://dl.acm.org/citation.cfm?id=2716307" rel="noreferrer">improved</a> recently by  Fiorini,  Massar, Pokutta,  Tiwary, and De Wolf to drop the "symmetric" requirement in Yannakakis' result.</p>

CC BY-SA 4.0
2018-06-22T14:58:57.520Z
Preprint of Fiorini et al. is https://arxiv.org/abs/1111.0837v5
András Salamon
CC BY-SA 4.0
2018-06-25T07:31:24.513Z
The relation of the latter result to P vs. NP is discussed e.g. here: https://cs.stackexchange.com/a/80173/1084
Martin Schwarz
CC BY-SA 4.0
2018-06-21T21:02:29.350Z
2018-06-21T21:55:34.980Z
2018-06-21T21:55:34.980Z
Peter Shor 
<p>Not much of a barrier, but it's worth noting that a lot of Proof Complexity research involves finding lower bounds to the <em>size</em> of proofs of propositional statements in certain settings.</p>
<p>For example, there are propositions with no polynomial size tree resolution proofs (see, e.g. <a href="https://people.clarkson.edu/%7Ealexis/PCMI/Notes/lectureA14.pdf" rel="noreferrer">these notes</a>)</p>
<p>This creates potential obstructions to <span class="math-container">$\mathrm{coNP} = \mathrm{NP}$</span>, which, of course, are obstructions to <span class="math-container">$\mathrm{P} = \mathrm{NP}$</span>. E.g. one can forget about using resolution or any &quot;classical&quot; algorithm for SAT solving to try to find polynomial algorithms for SAT: they produce resolution proofs, which we know may be superpolynomial.</p>

CC BY-SA 4.0
2021-12-15T04:09:48.547Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/132344/discussion-on-answer-by-cody-barriers-to-show-pnp).
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2021-11-16T22:57:46.543Z
2021-11-16T22:57:46.543Z
cody
<p>We all know showing $P\ne NP$ has barriers. We all have studied these barriers because we believe $P\ne NP$.</p>

<p>However assume $P=NP$ and there are <a href="https://emanueleviola.wordpress.com/2018/02/16/i-believe-pnp/" rel="noreferrer">wise people who believe that possibility exists</a>. 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?</p>

CC BY-SA 4.0
2018-05-25T18:39:44.267Z
Note that natural proofs barrier assumes existence of strong psuedo-random number generators. The same assumption implies that P is not equal to NP.
Kaveh
CC BY-SA 4.0
2018-05-25T18:59:49.430Z
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
CC BY-SA 4.0
2018-05-25T20:00:05.483Z
@JoshuaGrochow Are you sure that relativization still applies against $P = NP$? I thought algebrization was introduced as barrier against proving $N=NP$ (and similar problems), after work on interactive proofs showed that relativization is not really an effective barrier against proving equality.
Thomas Klimpel
CC BY-SA 4.0
2018-05-25T20:20:04.060Z
@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
CC BY-SA 4.0
2018-05-25T20:40:41.890Z
@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
CC BY-SA 4.0
2018-05-25T20:58:36.000Z
I admit that the existence of an oracle relative to which P≠NP is nice evidence in favor of P≠NP. But the obstacle towards proving P=NP is the "fact" that P≠NP. If it were indeed the case that P=NP, then there would be an algorithm, and if you know that algorithm, then the only remaining task is proving that it runs in polynomial time and solves the problem. I don't think that relativization will be a barrier against that task.
Thomas Klimpel
CC BY-SA 4.0
2018-05-26T01:59:19.277Z
@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
CC BY-SA 4.0
2018-05-26T02:02:13.430Z
Actually, REG=DTIME(o(nlogn)) surely doesn't relativize, but that may have to do with the fact that REG itself seems not to relativize very well.
Joshua Grochow
CC BY-SA 4.0
2018-05-26T09:58:47.033Z
I don't know whether this should be considered a 'barrier' similar to those for P vs NP, but there has been some work on showing that TSP cannot be solved solved by small linear programs, which invalidated some previous attempts at showing P=NP. See [this blogpost](https://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/), for example.
Discrete lizard
CC BY-SA 4.0
2018-05-26T15:43:37.423Z
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
CC BY-SA 4.0
2018-05-27T03:03:48.463Z
Analogously, could  the P = NP barrier have similar barriers for the VP = VNP (ie to show VP = VNP)question. In other words, what barriers could be there to show VP = VNP.
user3483902
CC BY-SA 4.0
2018-06-22T01:06:21.877Z
@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.
Peter Shor 
<p-vs-np><barriers>
Barriers to show $P=NP$
Turbo
# Barriers to show $P=NP$

(Asked by: username_0 on 2018-05-25)

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](https://emanueleviola.wordpress.com/2018/02/16/i-believe-pnp/). 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?

**Tags:** p-vs-np, barriers
> **Comments:**
> **username_1**: Note that natural proofs barrier assumes existence of strong psuedo-random number generators. The same assumption implies that P is not equal to NP.  
> **username_2**: 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.  
> **username_3**: @JoshuaGrochow Are you sure that relativization still applies against $P = NP$? I thought algebrization was introduced as barrier against proving $N=NP$ (and similar problems), after work on interactive proofs showed that relativization is not really an effective barrier against proving equality.  
> **username_2**: @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.  
> **username_3**: @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.  
> **username_3**: I admit that the existence of an oracle relative to which P≠NP is nice evidence in favor of P≠NP. But the obstacle towards proving P=NP is the "fact" that P≠NP. If it were indeed the case that P=NP, then there would be an algorithm, and if you know that algorithm, then the only remaining task is proving that it runs in polynomial time and solves the problem. I don't think that relativization will be a barrier against that task.  
> **username_2**: @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...  
> **username_2**: Actually, REG=DTIME(o(nlogn)) surely doesn't relativize, but that may have to do with the fact that REG itself seems not to relativize very well.  
> **username_4**: I don't know whether this should be considered a 'barrier' similar to those for P vs NP, but there has been some work on showing that TSP cannot be solved solved by small linear programs, which invalidated some previous attempts at showing P=NP. See [this blogpost](https://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/), for example.  
> **username_5**: 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.  
> **username_6**: Analogously, could  the P = NP barrier have similar barriers for the VP = VNP (ie to show VP = VNP)question. In other words, what barriers could be there to show VP = VNP.  
> **username_7**: @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.  

---

## 2 answers

### Answer by username_7 on 2018-06-21. Score: 18

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](https://www.sciencedirect.com/science/article/pii/002200009190024Y?via%3Dihub), by Yannakakis.

This result was [improved](https://dl.acm.org/citation.cfm?id=2716307) recently by Fiorini, Massar, Pokutta, Tiwary, and De Wolf to drop the "symmetric" requirement in Yannakakis' result.

> **Comments:**
> **username_8**: Preprint of Fiorini et al. is https://arxiv.org/abs/1111.0837v5  
> **username_9**: The relation of the latter result to P vs. NP is discussed e.g. here: https://cs.stackexchange.com/a/80173/1084  

---

### Answer by username_10 on 2021-11-16. Score: 7

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](https://people.clarkson.edu/%7Ealexis/PCMI/Notes/lectureA14.pdf))

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.

> **Comments:**
> **username_11**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/132344/discussion-on-answer-by-cody-barriers-to-show-pnp).  

---

