NEXPTIME...unlimited space?
in [Theory]
|
Prev: NP with oracle machines
Next: Position: Full Professorship in Programming Languages and Formal Models at University of Aarhus, Denmark
From: Zhu Guohun on 7 Jul 2008 11:17 On 7รร7รร, รรรรง3รยฑ27ยทร, Chris F Clark <c...(a)shell01..TheWorld.com> wrote: > If I followed the attributions correctly, cplxp...(a)gmail.com wrote: > > > > "NEXPTIME (sometimes called NEXP) is the set of decision problems that > > > can be solved by a non-deterministic Turing machine using time > > > O(2^p(n)) for some polynomial p(n), and unlimited space." > > The space won't truly be unlimited because a TM can only write to so > many cells in the time alloted. Clearly, if the machine spends the > entire time moving in one direction and writing symbols, one can bound > the amount of space it uses and no other TM will use more. However, > by saying unbounded, one might not have to worry about what the actual > bounds on the space are, nor with proving them. > The space can be regard as a infinite space. for example : integer factor n=p*q the p,q belong to the infinite integer set, certainly, we only consider the factor not beyond the sqrt(n). ------------------------- Zhu
From: tchow on 7 Jul 2008 12:36 In article <45b5d1fa-d664-4c6d-baff-6a40c84b95fb(a)m44g2000hsc.googlegroups.com>, <cplxphil(a)gmail.com> wrote: >Does NEXPTIME really allow for unlimited space? I would have thought >it would be bounded by exponential space. Consider the simpler class P. This could be defined as languages that can be decided given polynomial time and polynomial space, but it can also be defined as languages decidable given polynomial time and unlimited space. The point is that even if you're given unlimited space, you can use only a polynomial amount of it in a polynomial amount of time, so you really can't solve any more problems with unlimited space than with polynomial space (if you have only polynomial time). So if for some theoretical reason you find it convenient to use the unlimited-space version of the definition, you are free to do so. Somewhat more subtly, PSPACE can be defined as the class of languages decidable with polynomial space and unlimited time. Again, with only polynomial space to work with, extra time beyond a certain point is of no use and makes no difference. Your program and your memory space can be in only a limited number of possible states, and they must deterministically do the same thing when they're in the same state, so the possible computations are limited. -- 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
From: cplxphil on 7 Jul 2008 16:45
On Jul 7, 12:36 pm, tc...(a)lsa.umich.edu wrote: > In article <45b5d1fa-d664-4c6d-baff-6a40c84b9...(a)m44g2000hsc.googlegroups.com>, > > <cplxp...(a)gmail.com> wrote: > >Does NEXPTIME really allow for unlimited space? I would have thought > >it would be bounded by exponential space. > > Consider the simpler class P. This could be defined as languages that can > be decided given polynomial time and polynomial space, but it can also be > defined as languages decidable given polynomial time and unlimited space. > The point is that even if you're given unlimited space, you can use only a > polynomial amount of it in a polynomial amount of time, so you really can't > solve any more problems with unlimited space than with polynomial space (if > you have only polynomial time). So if for some theoretical reason you find > it convenient to use the unlimited-space version of the definition, you are > free to do so. > > Somewhat more subtly, PSPACE can be defined as the class of languages > decidable with polynomial space and unlimited time. Again, with only > polynomial space to work with, extra time beyond a certain point is of > no use and makes no difference. Your program and your memory space > can be in only a limited number of possible states, and they must > deterministically do the same thing when they're in the same state, > so the possible computations are limited. > -- > 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 Ok cool, thanks. -Phil |