Search code examples
algorithmtime-complexitynpnp-complete

Np class of problems


Are All problems in NP are known to be reducible to one another. I know if a problem X is in NP and any NP problem Y in NP is reducible to X then X is NP-complete. So by this assumption can we state that all NP problems are reducible to one another?


Solution

  • A decision problem C is NP-complete if:
    
    C is in NP, and
    Every problem in NP is reducible to C in polynomial time. 
    

    Source: https://en.wikipedia.org/wiki/NP-completeness

    If all NP problems are reducible to one another, it would mean that all NP problems are NP complete, which we can not say since we still can't prove whether P = NP Refer to the image below for a better understanding.

    enter image description here