6
  1. We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems.

What is the standard way to define $EXP$-complete problem from succinct representations of $P$ complete problems that do not come from graphs if there are any?

For example what is the succinct version of the $P$-complete iterated mod problem $$\mbox{given }a, b_1, b_2,\dots, b_n\in\Bbb Z,\mbox{ is }((\dots((a \bmod b_1) \bmod b_2) \dots) \bmod b_n) = 0$$ and would that be $EXP$-complete and what is the succinct version of linear programming and would that be $EXP$-complete?

  1. Is there a higher version of $ETH$ (Exponential Time Hypothesis) that is applicable to the $EXP$ versus $NEXP$ problem for $NEXP$ complete problems that come from succinct version of $NP$ complete problems?
Turbo
  • 12,812
  • 1
  • 19
  • 68
  • "We know succinct versions of $P$-complete problems are $EXP$-complete" : do we? We know that we can get $EXP$-complete problems by 'succinctifying' some $P$-complete problems, but I don't know that I've ever seen anything that suggests that every $P$-complete problem can be turned into an $EXP$-complete one by making it succinct... – Steven Stadnicki Jul 11 '17 at 19:49
  • 1
    @StevenStadnicki In here we have 'Papadimitriou and Yanakkakis further this line of research, and prove that for a problem $Π$ which is $NP$-complete/$P$-complete, the corresponding Succinct version, namely Succinct $Π$ is respectively, $NEXP$-complete and $EXP$-complete'. – Turbo Jul 11 '17 at 20:28
  • 1
    So, that paper should give you the answer to question 1. – Emil Jeřábek Jul 11 '17 at 21:03

1 Answers1

4

  1. The description of a succinct problem has very little to do with graphs, per se. Given a language $L \subseteq \Sigma^*$, we can define its succinct version as the set of Boolean circuits $C$ such that, if $C$ has $m$ inputs, then the string $s$ of length $2^m$ which is the concatenation of $C(0^m) C(0^{m-1} 1) C(0^{m-2} 10) \dotsb C(1^m)$ is in $L$.

  2. You can make such a version, though I haven't seen it studied before. The smallest known upper bound on the deterministic time complexity of $\mathsf{NEXP}$ is $\mathsf{EEXP} = \mathsf{DTIME}(2^{2^{n^{O(1)}}})$, so you could conjecture that a standard $\mathsf{NEXP}$-complete problem is not in significantly sub-doubly-exponential time.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228