<p>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.</p>

<p>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. </p>

<p>Furthermore, there <em>cannot</em> 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.</p>

<p>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 <em>deterministic</em> 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.</p>

CC BY-SA 4.0
2020-06-23T21:42:47.870Z
cs.stackexchange.com/questions/127565/… check out this Q, if you are interested. When you say " itself is not in " do you know of any  that is in  ?
DeeDee
CC BY-SA 3.0
2013-05-08T17:49:37.677Z
2013-05-08T17:49:37.677Z
Joshua Grochow
<p>I'm trying to get straight in my mind the relation between <em>complete problems</em> and <em>universal simulator machines</em>.  Some notions of computability have universal machines (Turing-computability) and some don't (FDAs).   </p>

<p>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?  </p>

<p>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?</p>

CC BY-SA 3.0
2013-04-30T13:43:17.267Z
Welcome to cstheory Prof. Forster. Are you asking if the notion of completeness and universal simulator for a class are equivalent?
Kaveh
CC BY-SA 3.0
2013-04-30T13:51:29.853Z
That in particular yes, and a bit more besides.
Thomas Forster
CC BY-SA 3.0
2013-04-30T13:51:51.317Z
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.
Kaveh
CC BY-SA 3.0
2013-04-30T21:19:04.677Z
Here is one related question that I found: [Semantic vs. Syntactic Complexity Classes](http://cstheory.stackexchange.com/q/1233). 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?](http://cstheory.stackexchange.com/q/761/)
Kaveh
CC BY-SA 3.0
2013-05-01T12:21:14.110Z
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.
Thomas Forster
CC BY-SA 3.0
2013-05-02T02:12:17.957Z
The issue is: complete w.r.t. what kind of reductions? The weakest reduction that is usually considered is $\mathsf{AC^0}$ I think. $\mathsf{Reg}$ and $\mathsf{AC^0}$ are not insider each other. In short if we pick a class of reductions it should be easy to say that there is no complete problem for $\mathsf{DSpace}(o(\lg\lg n))$ w.r.t. to those reduction (either too much or too little). ps: $\mathsf{DLogTime}$ is also used but only for stating uniformity and the things are generally not very robust below quadratic time, specially for single-tape Turing machines.
Kaveh
CC BY-SA 3.0
2013-05-03T13:48:38.073Z
Thanks!  It's beginning to look as if there isn't really anything straightforward and illuminating one can say to the students....  You have also shed some light on something that had been bothering me.. namely why in degree-theory one uses Turing reducibility but in finite complexity theory one uses many-one reducibility.  It's a %£#@! minefield
Thomas Forster
<cc.complexity-theory><computability><automata-theory><universal-computation>
Complete problems and universal simulator machines
Thomas Forster
# Complete problems and universal simulator machines

(Asked by: username_0 on 2013-04-30)

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?

**Tags:** cc.complexity-theory, computability, automata-theory, universal-computation

> **Comments:**
> **username_1**: Welcome to cstheory Prof. Forster. Are you asking if the notion of completeness and universal simulator for a class are equivalent?  
> **username_0**: That in particular yes, and a bit more besides.  
> **username_1**: 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.  
> **username_1**: Here is one related question that I found: [Semantic vs. Syntactic Complexity Classes](http://cstheory.stackexchange.com/q/1233). 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?](http://cstheory.stackexchange.com/q/761/)  
> **username_0**: 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.  
> **username_1**: The issue is: complete w.r.t. what kind of reductions? The weakest reduction that is usually considered is $\mathsf{AC^0}$ I think. $\mathsf{Reg}$ and $\mathsf{AC^0}$ are not insider each other. In short if we pick a class of reductions it should be easy to say that there is no complete problem for $\mathsf{DSpace}(o(\lg\lg n))$ w.r.t. to those reduction (either too much or too little). ps: $\mathsf{DLogTime}$ is also used but only for stating uniformity and the things are generally not very robust below quadratic time, specially for single-tape Turing machines.  
> **username_0**: Thanks!  It's beginning to look as if there isn't really anything straightforward and illuminating one can say to the students....  You have also shed some light on something that had been bothering me.. namely why in degree-theory one uses Turing reducibility but in finite complexity theory one uses many-one reducibility.  It's a %£#@! minefield  

---

## 1 answers

### Answer by username_2 on 2013-05-08. Score: 4

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.

> **Comments:**
> **username_3**: cs.stackexchange.com/questions/127565/… check out this Q, if you are interested. When you say " itself is not in " do you know of any  that is in  ?  

---

