Talk:EXPTIME

From Wikipedia, the free encyclopedia

[edit] Notation EXPTIME^X

What does the notation EXPTIME^X mean? The Anome

From the change you made, I assume you already figured out it means exponential time for oracle machine X. --LC

Yes. The Anome

[edit] EXPTIME vs. EXPSAPCE

Does anybody know where it was proven that EXPTIME is a strict subset of EXPSPACE? I thought that was unknown. -- Jan Hidders 13:17 Feb 9, 2003 (UTC)

I looked around on the internet a bit and everyone says it's unknown, so I'll remove the claim for now.

It would be nice to have an outline of the argument that P is a proper subset of EXPTIME on this page. AxelBoldt 18:56 Feb 9, 2003 (UTC)

Ok. I'll see if I can find some time. It's actually an easy corollary of the Time-hierarchy theorem which probabaly deserves an article by itself. Btw. the EXPTIME-EXPSPACE claim is also made on Computation. -- Jan Hidders 22:29 Feb 9, 2003 (UTC)

Uh I thought the most space consuming algorithm in EXPSPACE was easily proven to be in EXPTIME:

a <- array.new; 
for x <- 1 to 2N do 
  a << 1 
done

clearly proving that EXPTIME was NOT strictly subset of EXPSPACE. In fact, using that same theorem, (x)TIME cannot be strictly contained in (x)SPACE. Poltras 02:49, 8 June 2006 (UTC)

You're wrong. It's easy to construct an algorithm that runs in EXPSPACE and double-exponential time: just have it step a binary counter through all values between 1 and 2^(2^n). This doesn't prove that EXPTIME is a proper subset of EXPSPACE, since these are sets of problems, but it's certainly not true that every exponential space algorithm requires at most exponential time. Also, if PTIME = PSPACE, then P = NP, which as you may be aware is an unsolved problem. Deco 02:53, 8 June 2006 (UTC)

You're right. I was proving the reverse: xSPACE cannot be strictly contained in xTIME. pfffft... hard night (2:49 AM was way over my head :). Poltras 14:07, 9 June 2006 (UTC)

By the way, there is a result (not a simple one) proving that f(n) time is properly contained in f(n) space. For example, you can do more in O(n^2) space than O(n^2) time. However, this only applies to specific functions, not infinite unions over such functions, so it doesn't show P is properly contained in PSPACE, for example. I'd add a citation but can't find it right now. Deco 20:08, 20 June 2006 (UTC)

[edit] Deboldening

Does anyone object to deboldening the nondefining occurrences of EXPTIME, etc.? The emboldening is inconsistent on this page, at least, and I don't think it's within Style to embolden every occurrence... --Erik Demaine 20:23, 15 August 2005 (UTC)

It's popular in a number of complexity articles to embolden all occurrences of complexity class names, with the possible exception of links. This is in emulation of popular literature, which does it to distinguish (for example) P the complexity class from some more ordinary set/function P. I would not change just this one article (it would be inconsistent); whether all articles should be changed is a topic that should be decided in a wider forum. Deco 21:05, 15 August 2005 (UTC)