What is the complexity of (possibly succinct) Nurikabe?

Question

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number indicating a region of connected 'on' cells of that size, and some minor constraints on the region of 'off' cells (it must be connected and can't contain any contiguous 2x2 regions). The Wikipedia page has more explicit rules and sample puzzles.

Generically, puzzles of this sort tend to be NP-complete, and Nurikabe is no exception; they fall into NP because the solution itself serves as a (polynomially-verifiable) witness to the problem. But unlike most similar puzzles, Nurikabe instances might be succinct: Sudoku on an $n\times n$ grid requires $\Theta(n)$ givens to be solvable (if less than $n-1$ givens are offered, then there's no way of distinguishing between the missing symbols), Nonograms obviously require at least one given for each row or column, and Minesweeper must have givens on at least $1\over16$ of the cells or there will be cells not next to a given (and whose status therefore can't be determined). But while the givens of a Nurikabe puzzle have to sum to $\Theta(n^2)$, it's possible to have $\mathrm{O}(1)$ givens each of that size, so that $\Theta(\log(n))$ bits might be enough to specify a Nurikabe puzzle of size $n$ - or inverting, $k$ bits may be enough to specify a Nurikabe instance of size exponential in $k$, meaning that the only guarantee is that the problem lies in NEXP.

Unfortunately, the proofs of Nurikabe's hardness I've found all use constructions with $\Theta(n^2)$ givens of constant size, so their instances are polynomial in the grid size rather than logarithmic, and I can't rule out that all solvable 'succinct' Nurikabe puzzles have additional structure such that solutions can be described and verified just as succinctly; for instance, the one example I know of a puzzle with 2 givens of size $\Theta(n^2)$ leads to regions of both on and off cells that are each the union of $\mathrm{O}(1)$ rectangles, and so have a succinct description of their own. Does anyone know of additional research that's been done into this puzzle beyond the basic NP-completeness result, and in particular any further complexity results for the possibly-succinct cases?

(note: this was originally asked over at math.SE, but there haven't been any answers there yet and this seems appropriately research-level for this site)

Answer 1

You seem to be really asking: is Nurikabe in NP?

Nurikabe is NP-hard, since one can build polynomial-size gadgets that can be used to reduce an NP-complete problem to a Nurikabe decision problem. This is what Holzer, Klein, and Kutrib do, and also McPhail and Fix in their poster (both referenced from the Wikipedia article).

Both groups of authors assume that the problem is trivially in NP, and wave away the question of membership. Your unease about succinct instances seems spot on -- I do not believe the problem is in NP. Consider the following way to formalise the decision problem:

BINARY NURIKABE
Input: integers m and n in binary, representing a Nurikabe board, and a list of triples, each indicating a position on the board and a positive integer written in that position.
Question: can the remaining board positions be coloured with two colours, respecting the Nurikabe constraints?

If $m$ and $n$ are instead specified in unary, then the decision problem of determining if there exists some (not necessarily unique) solution to a given Nurikabe instance is in NP, as a solution can be specified in at most $mn$ bits which is then polynomial in the input size.

In contrast, with a binary encoding, there is a problem (as you point out): if one has just one large constraint (say, the number $(m-2)(n-2)$ placed in the middle of the $m \times n$ board), then a solution will require $mn-1$ bits to represent, which is exponential in the size of the input $\Theta(\log\, m + \log\, n)$. This means that the problem is not in NP, unless small certificates always exist.

Your question then becomes: do there exist polynomial-sized certificates for all binary Nurikabe instances, which can be checked in polynomial time?

It is not obvious to me that such certificates necessarily exist. Nor is it obvious how one would go about proving that succinct, quickly-verifiable certificates cannot exist.

However, the restriction to unique solutions means that the problem is actually US-hard, so co-NP-hard, and therefore unlikely to be in NP. The point is that if one regards "has a unique solution" as a Nurikabe constraint (as opposed to a desirable feature of instances that are presented to humans), then it is not sufficient to demonstrate that there is a solution, but one must also demonstrate that no other solutions are possible. This requirement alone is then enough to ensure the problem is probably not in NP. This is true even for the unary version of the problem.

In summary: if one relaxes the unique solutions requirement, and specifies the board size in unary, then the decision problem is in NP; with non-unique solutions and binary board size, it is unclear whether the decision problem is in NP; and with unique solutions the decision problem is US-hard and therefore unlikely to be in NP, for either encoding of the board size.