# EXP-complete example

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?

• Diagonalization is a constructive proof method: it shows existence by giving an explicit example. – sdcvvc Apr 3 '16 at 17:00
• @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? – David Richerby Apr 3 '16 at 18:54
• @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? – Pranav Bisht Apr 3 '16 at 19:16
• 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. – D.W. Apr 3 '16 at 23:09
• 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. – D.W. Apr 3 '16 at 23:11

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