<p>This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to the nature of the question).</p>
<p>So my original question was: <strong>&quot;Given a (fixed, say <span class="math-container">$NP$</span>) Complexity Class <span class="math-container">$\mathcal{C}$</span> and arbitrary decision problem <span class="math-container">$P$</span>, is there a Turing machine <span class="math-container">$M_{CC}$</span> for the fixed complexity class that decides the question &quot;Does <span class="math-container">$P\in\mathcal{C}$</span>?&quot;&quot;</strong>.</p>
<ol>
<li>My first step was to note that a given decision problem <span class="math-container">$P$</span> can be seen/encoded as a language <span class="math-container">$\mathcal{L}$</span> (using the logical predicates etc) (please confirm). Here I'm a bit unsure whether we make the topic slightly more complex or it' still equivalent.</li>
</ol>
<p>Then there is a similar <a href="https://cstheory.stackexchange.com/questions/45880/is-the-decidability-of-a-language-decidable">question</a> that tries to clarify the decidability of the language (not the given complexity class), though they are related.</p>
<p>Also I found <a href="https://cs.stackexchange.com/questions/24326/is-the-complexity-class-np-computably-enumerable">this</a> question that is somewhat a &quot;special case&quot; where the interest was specifically for <span class="math-container">$NP$</span> complexity class. This raises the next question:</p>
<ol start="2">
<li>a) Does my question/problem can be restated as &quot;Is <span class="math-container">$\{P|P\in\mathcal{C}\}$</span> recursively enumerable?&quot;. b) Or, alternatively, as &quot;Is <span class="math-container">$\{\langle M\rangle|L(M)\in\mathcal{C}\}$</span> recursively enumerable?&quot;.</li>
</ol>
<p>And the last related question is <a href="https://cs.stackexchange.com/questions/113349/what-is-the-complexity-class-of-deciding-whether-a-problem-is-in-np-is-it-decid">this</a>. Here it is also about the <span class="math-container">$NP$</span> complexity class and there is an answer which shows undecidability of the problem in question. But the reduction mechanism was unclear as well as some statements, so it brings to the final question:</p>
<ol start="3">
<li>Assuming my question can be asked as in 2b) about <span class="math-container">$\{\langle M\rangle|L(M)\in\mathcal{C}\}$</span>, how can I build a reduction mechanism from a halting problem (showing the equivalence of the mapping as well) to show that the set is not R.E./problem is undecidable?</li>
</ol>
<p>Many thanks in advance.</p>

CC BY-SA 4.0
2023-10-24T00:08:56.260Z
This (https://cstheory.stackexchange.com/a/162/129) is very closely related, and provides an answer to the OQ above. tl;dr: No, it's not computable. In fact, the set of TMs such that they decide a language in P is $\Sigma^0_3$-complete. References in the previous link, where you can see techniques that answer your Q3.
Joshua Grochow
CC BY-SA 4.0
2023-10-24T07:19:35.653Z
By Rice's theorem, no nontrivial problem of the form $\{\langle M\rangle:L(M)\in\dots\}$ is decidable.
Emil Jeřábek
CC BY-SA 4.0
2023-10-24T08:34:38.643Z
Oh, and by the [Rice-Shapiro theorem](https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem), $\{\langle M\rangle:L(M)\in\dots\}$ is recursively enumerable only if it has the form $\{\langle M\rangle:\exists F\in A\:F\subseteq L(M)\}$, where $A$ is a recursively enumerable set of (encodings of) finite sets.
Emil Jeřábek
CC BY-SA 4.0
2023-10-24T17:28:39.553Z
@EmilJeřábek, thanks for the last comment, that's worth knowing. For the former, I was more interested in the equivalences between the definitions and formulations I gave there (1-2a,2b).
A. G
<cc.complexity-theory><complexity-classes><computability><turing-machines><decidability>
Decidability of the complexity of decision problems
A. G
# Decidability of the complexity of decision problems

(Asked by: username_0 on 2023-10-23)

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to the nature of the question).

So my original question was: **"Given a (fixed, say $NP$) Complexity Class $\mathcal{C}$ and arbitrary decision problem $P$, is there a Turing machine $M\_{CC}$ for the fixed complexity class that decides the question "Does $P\in\mathcal{C}$?""**.

1. My first step was to note that a given decision problem $P$ can be seen/encoded as a language $\mathcal{L}$ (using the logical predicates etc) (please confirm). Here I'm a bit unsure whether we make the topic slightly more complex or it' still equivalent.

Then there is a similar [question](https://cstheory.stackexchange.com/questions/45880/is-the-decidability-of-a-language-decidable) that tries to clarify the decidability of the language (not the given complexity class), though they are related.

Also I found [this](https://cs.stackexchange.com/questions/24326/is-the-complexity-class-np-computably-enumerable) question that is somewhat a "special case" where the interest was specifically for $NP$ complexity class. This raises the next question:

2. a) Does my question/problem can be restated as "Is $\{P|P\in\mathcal{C}\}$ recursively enumerable?". b) Or, alternatively, as "Is $\{\langle M\rangle|L(M)\in\mathcal{C}\}$ recursively enumerable?".

And the last related question is [this](https://cs.stackexchange.com/questions/113349/what-is-the-complexity-class-of-deciding-whether-a-problem-is-in-np-is-it-decid). Here it is also about the $NP$ complexity class and there is an answer which shows undecidability of the problem in question. But the reduction mechanism was unclear as well as some statements, so it brings to the final question:

3. Assuming my question can be asked as in 2b) about $\{\langle M\rangle|L(M)\in\mathcal{C}\}$, how can I build a reduction mechanism from a halting problem (showing the equivalence of the mapping as well) to show that the set is not R.E./problem is undecidable?

Many thanks in advance.

**Tags:** cc.complexity-theory, complexity-classes, computability, turing-machines, decidability
> **Comments:**
> **username_1**: This (https://cstheory.stackexchange.com/a/162/129) is very closely related, and provides an answer to the OQ above. tl;dr: No, it's not computable. In fact, the set of TMs such that they decide a language in P is $\Sigma^0_3$-complete. References in the previous link, where you can see techniques that answer your Q3.  
> **username_2**: By Rice's theorem, no nontrivial problem of the form $\{\langle M\rangle:L(M)\in\dots\}$ is decidable.  
> **username_2**: Oh, and by the [Rice-Shapiro theorem](https://en.wikipedia.org/wiki/Rice%E2%80%93Shapiro_theorem), $\{\langle M\rangle:L(M)\in\dots\}$ is recursively enumerable only if it has the form $\{\langle M\rangle:\exists F\in A\:F\subseteq L(M)\}$, where $A$ is a recursively enumerable set of (encodings of) finite sets.  
> **username_0**: @EmilJeřábek, thanks for the last comment, that's worth knowing. For the former, I was more interested in the equivalences between the definitions and formulations I gave there (1-2a,2b).  

---

## 0 answers

