Mixing
What happens for factoring algorithms if P=NP?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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?
factoring complexity
edited 1 hour ago
AleksanderRas
9441219
asked 1 hour ago
tyuil
293
add a comment |Â
up vote
1
down vote
favorite
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?
factoring complexity
edited 1 hour ago
AleksanderRas
9441219
asked 1 hour ago
tyuil
293
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
factoring complexity
edited 1 hour ago
AleksanderRas
9441219
asked 1 hour ago
tyuil
293
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?
factoring complexity
factoring complexity
edited 1 hour ago
AleksanderRas
9441219
asked 1 hour ago
tyuil
293
edited 1 hour ago
AleksanderRas
9441219
asked 1 hour ago
tyuil
293
edited 1 hour ago
AleksanderRas
9441219
edited 1 hour ago
AleksanderRas
9441219
edited 1 hour ago
AleksanderRas
9441219
9441219
asked 1 hour ago
tyuil
293
asked 1 hour ago
tyuil
293
asked 1 hour ago
tyuil
293
293
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
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 an algorithm to solve a NP-problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered 1 hour ago
AleksanderRas
9441219
add a comment |Â
up vote
1
down vote
No, it will not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem in $mathbbNP$-class that has a polynomial time solution that proves the famous problem; $mathbbNP=mathbbP$ or $mathbbNP neq mathbbP.$
Reduce the factorization problem into Hamiltonian Path Problem ( that is $ in mathbbNP$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the reduction step in this answer. Solve this problem in polynomial time by reducing to $x$, and transfer the solutions back to the factorization problem since the reductions are answer-preserving, so backward available.
Note: If the proof of $mathbbNP=mathbbP$ is not performed by showing an $mathbbNP$-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 $mathbbNP$-Complete problem.
answered 1 hour ago
kelalaka
2,394624
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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 an algorithm to solve a NP-problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered 1 hour ago
AleksanderRas
9441219
add a comment |Â
up vote
2
down vote
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 an algorithm to solve a NP-problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered 1 hour ago
AleksanderRas
9441219
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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 an algorithm to solve a NP-problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered 1 hour ago
AleksanderRas
9441219
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 an algorithm to solve a NP-problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.
answered 1 hour ago
AleksanderRas
9441219
edited 1 hour ago
answered 1 hour ago
AleksanderRas
9441219
answered 1 hour ago
AleksanderRas
9441219
answered 1 hour ago
AleksanderRas
9441219
9441219
add a comment |Â
add a comment |Â
up vote
1
down vote
No, it will not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem in $mathbbNP$-class that has a polynomial time solution that proves the famous problem; $mathbbNP=mathbbP$ or $mathbbNP neq mathbbP.$
Reduce the factorization problem into Hamiltonian Path Problem ( that is $ in mathbbNP$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the reduction step in this answer. Solve this problem in polynomial time by reducing to $x$, and transfer the solutions back to the factorization problem since the reductions are answer-preserving, so backward available.
Note: If the proof of $mathbbNP=mathbbP$ is not performed by showing an $mathbbNP$-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 $mathbbNP$-Complete problem.
answered 1 hour ago
kelalaka
2,394624
add a comment |Â
up vote
1
down vote
No, it will not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem in $mathbbNP$-class that has a polynomial time solution that proves the famous problem; $mathbbNP=mathbbP$ or $mathbbNP neq mathbbP.$
Reduce the factorization problem into Hamiltonian Path Problem ( that is $ in mathbbNP$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the reduction step in this answer. Solve this problem in polynomial time by reducing to $x$, and transfer the solutions back to the factorization problem since the reductions are answer-preserving, so backward available.
Note: If the proof of $mathbbNP=mathbbP$ is not performed by showing an $mathbbNP$-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 $mathbbNP$-Complete problem.
answered 1 hour ago
kelalaka
2,394624
add a comment |Â
up vote
1
down vote
up vote
1
down vote
No, it will not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem in $mathbbNP$-class that has a polynomial time solution that proves the famous problem; $mathbbNP=mathbbP$ or $mathbbNP neq mathbbP.$
Reduce the factorization problem into Hamiltonian Path Problem ( that is $ in mathbbNP$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the reduction step in this answer. Solve this problem in polynomial time by reducing to $x$, and transfer the solutions back to the factorization problem since the reductions are answer-preserving, so backward available.
Note: If the proof of $mathbbNP=mathbbP$ is not performed by showing an $mathbbNP$-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 $mathbbNP$-Complete problem.
answered 1 hour ago
kelalaka
2,394624
No, it will not give us directly a new algorithm. What immediately we can do is classical problem reduction;
Let $x$ be a problem in $mathbbNP$-class that has a polynomial time solution that proves the famous problem; $mathbbNP=mathbbP$ or $mathbbNP neq mathbbP.$
Reduce the factorization problem into Hamiltonian Path Problem ( that is $ in mathbbNP$-Complete) in the polynomial time as Adleman did in DNA computing. You can find the reduction step in this answer. Solve this problem in polynomial time by reducing to $x$, and transfer the solutions back to the factorization problem since the reductions are answer-preserving, so backward available.
Note: If the proof of $mathbbNP=mathbbP$ is not performed by showing an $mathbbNP$-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 $mathbbNP$-Complete problem.
answered 1 hour ago
kelalaka
2,394624
edited 33 mins ago
answered 1 hour ago
kelalaka
2,394624
answered 1 hour ago
kelalaka
2,394624
answered 1 hour ago
kelalaka
2,394624
2,394624
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63712%2fwhat-happens-for-factoring-algorithms-if-p-np%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
