Re: Noob question on complexity of emulated machines?

In article <1156356273.488308.188920@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
D. C. <enharmonix@xxxxxxxxx> wrote:
Is there a name for the class of problems that are solvable in LINEAR
time on an NTM, and does this class have the same sort of relation to
LINEAR that NP has to P, or is the NTM-LINEAR the same as LINEAR for DTM?

One has to be a little careful working with complexity classes of such low
complexity, because they're sensitive to precise definitions in a way that
classes like P aren't. For example, usually one glosses over the question
of the precise format in which the input to an algorithm is provided,
because as far as membership in P is concerned, it doesn't matter whether
you write numbers in binary or decimal, or what order you list the separate
parts in, etc. Massaging the format takes at most polynomial time and so
these issues get lost in the noise. Complicated changes in format, though,
might take more than linear time.

However, provided we take reasonable care, it makes sense to talk about
linear-time solvability on a DTM vs. a LTM. They are not known to be
equivalent, and indeed people suspect that there is an entire linear-time
hierarchy (LTH) that is analogous to the polynomial-time hierarchy. It
is not known if LTH is contained in P or vice versa. Steve Cook's notes
on bounded arithmetic and propositional proof complexity, available on his
website, give a little more information.

More to the point, is the complexity of emulating an NTM known to be NP
(or in a similar class, e.g. NPC), or is it PSPACE? It seems to me
that it should actually be /easier/ than NP, since poly-time should not
be required to emulate an NTM on another NTM, the NTM equivalent of
LINEAR would suffice. Or maybe another way, if P=NP, would DTM = NTM,
or are there more problems that NTM does better?

Savitch's theorem tells us that a DTM can simulate an NTM with only a
quadratic increase in space complexity. In general, to make your question
precise, you need to specify what kind of resource bound you care about.
With no resource bounds at all, a DTM can certainly simulate an NTM since
both kinds of machine types just compute recursive (or recursively
enumerable) functions.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Noob question on complexity of emulated machines?
    ... Is there a name for the class of problems that are solvable in LINEAR ... is the complexity of emulating an NTM known to be NP ... Or maybe another way, if P=NP, would DTM = NTM, ...
    (comp.theory)
  • Re: Wie ist Nicht-Determinismus genau definiert?
    ... Eine DTM kann alle Probleme aus NP berechnen (in NP sind ja nur ... Nur kann eine DTM manche Probleme aus NP ... DTM und NTM werden unabhängig definiert. ... TMs werden sind erstmal Automaten, die ein Wort von einem Eingabeband ...
    (de.sci.informatik.misc)
  • Re: Wie ist Nicht-Determinismus genau definiert?
    ... > Mit Zufallszahlen hat das aber eher weniger zu tun. ... dass man mit einer DTM ... > eine NTM simulieren kann. ... Next by Date: ...
    (de.sci.informatik.misc)
  • Re: Wie ist Nicht-Determinismus genau definiert?
    ... >>Mit Zufallszahlen hat das aber eher weniger zu tun. ... dass man mit einer DTM ... >>eine NTM simulieren kann. ... > Der Quantencomputer gilt als eine Realisierung einer NTM. ...
    (de.sci.informatik.misc)
  • Re: Noob question on complexity of emulated machines?
    ... w/ complexity as it applies to modern computers, ... hierarchy (LTH) that is analogous to the polynomial-time hierarchy. ... everything there is to know about computational complexity theory?" ... The idea of emulating an NTM on another NTM got me wondering about LTH, ...
    (comp.theory)