20

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.

Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?

An alternative statement of $\mathbf{P} \neq \mathbf{NP}$ is the extended Church-Turing Thesis. So if we have an speedup algorithm of other model than classic Turing Machine, we have to find an new algorithm for Turing Machine with the assumption $\mathbf{P} \neq \mathbf{NP}$ ? that means we have to find new speedup algorithm of factoring and the like.

  • 4
    I'm not quite sure why there is a negative reaction to this question. As everyone knows, there is a slew of results that start with "Assuming the Riemann Hypothesis, ..." -- see https://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis Now substitute $P \neq NP$ for RH; are there similar conditional results? – Todd Trimble Aug 17 '17 at 01:21
  • 7
    There are hundreds of results of the form, if P$\neq$NP, then these various specific problems have no polynomial-time feasible solution. This would be true, for example, of any NP-complete problem, of which many are known, and often very practical problems. In particular, I believe that there are important instances such as: if P$\neq$NP, then these various encryption schemes are safe against polynomial-time feasible attacks. But I'll let those who know better answer. – Joel David Hamkins Aug 17 '17 at 02:22
  • @ToddTrimble so do I. – XL _At_Here_There Aug 17 '17 at 02:28
  • @JoelDavidHamkins Those are well-known, and of course important, I wonder if there are important results for instance, of number theory,etc. – XL _At_Here_There Aug 17 '17 at 02:30
  • 3
    @XL_at_China, the question should state what you want to ask. Right now it is not a research-level question and it would be impossible to make any kind of list of answers here -- it would be a large fraction of all theoretical computer science results of the last 40 years. – usul Aug 17 '17 at 02:40
  • @usul Why do not we let people list the important results and have an overview or big picture of such question ? Maybe it is not only related to computational questions. – XL _At_Here_There Aug 17 '17 at 02:44
  • There are some definability results in finite models. There are algorithmic implications in various fields, including CSP results in Universal Algebra. I am no longer an expert, so I defer to others for details. However, I see them as mirroring results in TCS, so I think this question is a little broad for this forum. Gerhard "Like 'What Comes After This?'" Paseman, 2017.08.16. – Gerhard Paseman Aug 17 '17 at 03:13
  • 2
    Also, a few minutes of web searching and about an hour or two of blog reading can answer the question as stated. What should be asked are about lesser known consequences, not just any, so that the scope is sufficiently and explicitly made narrow. Gerhard "Clarity Makes Life Much Easier" Paseman, 2017.08.16. – Gerhard Paseman Aug 17 '17 at 03:22
  • 8
    @JoelDavidHamkins Just for posterity: There actually aren't really any statements of the form "If $\mathrm{P} \neq \mathrm{NP}$ then cryptosystem $X$ is secure." The reason is that generally cryptography requires not just that there exist hard instances of a problem, but that we can actually generate hard instances (and many of them) efficiently. I think basing cryptography on $\mathrm{P} \neq \mathrm{NP}$ is considered a major open problem. – Izaak Meckler Aug 17 '17 at 06:52
  • 1
    @IzaakMeckler Thanks for that. I guess P$\neq$NP gives you only worst-case difficulty, but if you can rob the bank 82% of the time, or even only 1% of the time, that is probably not acceptable. Incidentally, about generating hard instances of problems, see my question at https://mathoverflow.net/q/168619/1946. – Joel David Hamkins Aug 17 '17 at 10:56
  • The question will be closed soon? Why? – XL _At_Here_There Aug 17 '17 at 17:01
  • 1
    The question is a little broad as stated, but it has attracted one excellent answer and no trivial answers of the form "if $P \neq NP$ then the following 50 NP problems don't have polynomial solutions". It's probably possible to improve the question to focus on the former and exclude the latter, but for the moment this would be fixing something that isn't broken. – Paul Siegel Aug 17 '17 at 18:13
  • 1
    One reason it's innately harder to get 'deep' consequences of P vs. NP than RH is that the latter is about the existence of any instances of a given phenomenon (i.e., zeroes off the line) whereas the former is strictly about instances of a given size, so any consequences are going to have to involve some notion of size (be it dimension or otherwise) rather than pure existence/nonexistence. – Steven Stadnicki Aug 17 '17 at 21:51
  • Why to close the question? I feel strange about the closing – XL _At_Here_There Aug 18 '17 at 14:43
  • I vaguely recall having seen the phrase "extended Church-Turing thesis" used with a meaning different from P$\neq$NP. I believe it was something to the effect that any algorithm can be efficiently simulated by a Turing machine, where "efficiently" probably meant that the time increases only polynomially. – Andreas Blass Nov 11 '17 at 16:54
  • @AndreasBlass, that means any other computation models can not make the $\mathbf{NP}$ collapse to $\mathbf{P}$, which is more stronger than $\mathbf{NP}\neq\mathbf{P}$, or equivalent to $\mathbf{NP}\neq\mathbf{P}$ – XL _At_Here_There Nov 12 '17 at 02:52

2 Answers2

28

Because there are natural computational problems involving many mathematical objects, there are a bunch of implications of complexity class separations like $\mathrm{P} \neq \mathrm{NP}$. I think the first paper to investigate this idea is probably Mike Freedman's Complexity classes as mathematical axioms, which assumes a complexity class separation (namely $\mathrm{NP} \neq \mathrm{P}^{\#\mathrm{P}}$, which is stronger than $\mathrm{P} \neq \mathrm{NP}$) to prove that knots with certain properties exist.

The main idea of all these arguments is to prove an implication like "If all objects of type $T$ satisfy property $P$, then there is an efficient algorithm for a problem which we assumed has no efficient algorithm." You can then deduce the existence of objects of type $T$ which satisfy property $\neg P$. (Here the meaning of "efficient" depends on the class separation you assume.)

The exact thing Freedman proves is a little esoteric, so let me give two other examples that have a somewhat similar flavor.

  • The systole of a metric manifold is the length of the shortest non-contractible loop on it (I'll also use the word for the shortest loop itself). Probably the first manifold whose systole you'd try to understand is a flat torus $\mathbb{T}^d = \mathbb{R}^d / \Lambda$ for some lattice $\Lambda = \langle v_1, \dots, v_d \rangle$, since these are pretty much the simplest metric manifolds.

    One natural thing might be to try to say something about the word length of the systole $\gamma$ when considered as an element of $\pi_1(\mathbb{T}^d)$ equipped with the generating set $\{ v_1^*, \dots, v_d^* \}$ where $v_i^*$ is the loop in $\mathbb{T}^d$ naturally associated to $v_i$. For example, maybe the systole always has a relatively short word expressing it. Say, maybe we can always write $\gamma =_{\pi_1(\mathbb{T}^d)} \sum_i n_i v_i^*$ with $\sum_i |n_i| < \sqrt{d}$ or something.

    It turns out that a modest strengthening of $\mathrm{P} \neq \mathrm{NP}$ actually rules this out. Specifically, assuming that $\mathrm{NP}$-hard problems do not have time $2^{o(n)}$ bounded-error probabilstic algorithms, we can prove the following: For any $\ell(d) = o(d / \log d)$, there exist infinitely many $d$ and $\Lambda=(v_1, \dots, v_d)$ such that every systolic loop $\gamma$ on the torus $\mathbb{R}^d / \Lambda$ has word length at least $\ell(n)$ in the generating set $\{ v_1^*, \dots, v_d^* \}$.

    The idea of the argument is just that such a bound would imply a sub-exponential time algorithm for the $\mathrm{NP}$-hard problem of computing the systole: namely just enumerate all possible words in the generators of the given word length and pick the one which is represented by the shortest loop (this is easy to compute).

  • You can use a similar argument also to show that faithful representations of $S_n$ have dimension at least $n^{\varepsilon}$ for some $\varepsilon > 0$ (assuming some version of the strong exponential time hypothesis.) The basic idea is given here -- the argument is very simple.

These arguments I think give some idea of why proving class separations should be hard. They immediately imply that mathematical objects of all kinds must have certain kinds of complexity, or else they could be used to give algorithms contradicting the class separations. So, the class separation simultaneously demonstrates the existence of such complexity in all such mathematical objects at once.

Bonus: Tim Roughgarden and Inbal Talgam-Cohen have some writing along these lines as well showing that class separations imply markets in which certain kinds of equilibria do not exist.

18

Let me take a slightly different angle on this question and interpret it as asking what sorts of hardness results require P ≠ NP only, and which ones require stronger assumptions.

By itself, P ≠ NP implies (or more pedantically, is known to imply) less than what many people think. For example, here are some of the things that P ≠ NP is not known to imply:

  1. Factoring has no polynomial time algorithm.
  2. Graph isomorphism has no polynomial time algorithm.
  3. One-way functions exist.
  4. There is in general no short certificate that a graph is not Hamiltonian.
  5. There is no family of polynomial size circuits for SAT.
  6. NP-complete problems have no subexponential time algorithms.
  7. NP-complete problems are hard on average.
  8. There is no randomized polynomial time algorithm for an NP-complete problem.
  9. There is no polynomial time algorithm for an NP-complete problem on a quantum computer.

On the other hand, P ≠ NP does imply some results that might seem at first to be stronger than P ≠ NP. A notable class of examples are inapproximability results that follow from the PCP theorem. For example, if P ≠ NP then there is no polynomial time approximation algorithm for the size of the maximum independent set of a graph that is guaranteed to get within a constant (or even logarithmic) factor of the optimum. Another example is Mahaney's theorem that if P ≠ NP then there is no sparse set that is NP-complete.

Timothy Chow
  • 78,129
  • 1
    I guess you mean "is not known to imply" rather than "does not imply". Since if P=NP then P$\neq$NP implies everything. – Adam Przeździecki Aug 18 '17 at 13:10
  • 6
    @AdamPrzeździecki : Search the text of my post for "pedantic". – Timothy Chow Aug 18 '17 at 15:22
  • 5
    @JoelDavidHamkins : It is standard practice, not just in computational complexity but in all of mathematics, to use "implies" for conditionals other than the material conditional when the context makes it clear that the material conditional is not intended. For example when someone says that one theorem implies (or is equivalent to) another theorem, it is always understood that the material conditional is not intended. Here I even went to the trouble of saying explicitly which conditional is intended and you're still complaining? – Timothy Chow Aug 22 '17 at 14:47
  • 1
    OK, I deleted my comments. I also edited your answer. – Joel David Hamkins Aug 25 '17 at 14:50
  • An alternative statement of $\mathbf{P} \neq \mathbf{NP}$ is the extended Church-Turing Thesis. – XL _At_Here_There Nov 11 '17 at 03:34