2

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?

Community
  • 1
benin
  • 23
  • 2

1 Answers1

6

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
  • 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? – benin Mar 05 '12 at 19:09
  • 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. – Sasho Nikolov Mar 05 '12 at 20:18
  • 4
    see my answer here http://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. – Sasho Nikolov Mar 05 '12 at 20:22