6
$\begingroup$

Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum.

Here we see 116 previous attempts at solving P vs. NP.

Here we see the P vs NP problem defined as:

The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).

Here the commentator writes:

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

My question is: What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

$\endgroup$
  • $\begingroup$ Maybe there are algorithms which have been proved to have optimal running time but weren't analyzed explicitly. $\endgroup$ – Andrew Aug 15 '17 at 13:19
  • $\begingroup$ It appears that Norbert Blom in your reference (attemps to) prove quite the opposite, namely P unequal NP (quoting from the abstract: "This implies P not equal NP".) $\endgroup$ – user53923 Aug 15 '17 at 14:47
  • $\begingroup$ Practical utility? None. The relevance of the P-NP question on practice is generally overstated (imho). It is, of course, of very much interest for complexity theory. The two things are not the same, even if some complexity theorists seem to forget that at times. $\endgroup$ – Raphael Aug 16 '17 at 19:52
5
$\begingroup$

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along.


It's much worse, because most researchers believe that $P\ne NP$, meaning that even when the proof is discovered, it means that we won't be able to find a polynomial-time algorithm for SAT, not because we're looking in the wrong places, but because no such algorithm exists.

But that doesn't worry most complexity theorists, because the would-be algorithm for SAT that you describe is only a practical application, a spin-off, of the proof. And if you care about practical applications, then why are you working on $P=NP$? It's the most theoretical question in computer science!

Rather, the motivation behind research in this direction is* to better understand computation, very much akin to why mathematicians care about the Riemann hypothesis, and why physicists build giant particle colliders, even though we already have giant databases of prime numbers and even though the discovery of new particles mostly does not help us build faster rockets or better fusion reactors.

But what don't we understand about computation? We can build marvellous AI systems that recognize faces and Chinese characters, and predict the weather! Those are results of the form, this problem can be solved with so-and-so many resources, but on the flip side, one can ask, for this problem, what is the minimum amount of resources needed? The current state of affairs in the last regard is rather embaressing, because as far as we know:

  • SAT has a linear-time (!) algorithm**
  • SAT has an algorithm that uses $O(n^{1.802})$ time and $O(\sqrt{n})$ space
  • every language in $NP$ has a circuit with $5n$ gates.
  • The Succinct Circuit Satisfiability problem***, which is $NEXP$-Complete ($NEXP$ is the exponential-time version of $NP$), can be solved in polynomial time with a randomized algorithm with bounded error (i.e. it gives the wrong answer only with probability $\leq \frac{1}{n}$)
  • Everything that can be computed using a polynomial amount of memory can be solved using a polynomial amount of time. For example, the Quantified Boolean Formula problem, which is like SAT except instead of an $\exists$ quantifier, there are any number of $\exists x\colon\forall y\colon\exists z\colon\cdots$ quantifiers.

Until these ridiculous scenarios are ruled out, we cannot honestly say that we understand computation in any depth. And that is the utility that you ask for, of why anybody at all works on $P=NP$.

I encourage you to read this wonderful survey of Scott Aaronson where in section 1.2 he addresses all the usual objections, like, what if $P=NP$ but we can't find the algorithm, or what if we do, but it's exponent is hopeless, or...


*as far as I can tell, as someone who is not a professional complexity theorist, but who did write his Master's thesis on the topic.

** We do not know whether nondeterminism gives you an advantage for solving SAT, but we do know, since 1983 [1] that nondeterminism gives you an advantage for some language, because there is a language $L$ solvable by a non-deterministic machine in $O(n)$ time but not by any deterministic machine in $O(n)$ time. In 2001, that result was improved [2] to a language in $NTime(n)$ but not in $DTime(n\sqrt{\log(n)})$.

*** The Succinct Circuit Satisfiability problem is this: fix some encoding of Boolean circuits as binary strings. You are given a circuit on $n$ inputs. Interpret the truth table of this circuit as a binary string of length $2^n$. Interpret that string as representing a circuit. Is that circuit satisfiable?

[1] Paul, Wolfgang J., et al. "On determinism versus non-determinism and related problems." Foundations of Computer Science, 1983., 24th Annual Symposium on. IEEE, 1983.

[2] Santhanam, Rahul. "On separators, segregators and time versus space." Computational Complexity, 16th Annual IEEE Conference on, 2001.. IEEE, 2001.

$\endgroup$
  • $\begingroup$ Wait, what? How that linear time algorithm for SAT behaves? $\endgroup$ – rus9384 Aug 15 '17 at 14:18
  • $\begingroup$ @rus9384 We don't have a candidate for that algorithm, I only mean to say that currently we cannot prove that it does not exist. Also, I should mention that the best bound is not linear, but it is $\omega(n\sqrt{\log^\star(n)})$, which is slightly better than linear. $\endgroup$ – Lieuwe Vinkhuijzen Aug 15 '17 at 14:44
  • $\begingroup$ This means that SAT can't be solved in $O(n)$ time? Other answers on stackexchange said that no bound $\omega(n)$ is known. Is this very recent result? $\endgroup$ – rus9384 Aug 15 '17 at 20:30
  • $\begingroup$ @rus9384 From (this cstheory post)[cstheory.stackexchange.com/q/1079/35749] we are redirected to "On determinism versus nondeterminism and Related Problems" by Paul et al., 1983, which shows $DTime(n)\ne NTime(n)$, and to "On Separators, Segregators and Time versus Space" by Santhanam, 2001, which shows the $n\sqrt{\log^\ast(n)}$ bound, among other things. A nondeterministic machine can solve SAT in linear time, hence. Of course I may be misinterpreting the results, which talk about sets and not about SAT, in which case I would appreciate that pointed out. $\endgroup$ – Lieuwe Vinkhuijzen Aug 16 '17 at 11:41
  • 1
    $\begingroup$ "It's the most theoretical question in computer science!" -- Citation needed. $\endgroup$ – Raphael Aug 16 '17 at 19:53
1
$\begingroup$

It wouldn't have a direct practical utility. It would "merely" be a huge mathematical discovery with a lot of implications, more interesting than (say) Fermat's Last Theorem was.

And of course, even if the proof itself doesn't provide a practical algorithm for NP problems (as opposed to a polynomial one: e.g. $O(N^{1000})$ is polynomial but useless in practice), it may well lead to a discovery of one in the future.

$\endgroup$

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.