Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
1  
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 S 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
add comment

Your Answer

 
discard

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.