NEXP-complete problems 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.
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.