[go: up one dir, main page]
Scribd
Upload
4K views1 page

Cook's Theorem: States That Satisfiability Is in P If and Only If P NP. Proof

Cook's theorem states that the problems of satisfiability and determining if P=NP are equivalent. It proves this by showing that if satisfiability is in P (can be solved in polynomial time), then any problem in NP (can be solved by a non-deterministic Turing machine in polynomial time) can also be solved in P, meaning P=NP. Conversely, if P=NP, then satisfiability must also be in P.

Uploaded by

Nandini Chowdary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4K views1 page

Cook's Theorem: States That Satisfiability Is in P If and Only If P NP. Proof

Cook's theorem states that the problems of satisfiability and determining if P=NP are equivalent. It proves this by showing that if satisfiability is in P (can be solved in polynomial time), then any problem in NP (can be solved by a non-deterministic Turing machine in polynomial time) can also be solved in P, meaning P=NP. Conversely, if P=NP, then satisfiability must also be in P.

Uploaded by

Nandini Chowdary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Cook's theorem: states that satisfiability is in P if and only if P = NP.

Proof:
We have already seen that satisfiability is in NP. Hence, if P = NP, then
satisfiability is in P.
It remains to be shown that if satisfiability is in P, then P = NP.
To do this, we show how to obtain from any polynomial time
nondeterministic decision algorithm A and input I a formula Q(A, I) such that Q
is satisfiable iff A has a successful termination with input I.
If the length of I is n and the time complexity of A is p(n) for some
polynomial p(), then the length of Q is O(p3 (n) log n) = O(p4 (n)).
The time needed to construct Q is also O(p3 (n) log n). A deterministic
algorithm Z to determine the outcome of A on any input I can be easily
obtained. Algorithm Z simply computes Q and then uses a deterministic
algorithm for the satisfiability problem to determine whether Q is satisfiable.
If O(q(m)) is the time needed to determine whether a formula of length
m is satisfiable, then the complexity of Z is O(p3 (n) logn + q(p3 (n) log n)).
If satisfiability is in P then q(m) is a polynomial function of m and the
complexity of Z becomes O(r(n)) for some polynomial r().
Hence, if satisfiability is in P, then for every nondeterministic algorithm A
in NP we can obtain a deterministic Z in P. So, the above construction shows
that if satisfiability is in P, then P=NP.
*****

You might also like