3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ What are $\leq^p_m$ and $\leq^p_T$? $\endgroup$ – Pål GD Nov 18 '20 at 10:54
  • $\begingroup$ The answer depends on the complexity class. Some complexity classes are actually defined this way, a notable example being LogCFL. $\endgroup$ – Yuval Filmus Nov 18 '20 at 11:28
  • $\begingroup$ @PålGD They are polynomial time many-one reduction and polynomial time Turing reduction. $\endgroup$ – TeamBright Nov 18 '20 at 11:49
  • $\begingroup$ @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}$ $\endgroup$ – TeamBright Nov 18 '20 at 11:54
  • $\begingroup$ @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. $\endgroup$ – Discrete lizard Nov 22 '20 at 10:20
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$ $\endgroup$ – TeamBright Nov 18 '20 at 13:35
  • $\begingroup$ You can say it if you can prove it using your favorite definition of NP. $\endgroup$ – Yuval Filmus Nov 18 '20 at 15:00
  • $\begingroup$ 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}$. $\endgroup$ – TeamBright Nov 19 '20 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.