The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing machines, and for each Turing machine report for each $k\in\mathbb{N}$ the language generated by stopping each computation after $n^k$ steps, and reject if the input hasn't been accepted before reaching this step limit.

This only gives a computable enumeration of Turing machines. However, it seems that the corresponding languages will be decidable, because the enumeration includes an explicit time bound for each of its Turing machines. Hence this should give an computable enumeration of $\mathsf{NP}$.

Question: Is the conclusion from this reasoning correct, i.e. is $\mathsf{NP}$ computably enumerable? One issue that I have is that even for decidable languages, we can only (computably) decide whether two given languages are different, but not whether they are equal. Hence it seems that we can't avoid to report the same language more than once. The deeper issue here is that being computably enumerable is a property of subsets of the natural numbers, but the complexity class $\mathsf{NP}$ doesn't seem to correspond to a subset of the natural numbers in any canonical way.


Your trick is actually used in structural complexity theory, say in these proofs of Ladner's theorem. In order to enumerate all languages in NP, you instead enumerate all timed Turing machines $\langle M, k \rangle$, which automatically stop and (say) reject after $kn^k$ steps. Another variant is that a time polytime machine is a pair $\langle M,k \rangle$, where $M$ is guaranteed to stop within $kn^k$ steps. You can't enumerate timed polytime machines under this definition, for the same reason as in Raphael's answer.

| cite | improve this answer | |

I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable.

First, let's fix what that means. I assume you are asking if

$\qquad\displaystyle \mathrm{TM}_{\mathsf{NP}} = \{ \langle M \rangle \mid L(M) \in \mathsf{NP} \}$

is recursively enumerable. It's not by the extended Rice theorem since the Turing machine $M$ that never halts is an NP-acceptor for the empty language, so $M \in \mathrm{TM}_{\mathsf{NP}}$, but there certainly are $M'$ with $M \subsetneq M'$ and $M' \notin \mathrm{TM}_{\mathsf{NP}}$.

Intuitively, no algorithm can separate $M$ (which has infinitely many equivalent brethren, by the way) from any other Turing machine in finite time, and thus can never enumerate them.

| cite | improve this answer | |
  • $\begingroup$ If I want to enumerate $\mathsf{NP}$, then I want to enumerate the decision problems in it, not the Turing machines deciding these decision problems. Now wikipedia say: "A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes." So I can represent these decision problems as languages. I have a surjective map of $\mathbb{N}$ to this set, but no computable bijective map. $\endgroup$ – Thomas Klimpel May 2 '14 at 22:16
  • $\begingroup$ @ThomasKlimpel You need to fix some finite representation of languages so they can be inputs/outputs of a (Turing) machine. If you use some mapping that is not even computable, clearly nothing can be done. In any case, if you don't want answerers to make up representations, you should formally specify the problem in your question. ;) $\endgroup$ – Raphael May 2 '14 at 22:21
  • $\begingroup$ The issue is not the representation, but the equality predicate. The languages from $\mathsf{NP}$ are decidable, hence they can be represented by suitable Turing machines. But equality is defined by extensional equality of the corresponding languages, not by equality of the Turing machines. My question didn't explicitly specify that I'm interested in computable bijective mappings between $\mathbb{N}$ and the set of languages in $\mathsf{NP}$, because I was actually thinking in terms of "computably enumerable", and making sense of this for arbitrary sets (or not) is part of the question. $\endgroup$ – Thomas Klimpel May 2 '14 at 22:30
  • 1
    $\begingroup$ "The issue is not the representation, but the equality predicate." -- yes, but you need a representation for enumeration. Recursive enumerability is equivalent to semi-decidability -- what's your input for the semi-decider you'd like to have? $\endgroup$ – Raphael May 3 '14 at 9:24
  • $\begingroup$ Thanks, now I see how to make sense of "computably enumerable" for arbitrary sets. The restrictions regarding representation have to be specified as part of the question. If I just ask, whether there exists "a reasonable" representation for which $\mathsf{NP}$ is c.e., then the answer is yes. If I ask about whether it is c.e. for "almost all reasonable" representations, then the answer is no. The extended Rice theorem tells me that for "any reasonable" representation, if $\mathsf{NP}$ turn out to be c.e. relative to it, then the corresponding decision procedure will be "almost trivial". $\endgroup$ – Thomas Klimpel May 3 '14 at 10:56

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.