1
$\begingroup$

Is there an explicit example of a language which is EXP-complete? Or a weaker question, i.e., is there an explicit example of a language which is proven to be in EXP but not in P? By diagonalization theorem, we know the existence of such a language but is there a construction or explicit example known till date?

$\endgroup$
  • 2
    $\begingroup$ Diagonalization is a constructive proof method: it shows existence by giving an explicit example. $\endgroup$ – sdcvvc Apr 3 '16 at 17:00
  • 1
    $\begingroup$ @PranavBisht What does "not quite satisfied" mean? How are we supposed to answer your question if you don't say what's wrong with the five detailed paragraphs that Wikipedia gives about EXP-completeness? $\endgroup$ – David Richerby Apr 3 '16 at 18:54
  • $\begingroup$ @David Richerby I'm sorry. I was looking for some natural example, which I think are these generalized games. I guess I need to explore and understand the complexity of these games, which I have not given much thought earlier. Is there any proof reference you can give me? $\endgroup$ – Pranav Bisht Apr 3 '16 at 19:16
  • $\begingroup$ Pranav, your question falls short of our expectations. We expect you to do a significant amount of research/self-study before asking, and to show us in the question what you've done, what you found, and why it didn't meet your needs. Also, if people ask you questions in the comments, we expect you to edit your question to clarify it, not just drop comments in the comment thread (questions should be self-contained). Your questions are not likely to be well-received if they are already answered in Wikipedia and you haven't followed up on the standard resources that are available to you. $\endgroup$ – D.W. Apr 3 '16 at 23:09
  • $\begingroup$ And, it's not clear why you are asking for a proof reference, when the Wikipedia article already gives references for its results. Have you read those already? If not, you should read them before asking. Before asking others to spend their time helping you, make sure you've done all the work you can possibly do on your own, including spending the time to follow up on the citations provided in Wikipedia. $\endgroup$ – D.W. Apr 3 '16 at 23:11
3
$\begingroup$

Every EXP-complete problem is not in P, by the time hierarchy theorem. Many games are EXP-complete, you can look up some starting from here.

As a concrete example (albeit not a very simple one), you can consider the problem of emptiness of the intersection of deterministic tree automata. Formally, the input consists of $n$ DFTs $A_1,...,A_n$ (deterministic automata over trees), and the problem is to decide whether $L(A_1)\cap...\cap L(A_n)\neq \emptyset$.

$\endgroup$
3
$\begingroup$

Wikipedia lists several EXPTIME-complete problems:

  • Deciding whether a Turing machine halts within a given number of steps
  • Generalized versions of chess, checkers and go
  • Succinct versions of P-complete problems
$\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.