P vs NP Determine whether the following statements are true or not. You must pro

Question

P vs NP

Determine whether the following statements are true or not. You must provide a convincing and short argument.

• If one can find a polynomial time algorithm that determines SAT, then P = NP. • Dr. K constructs a new neural system that can be used for computation.

•Dr. K constructs a polynomial time algorithm to determine SAT under the neural system, and further he argues that the neural system can simulate Turing machines efficiently (i.e. with polynomial overhead). Now Dr. K claims that P = NP. Is he correct or not? Why?

Explanation / Answer

1. Problem X is at least as hard as problem Y To prove such a statement, we reduce problem Y to problem X.

The big question: P= NP?

We know P NP.

So the question is:

Is there some problem in NP that is not in P.

there is an polynomial time algorithm for X and for Y

If we could solve X in polynomial time, then we’d be able to solve Y in polynomial time, contradicting the assumption.

We say X is NP-complete if:

X NP • for all Y NP, Y P X. If these hold, then X can be used to solve every problem in NP.

If P = NP, then X can be solved in polytime.

Suppose X is solvable in polytime, and let Y be any problem in NP.

We can solve Y in polynomial time: reduce it to X.

Therefore, every problem in NP has a polytime algorithm and P = NP

2. he is correct by the same way if we know there polytime algorithm and X can be solved in polytime.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.