18
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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 mathoverflow.net/questions/17209/… Now substitute $P \neq NP$ for RH; are there similar conditional results? $\endgroup$ – Todd Trimble Aug 17 '17 at 1:21
  • 7
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Aug 17 '17 at 2:22
  • 3
    $\begingroup$ @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. $\endgroup$ – usul Aug 17 '17 at 2:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Aug 17 '17 at 3:22
  • 8
    $\begingroup$ @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. $\endgroup$ – Izaak Meckler Aug 17 '17 at 6:52
28
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Excellent, I appreciate your post. Since the question is about big-list, let's wait for more answer. $\endgroup$ – XL _At_Here_There Aug 17 '17 at 17:42
  • $\begingroup$ It is very interesting that NP is related to prices. $\endgroup$ – XL _At_Here_There Aug 17 '17 at 17:45
15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I guess you mean "is not known to imply" rather than "does not imply". Since if P=NP then P$\neq$NP implies everything. $\endgroup$ – Adam Przeździecki Aug 18 '17 at 13:10
  • 5
    $\begingroup$ @AdamPrzeździecki : Search the text of my post for "pedantic". $\endgroup$ – Timothy Chow Aug 18 '17 at 15:22
  • 4
    $\begingroup$ @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? $\endgroup$ – Timothy Chow Aug 22 '17 at 14:47
  • 1
    $\begingroup$ OK, I deleted my comments. I also edited your answer. $\endgroup$ – Joel David Hamkins Aug 25 '17 at 14:50
  • $\begingroup$ An alternative statement of $\mathbf{P} \neq \mathbf{NP}$ is the extended Church-Turing Thesis. $\endgroup$ – XL _At_Here_There Nov 11 '17 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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