Recently I saw an interesting question on succinct problems from here. I was wondering if all problems have a succinct representation(It would be great if you can provide me a reference/proof). When I read the paper linked in the post, I could find mostly only graph problems with succinct representation. Can a problem like testing for primality have a succinct representation? Is there a proof/reference for this anywhere?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Any language $L$ consisting of strings of length $2^k$ for nonnegative integers k has a succinct version: given a binary circuit $C$ that takes $k$ inputs and outputs a single bit, is the truth table (seen as a binary string of length $2^k$) a string of the language $L$. You can restrict any language to strings whose length is a power of two, or you can try other encoding tricks.
answered Mar 5, 2012 at 18:53
-
$\begingroup$ can you give me a explicit example of how one can go about building such a circuit? in the paper by galperin-wigderson, a graph is represented by a circuit which outputs 1 iff the two $n$-bit numbers input correspond to some edge in the graph. how can you wire such a thing in to a circuit, if your graph has many edges? can any graph be represented in such a way? $\endgroup$– beninMar 5, 2012 at 19:09
-
$\begingroup$ for a graph $G$ with $N$ vertices, this is just a binary function on $2 \lceil \log_2 N \rceil$ bits. By Lupanov's bound, any binary function on $n$ bits can be computed by a $2^n/n + o(2^n/n)$ size circuit, so any graph on $N$ vertices can be represented by a circuit of size $O(N^2/\log N)$. However, some graphs have circuit representations where the circuit is polynomial size in $\log N$, and Galperin and Wigderson use that to prove their hardness result. $\endgroup$ Mar 5, 2012 at 20:18
-
4$\begingroup$ see my answer here cstheory.stackexchange.com/a/10503/4896: the argument is that the SAT instances in the Cook-Levin reduction have succinct (i.e. polysize in the number of input bits) circuit representations, and, therefore, Succinct SAT is NEXP-hard. $\endgroup$ Mar 5, 2012 at 20:22