Mixing
P=NP giving a deterministic algorithm for SAT
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $phi$.
OUTPUT: A satisfying assignment of $phi$ if $phi$ is satisfiable. If $phi$ is unsatisfiable, return $false$.
My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?
complexity-theory time-complexity satisfiability complexity-classes
edited Sep 2 at 21:25
David Richerby
61.4k1594179
asked Sep 2 at 20:50
Mr. E
204
add a comment |Â
up vote
1
down vote
favorite
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $phi$.
OUTPUT: A satisfying assignment of $phi$ if $phi$ is satisfiable. If $phi$ is unsatisfiable, return $false$.
My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?
complexity-theory time-complexity satisfiability complexity-classes
edited Sep 2 at 21:25
David Richerby
61.4k1594179
asked Sep 2 at 20:50
Mr. E
204
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
2
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $phi$.
OUTPUT: A satisfying assignment of $phi$ if $phi$ is satisfiable. If $phi$ is unsatisfiable, return $false$.
My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?
complexity-theory time-complexity satisfiability complexity-classes
edited Sep 2 at 21:25
David Richerby
61.4k1594179
asked Sep 2 at 20:50
Mr. E
204
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $phi$.
OUTPUT: A satisfying assignment of $phi$ if $phi$ is satisfiable. If $phi$ is unsatisfiable, return $false$.
My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?
complexity-theory time-complexity satisfiability complexity-classes
edited Sep 2 at 21:25
David Richerby
61.4k1594179
asked Sep 2 at 20:50
Mr. E
204
edited Sep 2 at 21:25
David Richerby
61.4k1594179
edited Sep 2 at 21:25
David Richerby
61.4k1594179
edited Sep 2 at 21:25
David Richerby
61.4k1594179
61.4k1594179
asked Sep 2 at 20:50
Mr. E
204
asked Sep 2 at 20:50
Mr. E
204
asked Sep 2 at 20:50
Mr. E
204
204
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
2
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09
add a comment |Â
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
2
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
2
2
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
I like the way you think, but there's a gap in your attempt.
$mathrmP$ and $mathrmNP$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $mathrmNP$, so the assumption that $mathrmP=mathrmNP$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
answered Sep 2 at 21:24
David Richerby
61.4k1594179
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
I like the way you think, but there's a gap in your attempt.
$mathrmP$ and $mathrmNP$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $mathrmNP$, so the assumption that $mathrmP=mathrmNP$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
answered Sep 2 at 21:24
David Richerby
61.4k1594179
add a comment |Â
up vote
5
down vote
accepted
I like the way you think, but there's a gap in your attempt.
$mathrmP$ and $mathrmNP$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $mathrmNP$, so the assumption that $mathrmP=mathrmNP$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
answered Sep 2 at 21:24
David Richerby
61.4k1594179
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
I like the way you think, but there's a gap in your attempt.
$mathrmP$ and $mathrmNP$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $mathrmNP$, so the assumption that $mathrmP=mathrmNP$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
answered Sep 2 at 21:24
David Richerby
61.4k1594179
I like the way you think, but there's a gap in your attempt.
$mathrmP$ and $mathrmNP$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $mathrmNP$, so the assumption that $mathrmP=mathrmNP$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.
answered Sep 2 at 21:24
David Richerby
61.4k1594179
answered Sep 2 at 21:24
David Richerby
61.4k1594179
answered Sep 2 at 21:24
David Richerby
61.4k1594179
answered Sep 2 at 21:24
David Richerby
61.4k1594179
61.4k1594179
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%2fcs.stackexchange.com%2fquestions%2f96909%2fp-np-giving-a-deterministic-algorithm-for-sat%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
> If it satisfies Õ, return it. What do you do when it doesn't satisfy?
– Curtis F
Sep 2 at 23:18
2
You have to use self-reducibility of SAT.
– Yuval Filmus
Sep 3 at 4:43
@Solomonoff'sSecret The proposal is to use nondeterminism to select the satisfying assignment, not randomness. NP has nothing whatsoever to do with randomness.
– David Richerby
Sep 3 at 11:07
@CurtisF The asker is proposing an algorithm that uses nondeterminism, and then trying to use P=NP to conclude that there is an equivalent deterministic one.
– David Richerby
Sep 3 at 11:09