Re: Noob question on complexity of emulated machines?

tchow@xxxxxxxxxxxxx wrote:
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.

Thanks. That makes sense. I'm still learning so I'm mostly concerned
w/ complexity as it applies to modern computers, but I think I might
try writing my own UTM simulator to see how these effect different
kinds of machines and handle different kinds of languages. Might as
well see it first hand.

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.

Wow... I'll have to check out Cook's website and the LTH, but I can
almost guarantee I won't understand yet. It's safe for a math major
(and ex-programmer) to take computational complexity and maybe some
comp theory, right?

Savitch's theorem tells us that a DTM can simulate an NTM with only a
quadratic increase in space complexity.

Thanks, I'll look into Savitch's theorem, that sounds like what I'm
looking for, esp. if he has answers about time complexity too.

In general, to make your question
precise, you need to specify what kind of resource bound you care about.

Well, technically space, because posting "Can somebody please teach me
everything there is to know about computational complexity theory?" to
Usenet could result in more data than I could process... :)

Seriously, though, I'm still a noob, so I'm just trying to get some
perspective about how different classes of problems behave on modern
computers, and how PCs behave compared to other classes of machines.
The idea of emulating an NTM on another NTM got me wondering about LTH,
P, NP... It sounds like between Savitch, Cook, and LTH, I should be
able to find an answer to this question, and actually, it sounds like
nobody knows for sure yet. If I don't find /some/ kind of answer (or
more likely, find one but don't understand it), I'll come back and post
again :)

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.

This is my understanding of UTMs in general, so I'm starting to think
rather than worrying about emulating NTMs on NTMs vs. DTMs, I ought to
be simulating a UTM and seeing for myself what happens in whatever
specific case I happen to be interested in at the time.

--
Tim Chow tchow-at-alum-dot-mit-dot-edu

As always, thanks for the terrific answers!

Regards,
D. C.

.

Relevant Pages