# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# EXPTIME

(Redirected from EXPTIME-complete)

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) 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.

In terms of DTIME,

$\mbox{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right).$

We know

PNPPSPACEEXPTIMENEXPTIMEEXPSPACE

and also, by the time hierarchy theorem,

P ⊂ EXPTIME (P ≠ EXPTIME)

so at least one of the inclusions on the first line must be proper (most experts believe all the inclusions are proper). It's also known that if P=NP, then EXPTIME=NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine. 1

EXPTIME can also be reformulated as the space class APSPACE , the problems that can be solved by an alternating Turing machine in polynomial space. This is one way to see that PSPACEEXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine. 2

## EXPTIME-complete

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. Notice that although we don't know if NP-complete is a subset of P or not, we do know that EXPTIME-complete lies outside P; none of these problems can possibly be solved in polynomial time.

In computability theory, one of the basic undecidable problems is that of deciding whether a deterministic Turing machine (DTM) accepts a particular input. One of the most fundamental EXPTIME-complete problems is a simpler version of this which asks if a DTM accepts an input in at most k steps. It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

Other examples of EXPTIME-complete problems include the problem of looking at a generalized Chess, Checkers, or Go position, and determining whether the first player can force a win. These games are EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. By contrast, generalized games that can last for a number of moves that is polynomial in the size of the board are often PSPACE-complete.

Another set of important EXPTIME-complete problems relates to succinct circuits . Succinct circuits are simple machines used to describe graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. If solving a problem on a graph in a natural representation, such as an adjacency matrix, is P-complete, then solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller.3

## References

C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0201530821.
Chris Umans. CS 21: Lecture 13 notes.

## Footnotes

1. Papadimitriou, section 20.1, pg.491.
2. Papadimitriou, section 20.1, Corollary 3, pg.495.
3. Papadimitriou, section 20.1, pg.492.
4. Umans, slide 24.
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice