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.

  • 1
    $\begingroup$ 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)? $\endgroup$ Nov 11, 2022 at 10:44
  • $\begingroup$ @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. $\endgroup$
    – Jake
    Nov 11, 2022 at 16:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.