# How to use succinct circuits to construct an EXPTIME complete problem?

When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar for EXPTIME-completeness. Wikipedia mentions:

Another set of important EXPTIME-complete problems relates to succinct circuits. Succinct circuits are simple machines used to describe some graphs in exponentially less space. They accept two vertex numbers as input and output whether there is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such as an adjacency matrix, solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs.[8]

8: Papadimitriou (1994), section 20.1, page 492.

I understand the concept that you can describe some graphs using exponentially less space and use that as input, but I can't find the mentioned resource or find out how succinct graphs work exactly or how to construct an EXPTIME-complete problem.

• You can find the book in any decent library. Dec 1, 2016 at 19:47
• Footnote 1 provides more details on the book. For example, its title is Computational Complexity. It is a pretty standard textbook. Dec 2, 2016 at 11:23
• I found that they have it in the University Library of Amsterdam. I'll drive there one of these days, thanks. Dec 3, 2016 at 12:03
• @AlbertHendriks you can find the book on the internet. pirate it. Dec 30, 2018 at 9:44

Suppose that $L$ is a P-complete problem, and that there is a polytime reduction $f$ from the Circuit Value Problem to $L$ in which, given an input $x_1\ldots x_n$ of size $n$, the $j$th bit of $f(x)$ is, irrespective of $x$, either constant of equals some input bit or its negation. Then the succinct version of $L$, which consists of pairs $\langle n,C \rangle$, where $C$ is a circuit on $\lceil \log_2 n \rceil$ inputs, such that $C(0) \ldots C(n-1) \in L$, is EXPTIME-complete.