Succinct problems over uniform computational models

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.

• Is $n$ given in binary? In the second example, which of the two languages called $\Gamma$ is actually $\Gamma$ and which is $\Pi$, and what is the “input string of length $2^n$” (does $2^n$ denote here what is denoted $n$ in the definition)? Nov 11, 2022 at 10:44
• @EmilJeřábek $n$ in binary is probably the most natural choice. Thanks for pointing out the typos; calling the cutoff $n$ was a mistake. I've fixed the ambiguities.
– Jake
Nov 11, 2022 at 16:17