8
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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/…). $\endgroup$
    – Noam Zeilberger
    Nov 3, 2016 at 10:37
  • $\begingroup$ 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 $\endgroup$
    – Markus
    Nov 3, 2016 at 17:20
  • $\begingroup$ 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. $\endgroup$
    – Thomas Vidick
    Nov 4, 2016 at 0:21
  • $\begingroup$ 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. $\endgroup$
    – Thomas Vidick
    Nov 4, 2016 at 0:24

1 Answer 1

Reset to default
6
$\begingroup$

See, e.g., Theorem 5 of

Balcazar, Lozano, and Toran, The complexity of algorithmic problems on succinct instances (doi)

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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))? $\endgroup$
    – Thomas Vidick
    Nov 3, 2016 at 23:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Nov 4, 2016 at 15:26
  • $\begingroup$ 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. $\endgroup$
    – Thomas Vidick
    Nov 5, 2016 at 14:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.