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....
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ 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. $\endgroup$– Tsuyoshi ItoCommented Feb 10, 2011 at 7:22
-
7$\begingroup$ 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". $\endgroup$– KavehCommented Feb 10, 2011 at 8:37
-
1$\begingroup$ Following on from Kaveh's comment, qwiki.stanford.edu/index.php/Complexity_Zoo:E#exp and qwiki.stanford.edu/index.php/Complexity_Zoo:E#expspace would be my canonical points of departure. $\endgroup$– András SalamonCommented Feb 10, 2011 at 9:52
-
1$\begingroup$ 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... $\endgroup$– Matt GroffCommented Feb 10, 2011 at 23:45
-
2$\begingroup$ 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. $\endgroup$– Tsuyoshi ItoCommented Feb 10, 2011 at 23:50
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
