patternMinor
Can a computational complexity class be redefined by using any complete (decision) problem?
Viewed 0 times
problemcananycomputationalcompletedecisionusingredefinedclasscomplexity
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?
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?
Solution
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.
We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.
Context
StackExchange Computer Science Q#132380, answer score: 3
Revisions (0)
No revisions yet.