The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
704 views
To say P=NP which one of the following is sufficient? (All reductions in polynomial time)

A. Reduction of a NP problem to a P problem

B. Reduction of a NP-complete problem to a P problem

C. Reduction of a P problem to an NP problem

D. Reduction of a P problem to an NP-complete problem
asked in Theory of Computation by Veteran (370k points)
edited by | 704 views

4 Answers

+7 votes
Best answer

Option B is the most correct answer. (To know why it is not THE correct answer read the tail section of this answer)

The reasons are as follows.

A problem p in NP is NP-complete if every other problem in NP can be transformed into p in polynomial time.  They have another property that given a problem in NP and a solution, we can verify deterministically in polynomial time that the solution is indeed a valid solution or not.

P represents the class of all problems whose solution can be found in polynomial time.

Reduction of an NPC problem to a P problem would imply 2 things:
1) All problems in NP are reducible to this problem in P because all NP problems are reducible to NPC problems.
2) We can solve the NPC problem in polynomial time as well because we ca solve ther problem in P in polynomial time by definition of class P.

This implies that all problems in NP are solvable in polynomial time.  (1)

A problem which can be solved in polynoimial time is essential in P

Which implies P=NP  (QED)

Tail

The statement of option B is incomplete. It is not enought to say that that reduction of NPC problem to a problem in P, but the reduction should be polynomial reduction or karp reduction.
The statement which implies P=NP would be There exist a polynomial time reduction of a problem in NPC to a problem in P. The answer is partially correct because when we say reduction, we usually mean polynomial time reduction, but neverthless it doesnt hurt to be precise.

answered by (173 points)
selected by
+1
(All reductions in polynomial time) is mentioned in the question :)
+1
My bad..didn't notice that....
+2
Np. Anyway good to highlight the "polynomial time" :)

Reduction of an NPC problem to a P problem (in polynomial time) would imply 2 things:

1) All problems in NP are reducible to this problem in P because all NP problems are reducible to NPC problems.
2) We can solve the NPC problem in polynomial time as well, because we can solve the problem in P in polynomial time by definition of class P.

This implies that all problems in NP are solvable in polynomial time, or NP = P

Thats the exact answer :)
0 votes

B. might be the answer.

As NPC are the "hardest" in NP. So Reduction of a NP-complete problem to a P problem will be sufficient. 

answered by Active (3.5k points)
0
Thats a very good guess and based on the choice it is correct. But had the choice contained "None of these" it wouldn't work :)
The answer is there in the definition itself of NPC..
0 votes

Acc to me Answer Should be option (B)

Explanation :

P=NP is true only when NP-complete can be reducible to P

answered by (421 points)
0
That's correct. But why?
0
if any mpc problem reduced to p..then p=np==all tuff problem which are in np redusable to p...everthing become easy..
–1 vote
i think option A is abosolute correct and i have some doubt on option B, because NPC represents hard problems soving in non deterministic time is there anything we can able to say NP=NPC
answered by (399 points)
+1
Actually many NP problems have been reduced to P problem (like Primality testing) and still P=NP? is an unsolved problem. Only if we can reduce all NP problems to P, we can say P=NP. And that is the main reason why NP-Complete class is formed. You can read the definition of NP-Complete once more and everything will be clear.
0
ok

Related questions

+5 votes
1 answer
4


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,468 questions
49,921 answers
165,495 comments
65,899 users