1
$\begingroup$

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for its own sake. Thus, the activity of applied mathematics is vitally connected with research in pure mathematics.

I wonder which problems in pure mathematics could be tackled once an algorithm solving NP-complete problems is found. The list of instances of NP-complete problems is long, but are they any other, let's say stand-alone problems in pure mathematics that could be solved?

Sure, we could get more numerical data to tighten some bounds, but that's not what I'm after...

$\endgroup$

2 Answers 2

5
$\begingroup$

All of them. It's possible to verify if a proof is valid in polynomial time, and it's possible to check if the last step of a proof is the theorem under consideration in polynomial time, so just encode "valid proof of length N" as a satisfiability problem.

N = 1
DO
IF (there is a valid proof of length N that proves theorem T) THEN return TRUE
IF (there is a valid proof of length N that proves theorem $\lnot$ T) THEN return FALSE
N = N * 2
LOOP

Unless the theorem is unprovable, which is really just another theorem to check. A tractable SAT solver would be ridiculously powerful.


I'll try to be more explicit. A proof is a string of characters. You could ask "what is the length of your proof?" and get a response "1300 characters long". In academic papers only the outlines to proofs tend to be published, but there are proofs where every single step can be checked.

Consider an algorithm $\text{ValidProof}(P, T)$ that returns true iff $P$ is a valid proof of $T$. We already know constructively how to implement $\text{ValidProof}$ in polynomial time.

If $P=NP$, then for any algorithm $Q(x)$ which runs in polynomial time, one can solve the problem "is there $x$ of length $N$ such that $Q(x)$ is true?". You can also determine what that $x$ is. That's the entire point of the $NP$ complexity class.

Since $Q(x)$ can be $\text{ValidProof}(x, T)$, $P=NP$ would allow anyone to just solve for $x$, the proof.

$\endgroup$
9
  • 1
    $\begingroup$ hmmm, but wouldn't you have to come up with a certain proof first? $\endgroup$
    – draks ...
    Feb 20, 2014 at 23:06
  • $\begingroup$ Your question doesn't make any sense to me. $\endgroup$
    – DanielV
    Feb 20, 2014 at 23:32
  • $\begingroup$ ok, so with "all of them" you mean all problems from the list, right? So can solve instances of length $N$, but this is just an "application". You was looking for more general things. For example you might some information about the number of solutions for a NP-complete problem, by that put up some asymptotics and finally get an idea how these asymptotics can be proven... $\endgroup$
    – draks ...
    Feb 20, 2014 at 23:41
  • $\begingroup$ By "all of them" I mean all (well formed) mathematical statements in the universe. Number theory, differential equations, geometry, whatever. $\endgroup$
    – DanielV
    Feb 20, 2014 at 23:59
  • 1
    $\begingroup$ Strictly speaking, the $NP$ problem is "does there exist a proof of X of length N?" and $\text{ValidProof}_T(x)$ is the corresponding deterministic algorithm that can check any witness. As far as how to implement $\text{ValidProof}$ at all, much less in in polytime, you could take an entire graduate level logic class in that. But the fact that it is possible should be obvious. It's just rule checking. $\endgroup$
    – DanielV
    Feb 23, 2014 at 14:46
3
$\begingroup$

I think it is important to note that NP-complete problems have solutions to them. An algorithm exists to solve any NP-complete problem. All NP-complete problems are NP. If one were to implement an algorithm solving an NP problem (that is not in P), then the implementation will have at least exponential running time (it will be very slow).

With that said, a proof showing that $P=NP$ will likely contain techniques that will change the landscape of pure mathematics forever, and it will likely be a proof showing that an NP-complete problem can be solved in polynomial time (which is what I think you are asking). Such a proof would change the world in ways that don't seem natural. For this reason, it is conjectured that $P\neq NP$.

I hope that helps add some context to DanielV's answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .