<p>For a language <span class="math-container">$\Pi$</span>, the traditional definition of &quot;Succinct-<span class="math-container">$\Pi$</span>&quot; is the set of encodings of circuits whose truth tables are members of <span class="math-container">$\Pi$</span>.</p>
<p>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 &quot;succinct problems&quot; has been studied, and some references to relevant papers if so:</p>
<p><strong>Uniform succinct problem:</strong> for some fixed languages <span class="math-container">$\Gamma$</span> and <span class="math-container">$\Pi$</span>, given a &quot;cutoff&quot; value <span class="math-container">$x \in \mathbb{N}$</span> written in binary, determine whether the bitstring <span class="math-container">$(b_i)_{0 \leq i &lt; x}$</span> defined by <span class="math-container">$b_i = 1 \iff i \in \Gamma$</span> is a member of <span class="math-container">$\Pi$</span>. (Assume each of the <span class="math-container">$i$</span> are padded out to the same length as <span class="math-container">$x$</span> with leading zeroes.)</p>
<p>I'm especially interested in the complexity of such &quot;uniform succinct problems&quot;, relative to the complexities of <span class="math-container">$\Gamma$</span> and <span class="math-container">$\Pi$</span>. For example, let <span class="math-container">$n$</span> be the length of the input value <span class="math-container">$x$</span>. Then we have the following brute-force approaches:</p>
<ul>
<li>If <span class="math-container">$\Gamma$</span> is computable in time <span class="math-container">$O(f(n))$</span> and <span class="math-container">$\Pi$</span> is computable in time <span class="math-container">$O(g(n))$</span>, we can query each of the <span class="math-container">$O(2^n)$</span> <span class="math-container">$\Gamma$</span> machines in time <span class="math-container">$O(2^nf(n) + 2^n)$</span>, and then compute <span class="math-container">$\Pi$</span> on the resulting bitstring in time <span class="math-container">$O(g(O(2^n)))$</span>, for a total runtime of <span class="math-container">$O(2^n + 2^nf(n) + g(O(2^n)))$</span>.</li>
<li>If <span class="math-container">$\Gamma$</span> is computable in <span class="math-container">$DSPACE(n^k)$</span> for <span class="math-container">$k \geq 1$</span>, then for any <span class="math-container">$\Pi \in DSPACE(\log^k(n))$</span>, the resulting succinct problem is in <span class="math-container">$DSPACE(n^k)$</span>. We can think of such a problem as having an implicit input tape of length <span class="math-container">$x \in O(2^n)$</span> which we can query by running <span class="math-container">$\Gamma$</span>. Since <span class="math-container">$\Pi$</span> is in <span class="math-container">$DSPACE(\log^k(n))$</span>, simulating it over this implicit input requires <span class="math-container">$O(\log^k(O(2^n))) = O(n^k)$</span> bits of space, as well as <span class="math-container">$\log(x) = \log(O(2^n)) = O(n)$</span> 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 <span class="math-container">$\Gamma$</span> on the input tape head position we have recorded, which takes <span class="math-container">$DSPACE(n^k)$</span>. In general, for <span class="math-container">$\Gamma$</span> computable in <span class="math-container">$DSPACE(f(n))$</span> and <span class="math-container">$\Pi$</span> computable in <span class="math-container">$DSPACE(g(n))$</span>, this gives us a space bound of <span class="math-container">$O(n + f(n) + g(O(2^n)))$</span>.</li>
</ul>
<p>...and one mildly non-trivial approach:</p>
<ul>
<li>(See <a href="https://cstheory.stackexchange.com/questions/51952/check-whether-dfa-accepts-majority-of-words-less-than-a-cutoff-with-another-dfa">this other question</a>) if <span class="math-container">$\Gamma$</span> is regular, and <span class="math-container">$\Pi$</span> 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 <span class="math-container">$DSPACE(n)$</span> naive approach). However, if we let <span class="math-container">$\Pi$</span> be the set of bitstrings with a majority of 1s, then the resulting succinct language is non-regular.</li>
</ul>
<p>Any references appreciated.</p>

CC BY-SA 4.0
2022-11-11T10:44:08.403Z
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)?
Emil Jeřábek
CC BY-SA 4.0
2022-11-11T16:17:18.967Z
@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
<reference-request><succinct>
Succinct problems over uniform computational models
Jake
# Succinct problems over uniform computational models

(Asked by: username_0 on 2022-11-11)

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](https://cstheory.stackexchange.com/questions/51952/check-whether-dfa-accepts-majority-of-words-less-than-a-cutoff-with-another-dfa)) 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.

**Tags:** reference-request, succinct

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

---

## 0 answers

