1

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

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
Matt Groff
  • 2,100
  • 13
  • 19
  • 2
    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 Feb 10 '11 at 07:22
  • 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 Feb 10 '11 at 08:15
  • 7
    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 Feb 10 '11 at 08:37
  • 1
    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 Feb 10 '11 at 09:52
  • 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 Feb 10 '11 at 14:41
  • 1
    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 Feb 10 '11 at 23:45
  • 2
    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 Feb 10 '11 at 23:50

1 Answers1

1

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.

Bin Fu
  • 26
  • 1