# Succinct complete problems in DTIME(EXP(EXP(…)))

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?

• 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: cstheory.stackexchange.com/questions/34883/…). – Noam Zeilberger Nov 3 '16 at 10:37
• I do not exactly understand your question either. If I remember correctly, Hans-Jörg Peter considered succinct problems beyond EXPTIME in his thesis: react.uni-saarland.de/publications/HJPeter.pdf – Markus Nov 3 '16 at 17:20
• 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 Nov 4 '16 at 0:21
• 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 Nov 4 '16 at 0:24

• @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 Nov 4 '16 at 15:26