# Is there a succinct representation for all problems?

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?

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.
• 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? Mar 5, 2012 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. Mar 5, 2012 at 20:18