Search code examples
algorithmcomputer-sciencetheorynp-completenp

Which of these languages is NP-complete?

I was searching the difference between NP and NP-complete problems. I came upon this great answer in StackOverflow by Jason. About NP-complete problems, he said

An NP problem X for which it is possible to reduce any other NP problem Y to X in polynomial time. Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X if there is a polynomial time algorithm f to transform instances x of X to instances y = f(x) of Y in polynomial time with the property that the answer to x is yes if and only if the answer to f(x) is yes.

My question is: which one is the NP-complete problem, X or Y?

Solution

  • The NP-complete language is X. The idea is that you can start with an arbitrary NP language Y and, in polynomial time, reduce it to X.

    Formally, the definition of NP-completeness is as follows: A language X is called NP-complete iff

    1. X ∈ NP. That is, X can't be "harder" than the "hardest NP problem," since X is itself a member of NP.
    2. For any Y ∈ NP, there is a polynomial-time mapping reduction from Y to X. That is, X is "at least as hard" as any problem in NP, since a polynomial-time algorithm for X gives a polynomial-time algorithm for Y. The fact that Y is polynomial-time reducible to X is sometimes denoted Y ≤p X, by the way.

    That said, it is possible to reduce any NP-complete language to any other NP-complete language, so if Y polynomial-time reduces to X and X is NP-complete, it is possible (but not necessary) for Y to be NP-complete. However, it is known that if Y reduces in polynomial time to X, that Y has to be an element of NP.

    Hope this helps!