# 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: 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. – Yuval Filmus Dec 1 '16 at 19:47
• Footnote 1 provides more details on the book. For example, its title is Computational Complexity. It is a pretty standard textbook. – Yuval Filmus Dec 2 '16 at 11:23
• I found that they have it in the University Library of Amsterdam. I'll drive there one of these days, thanks. – Albert Hendriks Dec 3 '16 at 12:03
• @AlbertHendriks you can find the book on the internet. pirate it. – Ayrat Dec 30 '18 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.