edited by
2,118 views
3 votes
3 votes
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
edited by

4 Answers

Best answer
7 votes
7 votes

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.

selected by
0 votes
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. 

0 votes
0 votes

Acc to me Answer Should be option (B)

Explanation :

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

–1 votes
–1 votes
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

Related questions

2 votes
2 votes
1 answer
3
iarnav asked Sep 6, 2021
449 views
Please help me understand this question. I have searched on internet, but not avail. Click this to see the question