I'm trying to get straight in my mind the relation between complete problems and universal simulator machines. Some notions of computability have universal machines (Turing-computability) and some don't (FDAs).

When we say that there are $\mathsf{NP}$-complete problems (to take an example) is this the same as saying that a polynomially hampered universal Turing machine is universal for the notion of polytime-computability?

My colleague Ashley Montanaro here (who kindly told me about this site) told me once that the class of $\mathsf{DSPACE}(o(\log\log n))$ problems is the same as the class of regular languages. Does this mean that there is no universal machine for the $\mathsf{DSPACE}(o(\log\log n))$ problems?

  • $\begingroup$ Welcome to cstheory Prof. Forster. Are you asking if the notion of completeness and universal simulator for a class are equivalent? $\endgroup$ – Kaveh Apr 30 '13 at 13:43
  • $\begingroup$ That in particular yes, and a bit more besides. $\endgroup$ – Thomas Forster Apr 30 '13 at 13:51
  • $\begingroup$ If a class has a nice universal simulator then it is often possible to define a complete problem for the class using it. However I think completeness is more general. ps: so if I understand correctly you are looking for (natural) examples of classes which have one but not the other? If I remember correctly we had a similar question sometime ago. $\endgroup$ – Kaveh Apr 30 '13 at 13:51
  • 1
    $\begingroup$ Here is one related question that I found: Semantic vs. Syntactic Complexity Classes. A class having a universal simulator and being a syntactic complexity class are closely related. You may also want to check Do all complexity classes have a leaf language characterization? $\endgroup$ – Kaveh Apr 30 '13 at 21:19
  • 1
    $\begingroup$ Thanks!what i am trying to do is find something to say to my 4th years. One wants to say that there is a univ Turing machine but no univ FDA; one also wants to say something about complete problems so it would be nice to say something about the connection between these two ideas. I have taken on board what you have said about how this might be complex. However i would still like to get straight if poss whether or not there is a complete 𝖣𝖲𝖯𝖠𝖢𝖤(o(loglogn)) problem. That would tie in nicely with the fact that every 𝖣𝖲𝖯𝖠𝖢𝖤(o(loglogn)) language is regular and that there is no univ FDA. $\endgroup$ – Thomas Forster May 1 '13 at 12:21

There is a universal simulator for $\mathsf{DSPACE}(o(\log \log n)) = \mathsf{DSPACE}(O(1))=\mathsf{REG}$. Namely, $U_{REG}(p,x)$ treats the first input $p$ as the description of a DFA, and then runs that DFA on input $x$. The universal simulator, however, is not itself in $\mathsf{DSPACE}(o(\log \log n))$---the $U_{REG}$ I just described uses space essentially $O(p)$---so I don't know about complete languages in this case.

More generally, complete problems and universal simulators are related, but not equivalent. For one, a universal simulator for a class $\mathcal{C}$ need not be (and in general won't be) in the class $\mathcal{C}$ itself, as in the above example. Your example of "polynomially-hampered universal TMs" for $\mathsf{P}$ exhibits this distinction even better: let $M_1, M_2, \dotsc$ be an enumeration of poly-time TMs, where $M_i$ is hampered to use time at most, say, $n^i + i$. Then let $U(i,x) = M_i(x)$. $U$ is a universal simulator for $\mathsf{P}$, but there is no single polynomial that bounds the runtime of $U$, so $U$ itself is not in $\mathsf{P}$ and hence not complete.

Furthermore, there cannot be a single polynomial that bounds the runtime of a universal simulator for $\mathsf{P}$: if the universal simulator ran in time $n^k$, it would never be able to decide a language which required more time, say, $n^{k+1}$. We know that such languages exist by the Time Hierarchy Theorem.

However, the other direction usually holds. That is, if a class has a complete language under essentially any of the natural types of reductions, then it has a universal simulator. As an example, consider $\mathsf{NP}$ and its standard complete language SAT. Then we construct a universal machine for $\mathsf{NP}$ as follows (we knew how to do this for $\mathsf{NP}$ already using polynomially-hampered nondeterministic machines, but you'll see how this construction generalizes to any class with a complete language). $U(i,x) = SAT(M_i(x))$ where $M_i$ is the $i$-th poly-time deterministic TM, as above. Here we are using the $M_i$ to list out the possible reductions to the complete language, rather than the deciders of languages themselves.


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.