<p>For some NP-complete problems, there's a SUCCINCT variant that's NEXP-complete.</p>

<p>An example is SUCCINCT HAMILTON PATH:</p>

<ul>
<li>A Boolean circuit with 2<i>n</i> inputs and one output represents a graph on 2<sup><i>n</i></sup> vertices. To determine if there is an edge between vertices <em>i</em> and <em>j</em>, encode <em>i</em> and <em>j</em> in <em>n</em> bits each, and feed their concatenation to the circuit: there is an edge between these vertices iff the output of the circuit is true. Given such a circuit, is there a Hamilton path in the graph represented by the circuit?</li>
</ul>

<p>Similarly, there's SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.</p>

<p>Reference</p>

<ul>
<li>Hana Galperin, and Avi Wigderson (1983), "Succinct representations of graphs", <em>Information and Control</em> 56:3, pp. 183–198.</li>
</ul>

CC BY-SA 4.0
2023-02-12T16:10:18.150Z
Let me note that Galperin&Wigderson only formulated the problem. NEXP-completeness was proven here:

Papadimitriou, Christos H., and Mihalis Yannakakis. "A note on succinct representations of graphs." Information and control 71, no. 3 (1986): 181-185.
Daniil Musatov
CC BY-SA 2.5
2010-11-24T16:40:17.410Z
2010-11-24T22:57:37.477Z
2010-11-24T22:57:37.477Z
Gareth Rees
<p>See <a href="http://arxiv.org/abs/0905.2419">http://arxiv.org/abs/0905.2419</a> by Gottesman and Irani.  This is a neat example.  Essentially, we are all used to the idea that constraint satisfaction can be an NP-complete problem (depending on geometry, etc...)  However, they consider a situation in which all the constraints are given beforehand and the only thing you are allowed to vary is how large the system is.  However, this turns out to be still hard if you encode the problem in the system size.  That is, the problem is specified by giving a string of N bits, giving the size of the system from 0 to 2^N-1.  So, the system size is exponentially larger than the input size.  They show that this is NEXP-complete (and that the quantum analogue is QMA_EXP-complete).</p>

CC BY-SA 2.5
2010-11-24T16:20:30.370Z
2010-11-24T16:20:30.370Z
matt hastings
<p>Let me start with the canonical one:</p>

<p>Given a non-deterministic Turing machine $M$ and an integer $n$ written in binary, is there are computation path of $M$ that accepts the empty string in at most $n$ steps?</p>

<p>Also NEXP-complete if $n$ is written in unary and we ask for at most $2^n$ steps.</p>

CC BY-SA 2.5
2010-11-24T08:10:23.490Z
2010-11-24T08:10:23.490Z
slimton
<p><strong>Inequivalence of regular expressions over $\cup$ (union), $\cdot$ (concatenation), and ${}^2$ (squaring)</strong>: Given two regular expressions do they represent different sets?</p>

<p>A regular expression is either </p>

<ul>
<li>$0$, </li>
<li>$1$, </li>
<li>$e\cup f$, </li>
<li>$e\cdot f$, or </li>
<li>$e^2$. </li>
</ul>

<p>These expressions represent the sets </p>

<ul>
<li>$L(0)=\{0\}$, </li>
<li>$L(1)=\{1\}$, </li>
<li>$L(e\cup f)=L(e)\cup L(f)$, </li>
<li>$L(e\cdot f)=\{ab\mid a\in L(e), b\in L(f)\}$, and </li>
<li>$L(e^2)=L(e\cdot e)$, </li>
</ul>

<p>respectively.</p>

<p>Note that if we allow the <a href="http://en.wikipedia.org/wiki/Kleene_star">Kleene star</a> (zero or more copies of an expression) as the forth operator (in addition to union, concatenation, and squaring), then the problem of recognizing whether two regular expressions represent different languages becomes <strong>EXPSPACE-complete</strong>.</p>

<p>L. J. Stockmeyer, A. R. Meyer, "<a href="http://dx.doi.org/10.1145/800125.804029">Word problems requiring exponential time</a>", 5th STOC, 1973.</p>

CC BY-SA 2.5
2010-11-25T13:00:35.727Z
2011-02-01T03:54:07.973Z
2011-02-01T03:54:07.973Z
Marcus Ritt
<p>SCHÖNFINKEL–BERNAYS SAT</p>

<ul>
<li>A formula in first-order logic belongs to the Schönfinkel–Bernays class of formulae if it can be expressed in the form $∃x_1 ∃x_2 \ldots ∀y_1 ∀y_2 \ldots φ$ (with $φ$ containing no quantifiers or function symbols). Given a Schönfinkel–Bernays formula, does it have a model?</li>
</ul>

<p>Reference</p>

<ul>
<li>H. R. Lewis (1980), "<a href="https://ac.els-cdn.com/0022000080900276/1-s2.0-0022000080900276-main.pdf?_tid=68c1d1ea-0d27-11e8-b6b0-00000aab0f6b&amp;acdnat=1518132543_a4153041d1a6d93d141092e724c2960c" rel="nofollow noreferrer">Complexity results for classes of quantificational formulas</a>", <em>Journal of Computer and System Sciences</em> 21, pp. 317–353.</li>
</ul>

CC BY-SA 3.0
2016-05-05T22:41:46.457Z
Is the converse (unsatisfiability) coNEXP-complete?
Nicola Gigante
CC BY-SA 3.0
2018-02-08T23:51:41.850Z
@BeniBela: These are formulas of first-order logic, so $φ$ can contain relation symbols (whose meaning needs to be specified by the model). See the reference. If the model is restricted to two elements, we have BINARY SCHÖNFINKEL–BERNAYS SAT, which [remains NEXP-complete](https://arxiv.org/pdf/1503.00362.pdf).
Gareth Rees
CC BY-SA 3.0
2010-11-24T23:07:02.507Z
2018-02-08T23:34:00.740Z
2018-02-08T23:34:00.740Z
Gareth Rees
<p>There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one available? As I assume there isn't, I open this question (is this supposed to be a community wiki? I don't know about this stuff).</p>

<p>Ideally the list should cover the different "types" of NEXP-complete problems, perhaps with some healthy redundancy to get the big picture, but without repeating itself too much. For example, it is good to have two or three different succinct versions of the same NP-complete problem as examples, if the succinct encodings come in slightly different forms. Not a dozen. A clean way to add the redundancy is by adding clauses of the form "Also NEXP-complete if BLAH". Clauses of the form "Remains NEXP-complete if the input graph has degree at most BLAH" are also welcome.</p>

<p>Finally, let me add a personal preference. I am most of all interested in complete problems of "algebraic" flavor, if there are any. For example, my favorite #P-complete problem is the permanent for its algebraic flavor. I hope the equality NEXP = MIP can also provide some nice algebraic NEXP-complete problem that I am not aware of.</p>

CC BY-SA 2.5
2010-11-24T08:11:39.260Z
Community Wiki!
Dave Clarke
CC BY-SA 2.5
2010-11-24T08:14:50.037Z
How does one turn it into a community wiki?
slimton
CC BY-SA 2.5
2010-11-24T08:23:39.900Z
Flag the post for moderator attention and ask them to make it CW.
Kaveh
CC BY-SA 2.5
2010-11-24T08:51:34.123Z
why NEXP ? i.e why not some other class ?
Suresh Venkat
CC BY-SA 2.5
2010-11-30T23:12:10.350Z
Notice that the class NEXP is sometimes also referred to as NEXPTIME. This might reveal additional results when using search engines.
Hermann Gruber
<cc.complexity-theory><complexity-classes><big-list><nexp>
NEXP-complete problems
slimton
# NEXP-complete problems

(Asked by: username_0 on 2010-11-24)

There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one available? As I assume there isn't, I open this question (is this supposed to be a community wiki? I don't know about this stuff).

Ideally the list should cover the different "types" of NEXP-complete problems, perhaps with some healthy redundancy to get the big picture, but without repeating itself too much. For example, it is good to have two or three different succinct versions of the same NP-complete problem as examples, if the succinct encodings come in slightly different forms. Not a dozen. A clean way to add the redundancy is by adding clauses of the form "Also NEXP-complete if BLAH". Clauses of the form "Remains NEXP-complete if the input graph has degree at most BLAH" are also welcome.

Finally, let me add a personal preference. I am most of all interested in complete problems of "algebraic" flavor, if there are any. For example, my favorite #P-complete problem is the permanent for its algebraic flavor. I hope the equality NEXP = MIP can also provide some nice algebraic NEXP-complete problem that I am not aware of.

**Tags:** cc.complexity-theory, complexity-classes, big-list, nexp
> **Comments:**
> **username_1**: Community Wiki!  
> **username_0**: How does one turn it into a community wiki?  
> **username_2**: Flag the post for moderator attention and ask them to make it CW.  
> **username_3**: why NEXP ? i.e why not some other class ?  
> **username_4**: Notice that the class NEXP is sometimes also referred to as NEXPTIME. This might reveal additional results when using search engines.  

---

## 5 answers

### Answer by username_5 on 2010-11-24. Score: 29

For some NP-complete problems, there's a SUCCINCT variant that's NEXP-complete.

An example is SUCCINCT HAMILTON PATH:

* A Boolean circuit with 2*n* inputs and one output represents a graph on 2*n* vertices. To determine if there is an edge between vertices *i* and *j*, encode *i* and *j* in *n* bits each, and feed their concatenation to the circuit: there is an edge between these vertices iff the output of the circuit is true. Given such a circuit, is there a Hamilton path in the graph represented by the circuit?

Similarly, there's SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Reference

* Hana Galperin, and Avi Wigderson (1983), "Succinct representations of graphs", *Information and Control* 56:3, pp. 183–198.

> **Comments:**
> **username_6**: Let me note that Galperin&Wigderson only formulated the problem. NEXP-completeness was proven here:  Papadimitriou, Christos H., and Mihalis Yannakakis. "A note on succinct representations of graphs." Information and control 71, no. 3 (1986): 181-185.  

---

### Answer by username_7 on 2010-11-24. Score: 17

See <http://arxiv.org/abs/0905.2419> by Gottesman and Irani. This is a neat example. Essentially, we are all used to the idea that constraint satisfaction can be an NP-complete problem (depending on geometry, etc...) However, they consider a situation in which all the constraints are given beforehand and the only thing you are allowed to vary is how large the system is. However, this turns out to be still hard if you encode the problem in the system size. That is, the problem is specified by giving a string of N bits, giving the size of the system from 0 to 2^N-1. So, the system size is exponentially larger than the input size. They show that this is NEXP-complete (and that the quantum analogue is QMA\_EXP-complete).


---

### Answer by username_0 on 2010-11-24. Score: 16

Let me start with the canonical one:

Given a non-deterministic Turing machine $M$ and an integer $n$ written in binary, is there are computation path of $M$ that accepts the empty string in at most $n$ steps?

Also NEXP-complete if $n$ is written in unary and we ask for at most $2^n$ steps.


---

### Answer by username_8 on 2010-11-25. Score: 16

**Inequivalence of regular expressions over $\cup$ (union), $\cdot$ (concatenation), and ${}^2$ (squaring)**: Given two regular expressions do they represent different sets?

A regular expression is either

* $0$,
* $1$,
* $e\cup f$,
* $e\cdot f$, or
* $e^2$.

These expressions represent the sets

* $L(0)=\{0\}$,
* $L(1)=\{1\}$,
* $L(e\cup f)=L(e)\cup L(f)$,
* $L(e\cdot f)=\{ab\mid a\in L(e), b\in L(f)\}$, and
* $L(e^2)=L(e\cdot e)$,

respectively.

Note that if we allow the [Kleene star](http://en.wikipedia.org/wiki/Kleene_star) (zero or more copies of an expression) as the forth operator (in addition to union, concatenation, and squaring), then the problem of recognizing whether two regular expressions represent different languages becomes **EXPSPACE-complete**.

L. J. Stockmeyer, A. R. Meyer, "[Word problems requiring exponential time](http://dx.doi.org/10.1145/800125.804029)", 5th STOC, 1973.


---

### Answer by username_5 on 2010-11-24. Score: 15

SCHÖNFINKEL–BERNAYS SAT

* A formula in first-order logic belongs to the Schönfinkel–Bernays class of formulae if it can be expressed in the form $∃x\_1 ∃x\_2 \ldots ∀y\_1 ∀y\_2 \ldots φ$ (with $φ$ containing no quantifiers or function symbols). Given a Schönfinkel–Bernays formula, does it have a model?

Reference

* H. R. Lewis (1980), "[Complexity results for classes of quantificational formulas](https://ac.els-cdn.com/0022000080900276/1-s2.0-0022000080900276-main.pdf?_tid=68c1d1ea-0d27-11e8-b6b0-00000aab0f6b&acdnat=1518132543_a4153041d1a6d93d141092e724c2960c)", *Journal of Computer and System Sciences* 21, pp. 317–353.

> **Comments:**
> **username_9**: Is the converse (unsatisfiability) coNEXP-complete?  
> **username_5**: @BeniBela: These are formulas of first-order logic, so $φ$ can contain relation symbols (whose meaning needs to be specified by the model). See the reference. If the model is restricted to two elements, we have BINARY SCHÖNFINKEL–BERNAYS SAT, which [remains NEXP-complete](https://arxiv.org/pdf/1503.00362.pdf).  

---

