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.