The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

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

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

+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 :)

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.

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

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,560 answers

146,291 comments

62,306 users