<p>See, e.g., Theorem 5 of </p>

<blockquote>
  <p>Balcazar, Lozano, and Toran, <a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/succinct.pdf" rel="noreferrer">The complexity of algorithmic problems on succinct instances</a> (<a href="http://dx.doi.org/10.1007/978-1-4615-3422-8_30" rel="noreferrer">doi</a>)</p>
</blockquote>

<p>This theorem essentially lets you bootstrap up the tower of exponentials as desired, using the appropriate standard bounded version of the halting problem as being complete for most standard classes.</p>

CC BY-SA 3.0
2016-11-03T23:33:54.463Z
Thanks! This looks great, but I don't immediately see how the notions of reduction they use can be "bootstrapped". That is, Theorem 5, seems to say that, if if I have a hard problem for a lower class (e.g. EXP) that is hard under a strong notion of logspace-reductions, then the succinct version of the same problem is hard for a higher class (e.g. EXP(EXP)) but for a weaker notion of reduction (standard poly-time). Can I use the latter problem to move up and obtain a "doubly succinct" problem for EXP(EXP(EXP))?
Thomas Vidick
CC BY-SA 3.0
2016-11-04T15:26:37.273Z
@ThomasVidick: No, you're right. "Bootstrap" was the wrong word. The point is this: suppose you want to consider $C=DTIME(2^{2^{...}})$ (tower of height $k=O(1)$). Let $H_k = \{(M,x) : M$ halts on input x in time $2^{2^{...}}\}$ (where the top of the tower is $|x|$). Then $H_k$ is complete for $C$ under logspace reductions (or possibly even weaker). Then the theorem implies the succinct version of $H_k$ is complete for the next tower-of-exp class up. It's not exactly what you were looking for, I think, but it's the closest I could find in the literature.
Joshua Grochow
CC BY-SA 3.0
2016-11-05T14:39:39.633Z
Thanks. Yes, I would have liked to go all the way up the hierarchy, starting from a problem at the bottom level and moving it up by recursively considering succinct versions of it. But that may not be possible.
Thomas Vidick
CC BY-SA 3.0
2016-11-03T18:52:43.590Z
2016-11-03T18:52:43.590Z
Joshua Grochow
<p>I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such that $R(x)$ is a succinct encoding of a satisfiable formula if and only if $x\in L$. </p>

<p>I am having trouble going beyond $(N)EXPTIME$. Take $DTIME(2^{2^{p(n)}})$. Are there analogue succinct problems here? This could take the form, on input $x$ one can compute a poly-size circuit $R(x)$ which on each input computes an exponential-size circuit which on each input returns a clause...</p>

<p>Aside from the fact that this is hard to grasp, what troubles me if whether one can guarantee that this hierarchy of circuits calling each other exists, i.e. that at every level the circuits of appropriate size exist. When we consider $NEXP$, we are directly verifying the tableau of a Turing-machine computation, so this is pretty straightforward. But a few levels up it becomes much less clear to me. (Ultimately I am interesting in moving up many levels of exponentiation, possibly even a polynomial number of exponentiations, which I believe would move me out of even $ELEMENTARY$?) </p>

<p>My question is, does anyone have pointers to literature discussing such problems? Or a good sense for what is the appropriate way to define "succinct" complete problems for classes that are so high in the time hierarchy? </p>

CC BY-SA 3.0
2016-11-03T10:37:03.790Z
I'm not sure this is exactly what you are looking for, so will just comment. A natural problem in logic which requires non-elementary time is deciding higher-order quantified boolean formulas, which is in a sense a "succinct" version of QBF. Bounding the order of the quantifiers presumably yields problems which are complete for exponential towers of time. However, I don't know of a good reference for these results (I actually asked a question about this recently: http://cstheory.stackexchange.com/questions/34883/reference-request-deciding-validity-of-higher-order-quantified-boolean-formulas).
Noam Zeilberger
CC BY-SA 3.0
2016-11-03T17:20:38.003Z
I do not exactly understand your question either. If I remember correctly, Hans-Jörg Peter considered succinct problems beyond EXPTIME in his thesis: https://www.react.uni-saarland.de/publications/HJPeter.pdf
Markus
CC BY-SA 3.0
2016-11-04T00:21:59.323Z
Thanks for the pointers! Regarding Peter's thesis, it is a bit of a mouthful so I might have missed something, but it seems he stops at EXP(EXP)) (what is called 2EXPTIME in the thesis). What I'm interested in is how one manages the complexity of repeated iterations of the "provide a succinct description of (a succinct description of (a succinct description of (...)))" process.
Thomas Vidick
CC BY-SA 3.0
2016-11-04T00:24:10.383Z
The reference [HT06] from the post Noam Zeilberger points to seems helpful, except I don't fully understand the descriptive complexity approach. I was looking for a more "down-to-earth" recursion, with circuits describing circuits, as could possibly come from Joshua Grochow's reference below - but as mentioned I am not sure how the notion of reduction evolves through the levels.
Thomas Vidick
<cc.complexity-theory><computability><time-complexity>
Succinct complete problems in DTIME(EXP(EXP(...)))
Thomas Vidick
# Succinct complete problems in DTIME(EXP(EXP(...)))

(Asked by: username_0 on 2016-11-02)

I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such that $R(x)$ is a succinct encoding of a satisfiable formula if and only if $x\in L$.

I am having trouble going beyond $(N)EXPTIME$. Take $DTIME(2^{2^{p(n)}})$. Are there analogue succinct problems here? This could take the form, on input $x$ one can compute a poly-size circuit $R(x)$ which on each input computes an exponential-size circuit which on each input returns a clause...

Aside from the fact that this is hard to grasp, what troubles me if whether one can guarantee that this hierarchy of circuits calling each other exists, i.e. that at every level the circuits of appropriate size exist. When we consider $NEXP$, we are directly verifying the tableau of a Turing-machine computation, so this is pretty straightforward. But a few levels up it becomes much less clear to me. (Ultimately I am interesting in moving up many levels of exponentiation, possibly even a polynomial number of exponentiations, which I believe would move me out of even $ELEMENTARY$?)

My question is, does anyone have pointers to literature discussing such problems? Or a good sense for what is the appropriate way to define "succinct" complete problems for classes that are so high in the time hierarchy?

**Tags:** cc.complexity-theory, computability, time-complexity

> **Comments:**
> **username_1**: I'm not sure this is exactly what you are looking for, so will just comment. A natural problem in logic which requires non-elementary time is deciding higher-order quantified boolean formulas, which is in a sense a "succinct" version of QBF. Bounding the order of the quantifiers presumably yields problems which are complete for exponential towers of time. However, I don't know of a good reference for these results (I actually asked a question about this recently: http://cstheory.stackexchange.com/questions/34883/reference-request-deciding-validity-of-higher-order-quantified-boolean-formulas).  
> **username_2**: I do not exactly understand your question either. If I remember correctly, Hans-Jörg Peter considered succinct problems beyond EXPTIME in his thesis: https://www.react.uni-saarland.de/publications/HJPeter.pdf  
> **username_0**: Thanks for the pointers! Regarding Peter's thesis, it is a bit of a mouthful so I might have missed something, but it seems he stops at EXP(EXP)) (what is called 2EXPTIME in the thesis). What I'm interested in is how one manages the complexity of repeated iterations of the "provide a succinct description of (a succinct description of (a succinct description of (...)))" process.  
> **username_0**: The reference [HT06] from the post username_1 points to seems helpful, except I don't fully understand the descriptive complexity approach. I was looking for a more "down-to-earth" recursion, with circuits describing circuits, as could possibly come from username_3's reference below - but as mentioned I am not sure how the notion of reduction evolves through the levels.  

---

## 1 answers

### Answer by username_3 on 2016-11-03. Score: 6

See, e.g., Theorem 5 of

> Balcazar, Lozano, and Toran, [The complexity of algorithmic problems on succinct instances](https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/succinct.pdf) ([doi](http://dx.doi.org/10.1007/978-1-4615-3422-8_30))

This theorem essentially lets you bootstrap up the tower of exponentials as desired, using the appropriate standard bounded version of the halting problem as being complete for most standard classes.

> **Comments:**
> **username_0**: Thanks! This looks great, but I don't immediately see how the notions of reduction they use can be "bootstrapped". That is, Theorem 5, seems to say that, if if I have a hard problem for a lower class (e.g. EXP) that is hard under a strong notion of logspace-reductions, then the succinct version of the same problem is hard for a higher class (e.g. EXP(EXP)) but for a weaker notion of reduction (standard poly-time). Can I use the latter problem to move up and obtain a "doubly succinct" problem for EXP(EXP(EXP))?  
> **username_3**: @ThomasVidick: No, you're right. "Bootstrap" was the wrong word. The point is this: suppose you want to consider $C=DTIME(2^{2^{...}})$ (tower of height $k=O(1)$). Let $H_k = \{(M,x) : M$ halts on input x in time $2^{2^{...}}\}$ (where the top of the tower is $|x|$). Then $H_k$ is complete for $C$ under logspace reductions (or possibly even weaker). Then the theorem implies the succinct version of $H_k$ is complete for the next tower-of-exp class up. It's not exactly what you were looking for, I think, but it's the closest I could find in the literature.  
> **username_0**: Thanks. Yes, I would have liked to go all the way up the hierarchy, starting from a problem at the bottom level and moving it up by recursively considering succinct versions of it. But that may not be possible.  

---

