show/hide this revision's text 2 edited body

I'm not sure that it's entirely correct, but here goes. Let $f(n)$ be a proper complexity function (a.k.a. space and time constructible, etc.) and consider the class $\mathcal{C} = \bigcup_{P,Q} DTIME Q(f(P(n)))$, where $P,Q$ rangs over polynomials with natural number coefficients. Suppose $f(n) \geq n$. Then the language $L=(M,x,P,Q)$: $M$ is a deterministic Turing machine that accepts string $x$ in at most $Q(f(P(n))$ steps should be $\mathcal{C}$-complete. Indeed, verification is just a mechanical process of simulating the Turing machine (which can be done in polynomial time on the length of $M$ and $x$), and every language decided by a Turing machine $M$ in $DTIME(Q(f(P(n)))$ should reduce to $L$ based on the machine $M$. The same should hold for nondeterministic complexity classes.

I've seen something like this for $NP$ (this is how the Cook-Levin theorem is proved, if I understand correctly), and I think it should generalize, and that natural complexity classes based solely on a time constraint (which is sufficiently large) shoudl should admit complete problems.
show/hide this revision's text 1

I'm not sure that it's entirely correct, but here goes. Let $f(n)$ be a proper complexity function (a.k.a. space and time constructible, etc.) and consider the class $\mathcal{C} = \bigcup_{P,Q} DTIME Q(f(P(n)))$, where $P,Q$ rangs over polynomials with natural number coefficients. Suppose $f(n) \geq n$. Then the language $L=(M,x,P,Q)$: $M$ is a deterministic Turing machine that accepts string $x$ in at most $Q(f(P(n))$ steps should be $\mathcal{C}$-complete. Indeed, verification is just a mechanical process of simulating the Turing machine (which can be done in polynomial time on the length of $M$ and $x$), and every language decided by a Turing machine $M$ in $DTIME(Q(f(P(n)))$ should reduce to $L$ based on the machine $M$. The same should hold for nondeterministic complexity classes.

I've seen something like this for $NP$ (this is how the Cook-Levin theorem is proved, if I understand correctly), and I think it should generalize, and that natural complexity classes based solely on a time constraint (which is sufficiently large) shoudl admit complete problems.