<p>You may start from the connection between polynomial identity problem and exponential time classes. Polynomial identity problem has significant importance in both algorithm and
complexity theory. The recent breakthrough for faster exponential time exact algorithm for Hamiltonian cycle problem
was derived via a reduction to polynomial identity. From the complexity point of view,
derandomization of polynomial identity implies the separation of NEXP or PP from P/ploy.
Therefore, I believe that polynomial identity will continue to play an important role in both<br>
algorithm and complexity theory. It is closely related to some exponential time algorithmes, and 
also the separations between exponential time classes and non-uniform circuit classes. </p>

CC BY-SA 2.5
2011-02-12T02:20:46.953Z
2011-02-12T02:20:46.953Z
Bin Fu
<p>I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE.  I'd like to learn more about these two topics, but I'm not sure what the best approach is....</p>

CC BY-SA 2.5
2011-02-10T07:22:18.817Z
Too vague.  What do you want to know about EXP and EXPSPACE?  I hope that your question is research-level, because otherwise it will not belong on this website.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T08:15:16.727Z
well it *is* a reference request, so it seems more on topic than off. For example, consider also Matt's question k-SAT (http://cstheory.stackexchange.com/questions/4314/information-on-k-sat-introduction-bounds-methods-etc) which was well received
Suresh Venkat
CC BY-SA 2.5
2011-02-10T08:37:20.713Z
Matt, I think the question is too general in the current form. It would be better if you give some motivation and be more specific about what you want to know about them and why. In the current form the answer is "check the complexity zoo".
Kaveh
CC BY-SA 2.5
2011-02-10T09:52:24.460Z
Following on from Kaveh's comment, http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp and http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#expspace would be my canonical points of departure.
András Salamon
CC BY-SA 2.5
2011-02-10T14:41:00.007Z
I have found it plenty challenging to construct concrete examples of the complexity classes that an answer by Luca Trevisan references: "problems in NE that require doubly-exponential time to be solved", and surely I am not alone in liking to see concrete examples of complexity classes.   So if this question were amended to request references that include multiple concrete example, then I would up-vote it. See the MathOverflow link to Trevisan's answer: "http://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716"
John Sidles
CC BY-SA 2.5
2011-02-10T23:45:52.900Z
One direction of study that I'm interested in is viewing papers on problems considered in one of these classes, and discussing the runtimes and analysis. I've had fun considering the designs of algorithms to solve tough problems. So I'm wondering what types of problems are associated with these two classes.  I'll try to provide a more descriptive inquiry soon...
Matt Groff
CC BY-SA 2.5
2011-02-10T23:50:19.403Z
From your comment, it seems to me that you are interested in works on algorithms (for some natural problems) which take exponential time and/or space rather than the complexity-theoretic aspect of the classes EXP and EXPSPACE.  (If this is the case, I think that the correct tag is [ds.algorithms] rather than [cc.complexity-theory].)  That is much more reasonable than “Tell me anything about EXP and EXPSPACE,” but I am afraid that still there might be too many works satisfying your criteria.
Tsuyoshi Ito
<cc.complexity-theory><reference-request><complexity-classes><exp-time-algorithms>
Learning about EXPTIME and EXPSPACE
Matt Groff
# Learning about EXPTIME and EXPSPACE

(Asked by: username_0 on 2011-02-10)

I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE. I'd like to learn more about these two topics, but I'm not sure what the best approach is....

**Tags:** cc.complexity-theory, reference-request, complexity-classes, exp-time-algorithms
> **Comments:**
> **username_1**: Too vague.  What do you want to know about EXP and EXPSPACE?  I hope that your question is research-level, because otherwise it will not belong on this website.  
> **username_2**: well it *is* a reference request, so it seems more on topic than off. For example, consider also Matt's question k-SAT (http://cstheory.stackexchange.com/questions/4314/information-on-k-sat-introduction-bounds-methods-etc) which was well received  
> **username_3**: Matt, I think the question is too general in the current form. It would be better if you give some motivation and be more specific about what you want to know about them and why. In the current form the answer is "check the complexity zoo".  
> **username_4**: Following on from Kaveh's comment, http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp and http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#expspace would be my canonical points of departure.  
> **username_5**: I have found it plenty challenging to construct concrete examples of the complexity classes that an answer by Luca Trevisan references: "problems in NE that require doubly-exponential time to be solved", and surely I am not alone in liking to see concrete examples of complexity classes.   So if this question were amended to request references that include multiple concrete example, then I would up-vote it. See the MathOverflow link to Trevisan's answer: "http://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716"  
> **username_0**: One direction of study that I'm interested in is viewing papers on problems considered in one of these classes, and discussing the runtimes and analysis. I've had fun considering the designs of algorithms to solve tough problems. So I'm wondering what types of problems are associated with these two classes.  I'll try to provide a more descriptive inquiry soon...  
> **username_1**: From your comment, it seems to me that you are interested in works on algorithms (for some natural problems) which take exponential time and/or space rather than the complexity-theoretic aspect of the classes EXP and EXPSPACE.  (If this is the case, I think that the correct tag is [ds.algorithms] rather than [cc.complexity-theory].)  That is much more reasonable than “Tell me anything about EXP and EXPSPACE,” but I am afraid that still there might be too many works satisfying your criteria.  

---

## 1 answers

### Answer by username_6 on 2011-02-12. Score: 1 | Accepted answer

You may start from the connection between polynomial identity problem and exponential time classes. Polynomial identity problem has significant importance in both algorithm and
complexity theory. The recent breakthrough for faster exponential time exact algorithm for Hamiltonian cycle problem
was derived via a reduction to polynomial identity. From the complexity point of view,
derandomization of polynomial identity implies the separation of NEXP or PP from P/ploy.
Therefore, I believe that polynomial identity will continue to play an important role in both  
algorithm and complexity theory. It is closely related to some exponential time algorithmes, and
also the separations between exponential time classes and non-uniform circuit classes.


---

