Is np-complete an equivalence class?

Question

So, there are multiple possible definitions of "np-complete", two of which being:

1. A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' \preceq_{p} L$

2. A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and there exists a np-complete problem $L \in \text{NP}$ such that: $L' \preceq_{p} L$

My question is, why are those two definitions equivalent, or put differently, (why) is np-complete an equivalence class?

If it is an equivalence class I can understand equivalence of the above two definitions, but I fail to see why this is the case, since the (one-to-many) poly-time reduction $\preceq_{p}$ is not symmetric... :-/

Answer 1

The second definition isn't valid, since it's self-referential. Given the first definition, the second statement is an easy theorem that follows from the first definition.

Indeed, suppose we define NP-completeness using the first definition. Let's see that the second definition is true.

$\Longrightarrow$ If $L$ is NP-complete then for all $L'$ in NP, $L'$ reduces to $L$. In particular, SAT reduces to $L$. Since SAT is NP-complete by Cook's theorem, there exists an NP-complete problem $L'$ (namely SAT) that reduces to $L$.

$\Longleftarrow$ Suppose $L$ is in NP and some NP-complete problem $L'$ reduces to $L$. We will show that every problem $M$ in NP reduces to $L$, and so $L$ is NP-complete. Given a problem $M$ in NP, since $L'$ is NP-complete, $M$ reduces to $L'$. Since $L'$ reduces to $L$, $M$ also reduces to $L$, and we're done.

The proof used two properties: (1) there exists some NP-complete problem, (2) reducibility is transitive: if $A$ reduces to $B$ and $B$ reduces to $C$ then $A$ reduces to $C$.

Finally, any two NP-complete problems reduce to each other (via the definition), and in this sense they form an equivalence class of the reduction relation.