The Gateway to Computer Science Excellence
+3 votes
828 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
in Theory of Computation by
edited by | 828 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.

by
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. 

by
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

by
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
by
+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
0

 SIR are these p and np problems still in syllabus ? 

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
52,345 questions
60,497 answers
201,865 comments
95,320 users