Can a computational complexity class be redefined by using any complete (decision) problem? Let $\mathcal{C}$ be a basic complexity class (such as $\mathrm{NP}, \mathrm{PSPACE}$).
And $\mathcal{C}$ is closed under a reduction &quot;$\leq$&quot; (such as polynomial time many-one reduction &quot;$\leq_{m}^{p}$&quot;, polynomial time Turing reduction &quot;$\leq_{T}^{p}$&quot;).
Suppose that a decision problem $L \subseteq \Sigma^{*}$ is complete for $\mathcal{C}$ under reduction &quot;$\leq$&quot;.
Let $[L]^{\leq}$ denote the closure of $L$ under reduction &quot;$\leq$&quot;, which means that $[L]^{\leq}$ is a class consists all the languages that can be reduced to $L$.
$$[L]^{\leq} = \{ L' \in \Sigma^{*}| L' \leq L \}$$
Does $\mathcal{C} = [L]^{\leq}$ hold true?
Here is my proof.
Firstly, $L \in \mathcal{C}$, thus for every $L' \in [L]^{\leq}$, we have $L' \in \mathcal{C}$ which leads that $[L]^{\leq} \subseteq \mathcal{C}$.
In the other hand, since $L$ is complete, for every $L' \in \mathcal{C}$, $L' \leq L$. We conclude that $L' \in [L]^{\leq}$ which means that $\mathcal{C} \subseteq [L]^{\leq}$.
Now, I have proved that $\mathcal{C} = [L]^{\leq}$.
If this is correct, I can say that
$$[\text{SAT}]^{\leq_{m}^{p}} = [\text{3-SAT}]^{\leq_{m}^{p}} = \mathrm{NP}$$
Am I right?
If $X$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $X$.
We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.