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?
  • $\begingroup$ "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... $\endgroup$ Jul 11, 2017 at 19:49
  • 1
    $\begingroup$ @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'. $\endgroup$
    – Turbo
    Jul 11, 2017 at 20:28
  • 1
    $\begingroup$ So, that paper should give you the answer to question 1. $\endgroup$ Jul 11, 2017 at 21:03

1 Answer 1

  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.


Your Answer

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

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