Noob question on complexity of emulated machines?
- From: "D. C." <enharmonix@xxxxxxxxx>
- Date: 23 Aug 2006 11:04:33 -0700
I just reread the title and thought who in the /world/ even understands
what I mean? ... and yet it's /still/ a noob question :) I know it's
probably obvious but I can't find an answer...
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?
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?
TIA!
Regards,
D. C.
.
- Follow-Ups:
- Prev by Date: Re: Diopantine Equations and comp science
- Next by Date: Find Similar Vertices in a graph
- Previous by thread: Re: SQL query plan question
- Next by thread: Re: Noob question on complexity of emulated machines?
- Index(es):
Relevant Pages
|
