HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

EXP-complete example

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
examplecompleteexp

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#55394, answer score: 6

Revisions (0)

No revisions yet.