Answer to Question 4-2

What is the definition of an NP-complete problem? (What properties does a problem A need to have in order to be NP-complete?)

Answer. A is NP-complete if A is a set where

1. A is in NP.
2. For every set X in NP, X ≤_p A.