1
$\begingroup$

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....

$\endgroup$
  • 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 Ito Feb 10 '11 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$ – Kaveh Feb 10 '11 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 Salamon Feb 10 '11 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 Groff Feb 10 '11 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 Ito Feb 10 '11 at 23:50
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.