37
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Community Wiki! $\endgroup$
    – Dave Clarke
    Nov 24, 2010 at 8:11
  • $\begingroup$ How does one turn it into a community wiki? $\endgroup$
    – slimton
    Nov 24, 2010 at 8:14
  • $\begingroup$ Flag the post for moderator attention and ask them to make it CW. $\endgroup$
    – Kaveh
    Nov 24, 2010 at 8:23
  • 5
    $\begingroup$ why NEXP ? i.e why not some other class ? $\endgroup$
    – Suresh Venkat
    Nov 24, 2010 at 8:51
  • 1
    $\begingroup$ Notice that the class NEXP is sometimes also referred to as NEXPTIME. This might reveal additional results when using search engines. $\endgroup$
    – Hermann Gruber
    Nov 30, 2010 at 23:12

5 Answers 5

Reset to default
29
$\begingroup$

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

An example is SUCCINCT HAMILTON PATH:

  • A Boolean circuit with 2n inputs and one output represents a graph on 2n 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.
Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Daniil Musatov
    Feb 12, 2023 at 16:10
17
$\begingroup$

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).

Improve this answer
$\endgroup$
16
$\begingroup$

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.

Improve this answer
$\endgroup$
16
$\begingroup$

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 (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", 5th STOC, 1973.

Improve this answer
$\endgroup$
15
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is the converse (unsatisfiability) coNEXP-complete? $\endgroup$
    – Nicola Gigante
    May 5, 2016 at 22:41
  • $\begingroup$ @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. $\endgroup$
    – Gareth Rees
    Feb 8, 2018 at 23:51

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.