snippetMinor
How to use succinct circuits to construct an EXPTIME complete problem?
Viewed 0 times
problemexptimecompletecircuitssuccincthowconstructuse
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#66772, answer score: 3
Revisions (0)
No revisions yet.