4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You can find the book in any decent library. $\endgroup$ – Yuval Filmus Dec 1 '16 at 19:47
  • 2
    $\begingroup$ Footnote 1 provides more details on the book. For example, its title is Computational Complexity. It is a pretty standard textbook. $\endgroup$ – Yuval Filmus Dec 2 '16 at 11:23
  • $\begingroup$ I found that they have it in the University Library of Amsterdam. I'll drive there one of these days, thanks. $\endgroup$ – Albert Hendriks Dec 3 '16 at 12:03
  • $\begingroup$ @AlbertHendriks you can find the book on the internet. pirate it. $\endgroup$ – Ayrat Dec 30 '18 at 9:44
3
$\begingroup$

Since you're having trouble getting hold of Papadimitriou's classic textbook Computational Complexity, let me suggest another resource: Papadimitriou's paper with Yannakakis, A note on succinct representations of graphs. They prove the following general result:

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.

The hard part of the proof uses the construction in the Cook–Levin theorem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.