MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Fix a standard effective listing $(\phi_e)_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow \omega$. Say that a set $X\subseteq\omega$ is a representative for $\mathcal{C}$ if $e\in X\implies \phi_e\in\mathcal{C}$ and for all $f\in \mathcal{C}, \exists e\in X$ such that $\phi_e=f$.

There is a very simple proof that there is no computable representative for $Tot=\lbrace \phi_e: \phi_e$ is total$\rbrace$. For suppose $X=\lbrace x_0 < x_1< . . . \rbrace$ were a computable representative. Then let $f_X(i)=\phi_{x_i}(i)+1$. Since $X$ is computable, so is $f_X$; since $X$ is a representative of $Tot$, $f_X$ is total; but clearly $f_X\not=\phi_{x_i}$ for any $i$, so we have a contradiction.

However, this argument need not hold in general. Suppose $\mathcal{C}$ were a class of functions which converged sufficiently slowly. Then perhaps $f$ so defined would not converge quickly enough to be an element of $\mathcal{C}$, in which case no contradiction could be derived. For instance, suppose $\mathcal{C}$ consists of the total polynomial-time computable functions. Then if $X$ is a computable representative, the function $f_X$ is not equal to any function in $\mathcal{C}$, but it appears that $f_X$ would need more than polynomial time to be computed, so no immediate contradiction is reached. On the other hand, it still seems extremely unlikely that the set of total polynomial-time-computable functions should have a computable representative.

My questions are the following: Is there a known complexity class with a computable representative? Does the set of polynomial-time-computable total functions have a computable representative?

share|cite|improve this question
up vote 3 down vote accepted

The set of polytime computable functions does indeed have a computable representative. Note that for $f$ to be polytime computable means there exists $t$, and $n_0$ such that for all $n\ge n_0$ it takes only at most $n^t$ time steps to compute $f(n)$. Now dovetail over all indices $e\in\omega$ and all $t$ and $n_0$; if $\phi_e(n)$ has not halted by time $n^t$ just set the output to say $0$, to make a total function.

share|cite|improve this answer
Oh, of course. If I recall correctly, this method also works to provide an explicit polynomial-time algorithm for SAT under the assumption P=NP. Thanks! – Noah Schweber May 5 '12 at 7:31
Hadn't thought of that but that makes sense too... because the "right" $\phi_{e_0}$ is visited polynomially (quadratically) often even if you don't know which $e=e_0$... – Bjørn Kjos-Hanssen May 5 '12 at 7:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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