Talk:EXPTIME

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

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)

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)

SMOG

This article is a great candidate for a SMOG analysis! --Justanother 13:33, 19 July 2007 (UTC)

Though probably not as these readability tests seem to only take number of syllables per word as the primary indicator of complexity, disregarding the fact that short words may represent obscure or esoteric concepts. --Justanother 13:38, 19 July 2007 (UTC)

I just calculated the SMOG of this article's source, and it's 11.9, for whatever that's worth. --Doradus (talk) 19:13, 3 August 2008 (UTC)

EXTIME-complete requires a polynomial-time reduction

Can someone explain why the notion of EXPTIME-complete is defined in terms of a polynomial-time reduction? To me, naively, it seems that an EXPTIME reduction would be a more natural definition, and would be just as interesting. --Doradus 13:51, 13 August 2007 (UTC)

All problems in EXPTIME would be EXPTIME-complete under EXPTIME reductions, which makes the concept useless. That's not to say that you couldn't define it in terms of, say, BPP or BQP or NP or PH reductions, or any number of other things. My best guess is that people use polytime reductions simply because it was what they used to define other classes like NP-complete, and most interesting reductions that we already know about can be done in polytime. It'd be an interesting question to explore the class under other types of reductions, but I'm not aware of any research in this direction, and unless we find some we have no reliable source to cite on it. Dcoetzee 20:11, 13 August 2007 (UTC)

Ok thanks, that's interesting. The notion of RE-complete uses RE reductions, for instance, so I just thought it was a natural analogy. I'm having trouble convincing myself that everything in EXPTIME would be EXPTIME-complete with EXPTIME reductions, but I'll take your word for it. --Doradus 03:48, 15 August 2007 (UTC)

does this seriously need a citation?

we do know that EXPTIME-complete problems are not in P; it has been proven that these problems cannot be solved in polynomial time.[citation needed]

If they are EXPTIME-complete then they are not in P. Otherwise, that means that pretty much all problems lie within P.

It seems silly to ask for a citation for this.

I disagree. Don't overestimate the knowledge level of Wikipedia readers. --Doradus (talk) 19:08, 3 August 2008 (UTC)

"Proper" Supersets

The caption on the Euler graphic says that EXPSPACE is a proper superset of EXPTIME, but this is not known. As far as I know, and consistent with the article, EXPSPACE is a proper superset of PSPACE but not necessarily of EXPTIME. Am I missing something, or is the caption statement unproven? TricksterWolf (talk) 19:51, 23 April 2014 (UTC)

Renaming and Merging EXPTIME and E

The term "EXPTIME" is rarely used in the literature today, it's usually just "EXP". Also there is considerable confusion with the class E. What if we renamed this entry "Exponential Time" and included both EXP and E? The page for E is basically a stub anyway.

If we do this, we should do the same for NEXPTIME and NE. Lance Fortnow (talk) 18:25, 1 July 2024 (UTC)