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$ Commented Nov 18, 2020 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$ Commented Nov 18, 2020 at 11:28
  • $\begingroup$ @PålGD They are polynomial time many-one reduction and polynomial time Turing reduction. $\endgroup$
    – Blanco
    Commented Nov 18, 2020 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$
    – Blanco
    Commented Nov 18, 2020 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
    Commented Nov 22, 2020 at 10:20

1 Answer 1

3
$\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$
    – Blanco
    Commented Nov 18, 2020 at 13:35
  • $\begingroup$ You can say it if you can prove it using your favorite definition of NP. $\endgroup$ Commented Nov 18, 2020 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$
    – Blanco
    Commented Nov 19, 2020 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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