# 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 "$$\leq$$" (such as polynomial time many-one reduction "$$\leq_{m}^{p}$$", polynomial time Turing reduction "$$\leq_{T}^{p}$$").

Suppose that a decision problem $$L \subseteq \Sigma^{*}$$ is complete for $$\mathcal{C}$$ under reduction "$$\leq$$". Let $$[L]^{\leq}$$ denote the closure of $$L$$ under reduction "$$\leq$$", 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?

• What are $\leq^p_m$ and $\leq^p_T$? Commented Nov 18, 2020 at 10:54
• The answer depends on the complexity class. Some complexity classes are actually defined this way, a notable example being LogCFL. Commented Nov 18, 2020 at 11:28
• @PålGD They are polynomial time many-one reduction and polynomial time Turing reduction. Commented Nov 18, 2020 at 11:49
• @YuvalFilmus Yes, even if the original definition does not say in this way, I want to know whether they are equilent. E.g. $[\text{SAT}]^{\leq_{m}^{p}} = [\text{SAT}]^{\leq_{T}^{p}} = [\text{3-SAT}]^{\leq_{T}^{p}} = \mathrm{NP}$ Commented Nov 18, 2020 at 11:54
• @TeamBright Please do not delete your question after you have received useful replies. We want the questions and answers to not just help you, but also others who have similar questions. Additionally, others may find it easier to answer your questions that are similar to this one if they know you've asked something similar earlier. Commented Nov 22, 2020 at 10:20

If $$X$$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $$X$$.
• Can I say: If $X$ is any $\mathrm{NP}$-complete decision problem, then $\mathrm{NP}$ consists and only consists of all decision problems which are polytime many-one reducible to $X$ Commented Nov 18, 2020 at 13:35
• That's easy, I think. Since $\mathrm{NP}$ is closed under the polytime many-one reduction, every decision problem that is reducible to $X$ is in $\mathrm{NP}$. Commented Nov 19, 2020 at 2:00