A problem in NP is NP-complete if
- it can be reduced to the 3-SAT problem in polynomial time
- the 3-SAT problem can be reduced to it in polynomial time
- it can be reduced to any other problem in NP in polynomial time
- some problem in NP can be reduced to it in polynomial time