If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
10
Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.).
But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered Nov 5, 2018 at 12:04
-
7$\begingroup$ I don't believe this is true, at least technically. Consider a diagonalization over all possible Turing machines, where we run the first machine for a step, then the first two machines for a step, etc. If the correct Turing machine is nr. $k$ in our ordered list of TMs, at some point we will have run enough steps to run it until it halted. $k$ will be unimaginably large, as will the number of steps wasted on Turing machines before $k$. However, this $k$ is a constant with respect to $n$, the input size, thus this diagonalization will still be polynomial time if a poly-time algorithm exists. $\endgroup$– orlpCommented Nov 5, 2018 at 14:27
-
4$\begingroup$ What @orlp describes is often known as Levin's universal search algorithm. $\endgroup$ Commented Nov 5, 2018 at 14:48
-
11$\begingroup$ The answer is correct. If it perhaps could more rigorous in language. A polynomical time algorithm to any NPC problem would lead to a polynomial algorithm for any NP problem yet polynomical does not imply practical. $\endgroup$ Commented Nov 5, 2018 at 16:00
-
6$\begingroup$ @MeirMaor Exactly: it's possible that, for example $\mathbf{P}=\mathbf{NP}$ but factorizing $n$-bit numbers takes time at least $n^{1000}$. $\endgroup$ Commented Nov 5, 2018 at 16:13
-
4$\begingroup$ @MeirMaor The OP wanted to know if knowing P = NP will give us a polynomial time factoring algorithm, not whether it'll be practical. At least that's the question OP asked. And the answer to that question is yes, not no, which is what this answer claims (as well as the other answer). I think if we're being pedantic both answers are incorrect. $\endgroup$– orlpCommented Nov 5, 2018 at 16:58
$\begingroup$
$\endgroup$
Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the algorithm solves factoring in polynomial time on all instances. However, this algorithm is utterly infeasible for real-world computation because it works by iterating over other algorithms. In a sense, it simply moves the nonconstructivity of the proof into the algorithm itself.
One thing that is interesting is that this result is somewhat specific to factoring. There does not appear to be a known algorithm that would solve SAT in polynomial time correctly, on all inputs, whose correctness proof is conditional only on P = NP. See this followup blog post by Lance Fortnow.
$\begingroup$
$\endgroup$
3
No, the proof may not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem that proves $\mathbf{NP}=\mathbf{P}$.
We can reduce the factorization problem into Hamiltonian Path Problem ( that is $ \in \mathbf{NP}$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the details of the reduction steps in this answer. So we can reduce our problem to $x$ in polynomial time, solve $x$ and transfer the solutions back to the factorization problem since the reductions are answer-preserving, i.e. backward available.
Note: If the proof of $\mathbf{NP}=\mathbf{P}$ is not performed by showing an $\mathbf{NP}$-Complete problem has a polynomial time solution the reduction will not work until one find one. But in general, if the equality is the case, we expect that one will find a polynomial time algorithm for an $\mathbf{NP}$-Complete problem.
answered Nov 5, 2018 at 12:00
-
$\begingroup$ The law of excluded middle already tells us that $\mathbf{P}=\mathbf{NP}$ or $\mathbf{P}\neq\mathbf{NP}\,$! So, presumably, $x$ is a problem that proves $\mathbf{P}=\mathbf{NP}$. $\endgroup$ Commented Nov 5, 2018 at 16:16
-
$\begingroup$ @DavidRicherby yes, exactly. The wording is wrong here? $\endgroup$– kelalakaCommented Nov 5, 2018 at 16:21
-
2$\begingroup$ Yours second paragraph talks about "[solving] the famous open problem $\mathbf{P}=\mathbf{NP}$ or $\mathbf{P}\neq\mathbf{NP}$." I'm saying that's a trivial problem and it would be better to say that $x$ proves that $\mathbf{P}=\mathbf{NP}$. $\endgroup$ Commented Nov 5, 2018 at 16:23