1
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\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$ – benin Mar 5 '12 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$ – Sasho Nikolov Mar 5 '12 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$ – Sasho Nikolov Mar 5 '12 at 20:22

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.