<ol>
<li><p>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$.</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2017-07-11T22:16:48.540Z
2017-07-11T22:16:48.540Z
Joshua Grochow
<ol>
<li>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. </li>
</ol>

<p>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?</p>

<p>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?</p>

<ol start="2">
<li>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?</li>
</ol>

CC BY-SA 3.0
2017-07-11T19:49:32.950Z
"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
CC BY-SA 3.0
2017-07-11T20:28:29.443Z
@StevenStadnicki In [here](https://cstheory.stackexchange.com/questions/10320/succinct-problems-in-mathsfp) 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
CC BY-SA 3.0
2017-07-11T21:03:16.647Z
So, that paper should give you the answer to question 1.
Emil Jeřábek
<cc.complexity-theory><nexp><succinct>
On succinct $EXP$ and $NEXP$ complete problems?
Turbo
# On succinct $EXP$ and $NEXP$ complete problems?

(Asked by: username_0 on 2017-07-10)

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?

2. 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?

**Tags:** cc.complexity-theory, nexp, succinct

> **Comments:**
> **username_1**: "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...  
> **username_0**: @StevenStadnicki In [here](https://cstheory.stackexchange.com/questions/10320/succinct-problems-in-mathsfp) 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'.  
> **username_2**: So, that paper should give you the answer to question 1.  

---

## 1 answers

### Answer by username_3 on 2017-07-11. Score: 4 | Accepted answer

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.


---

