# 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. Apr 3, 2016 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? Apr 3, 2016 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? Apr 3, 2016 at 19:16
– D.W.
Apr 3, 2016 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, 2016 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$.