1
$\begingroup$

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 that tries to clarify the decidability of the language (not the given complexity class), though they are related.

Also I found this question that is somewhat a "special case" where the interest was specifically for $NP$ complexity class. This raises the next question:

  1. 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. 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:

  1. 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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ This (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. $\endgroup$
    – Joshua Grochow
    Oct 24 at 0:08
  • 2
    $\begingroup$ By Rice's theorem, no nontrivial problem of the form $\{\langle M\rangle:L(M)\in\dots\}$ is decidable. $\endgroup$
    – Emil Jeřábek
    Oct 24 at 7:19
  • 2
    $\begingroup$ Oh, and by the Rice-Shapiro 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. $\endgroup$
    – Emil Jeřábek
    Oct 24 at 8:34
  • $\begingroup$ @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). $\endgroup$
    – A. G
    Oct 24 at 17:28

0

Reset to default

Your Answer

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