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.

| cite | improve this answer | |

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.