For a language $\Pi$, the traditional definition of "Succinct-$\Pi$" is the set of encodings of circuits whose truth tables are members of $\Pi$.
This definition is essentially restricted (or at least best-suited to) to non-uniform models of computation. What I'd like to know is whether the following uniform version of "succinct problems" has been studied, and some references to relevant papers if so:
Uniform succinct problem: for some fixed languages $\Gamma$ and $\Pi$, given a "cutoff" value $x \in \mathbb{N}$ written in binary, determine whether the bitstring $(b_i)_{0 \leq i < x}$ defined by $b_i = 1 \iff i \in \Gamma$ is a member of $\Pi$. (Assume each of the $i$ are padded out to the same length as $x$ with leading zeroes.)
I'm especially interested in the complexity of such "uniform succinct problems", relative to the complexities of $\Gamma$ and $\Pi$. For example, let $n$ be the length of the input value $x$. Then we have the following brute-force approaches:
- If $\Gamma$ is computable in time $O(f(n))$ and $\Pi$ is computable in time $O(g(n))$, we can query each of the $O(2^n)$ $\Gamma$ machines in time $O(2^nf(n) + 2^n)$, and then compute $\Pi$ on the resulting bitstring in time $O(g(O(2^n)))$, for a total runtime of $O(2^n + 2^nf(n) + g(O(2^n)))$.
- If $\Gamma$ is computable in $DSPACE(n^k)$ for $k \geq 1$, then for any $\Pi \in DSPACE(\log^k(n))$, the resulting succinct problem is in $DSPACE(n^k)$. We can think of such a problem as having an implicit input tape of length $x \in O(2^n)$ which we can query by running $\Gamma$. Since $\Pi$ is in $DSPACE(\log^k(n))$, simulating it over this implicit input requires $O(\log^k(O(2^n))) = O(n^k)$ bits of space, as well as $\log(x) = \log(O(2^n)) = O(n)$ bits of space for the position of the input head. Every time we need to query the input symbol at a given position, we compute $\Gamma$ on the input tape head position we have recorded, which takes $DSPACE(n^k)$. In general, for $\Gamma$ computable in $DSPACE(f(n))$ and $\Pi$ computable in $DSPACE(g(n))$, this gives us a space bound of $O(n + f(n) + g(O(2^n)))$.
...and one mildly non-trivial approach:
- (See this other question) if $\Gamma$ is regular, and $\Pi$ is the set of bitstrings with a fixed number of 1s mod a constant, then the uniform succinct language as defined here is also regular (which beats the $DSPACE(n)$ naive approach). However, if we let $\Pi$ be the set of bitstrings with a majority of 1s, then the resulting succinct language is non-regular.
Any references appreciated.
