Encyclopedia > EXPTIME-complete

  Article Content

EXPTIME

Redirected from EXPTIME-complete

In complexity theory, EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n.

Some authors restrict p(n) to be a linear function, but a more common definition is to allow p(n) to be any polynomial.

EXPTIME is known to be a subset of EXPSPACE and a superset of PSPACE, NP-complete, NP, and P. That is significant because it is currently unknown which (if any) of those four sets are equal to each other. It is known however that P is a strict subset of EXPTIME.

The complexity class EXPTIME-complete is also a set of decision problems. A decision problem is in EXPTIME-complete if it is in EXPTIME, and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. EXPTIME-complete might be thought of as the hardest problems in EXPTIME.

Examples of EXPTIME-complete problems include the problem of looking at a Chess or Go position, and telling whether the first player can force a win. Actually, the games have to be generalized by playing them on an n × n board instead of the usual board with fixed size. That is because complexity classes like EXPTIME-complete are defined by asymptotic behavior as the problem size grows without bound. Most board games are easier to solve than Chess and Go. See PSPACE-complete for examples.

There exist oracles X for which EXPTIMEX = PSPACEX = NPX (See the oracle machine article for an explanation of the EXPTIMEX notation).



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Bullying

... it did not always have inherently negative implications, it merely designated anyone who assumed power for any period of time without a legitimate basis of ...

 
 
 
This page was created in 40.1 ms