<p>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.</p>

CC BY-SA 3.0
2012-03-05T19:09:44.967Z
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
CC BY-SA 3.0
2012-03-05T20:18:42.177Z
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
CC BY-SA 3.0
2012-03-05T20:22:03.967Z
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
CC BY-SA 3.0
2012-03-05T18:53:31.480Z
2012-03-05T18:53:31.480Z
Sasho Nikolov
<p>Recently I saw an interesting question on succinct problems from <a href="https://cstheory.stackexchange.com/questions/10320/succint-problems-in-mathsfp">here</a>. 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?</p>

<cc.complexity-theory>
Is there a succinct representation for all problems?
benin
# Is there a succinct representation for all problems?

(Asked by: username_0 on 2012-03-05)

Recently I saw an interesting question on succinct problems from [here](https://cstheory.stackexchange.com/questions/10320/succint-problems-in-mathsfp). 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?

**Tags:** cc.complexity-theory

---

## 1 answers

### Answer by username_1 on 2012-03-05. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: 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.  

---

