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: cplxphil on 5 Jul 2008 20:42 Hello, I read on the Wikipedia page for NEXPTIME, or NEXP, the following definition for the complexity class: "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." Does NEXPTIME really allow for unlimited space? I would have thought it would be bounded by exponential space. NP languages require that the certificates for acceptance for all members of the language be polynomial bounded with respect to the string, meaning, NP languages have only polynomial space. Why is NEXPTIME different? (Or is Wikipedia wrong? It wouldn't be the first time, obviously.) -Phil
From: Zhu Guohun on 5 Jul 2008 23:25 On 7ÔÂ6ÈÕ, ÉÏÎç8ʱ42·Ö, cplxp...(a)gmail.com wrote: > Hello, > > I read on the Wikipedia page for NEXPTIME, or NEXP, the following > definition for the complexity class: > > "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." > > Does NEXPTIME really allow for unlimited space? I would have thought > it would be bounded by exponential space. NP languages require that > the certificates for acceptance for all members of the language be > polynomial bounded with respect to the string, meaning, NP languages > have only polynomial space. Why is NEXPTIME different? (Or is > Wikipedia wrong? It wouldn't be the first time, obviously.) > > -Phil I am not very clearly understand the definition of "unlimited space", is it equals to the "infinite space"? But I think the "using time O(2^p(n)) for some polynomial p(n)" is the main issue on the definition. ------------------------- Zhu
From: cplxphil on 6 Jul 2008 11:08 On Jul 5, 11:25 pm, Zhu Guohun <ccgh...(a)hrt.dis.titech.ac.jp> wrote: > On 7ÔÂ6ÈÕ, ÉÏÎç8ʱ42·Ö, cplxp...(a)gmail.com wrote: > > > > > Hello, > > > I read on the Wikipedia page for NEXPTIME, or NEXP, the following > > definition for the complexity class: > > > "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." > > > Does NEXPTIME really allow for unlimited space? I would have thought > > it would be bounded by exponential space. NP languages require that > > the certificates for acceptance for all members of the language be > > polynomial bounded with respect to the string, meaning, NP languages > > have only polynomial space. Why is NEXPTIME different? (Or is > > Wikipedia wrong? It wouldn't be the first time, obviously.) > > > -Phil > > I am not very clearly understand the definition of "unlimited > space", is it equals to the "infinite space"? > > But I think the "using time O(2^p(n)) for some polynomial p(n)" is > the main issue on the definition. > > ------------------------- > Zhu Yes, I suppose infinite space is an accurate synonym. I know that "using time O(2^p(n)) for some polynomial p(n)" is the main part of the definition, but to establish membership in NEXPTIME, it's important to have the full definition. -Phil
From: Chris F Clark on 6 Jul 2008 15:27 If I followed the attributions correctly, cplxphil(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. Hope this helps, -Chris ****************************************************************************** Chris Clark Internet: christopher.f.clark(a)compiler-resources.com Compiler Resources, Inc. or: compres(a)world.std.com 23 Bailey Rd Web Site: http://world.std.com/~compres Berlin, MA 01503 voice: (508) 435-5016 USA fax: (978) 838-0263 (24 hours) ------------------------------------------------------------------------------
From: Patricia Shanahan on 7 Jul 2008 09:22
Chris F Clark wrote: > If I followed the attributions correctly, cplxphil(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. Or you leave the field open for people to derive and prove bounds. In general, it seems better to use minimal definitions, and then derive relationships. In the complexity class context, that means defining classes that constrain only one resource at a time. Patricia |