Какова сложность (возможно, лаконичная) Nurikabe?

Nurikabe - это основанная на ограничениях головоломка, похожая на Minesweeper / Nonograms; числа помещаются в сетку, которая должна быть заполнена значениями включения / выключения для каждой ячейки, причем каждое число указывает область соединенных «включенных» ячеек этого размера, и некоторые незначительные ограничения на область «выключенных» ячеек (это должен быть подключен и не может содержать смежные области 2x2). На странице Википедии есть более четкие правила и примеры головоломок.

В общем, головоломки такого рода, как правило, являются NP-полными, и Nurikabe не является исключением; они попадают в NP, потому что само решение служит (проверяемым полиномом) свидетелем проблемы. Но, в отличие от большинства подобных головоломок, экземпляры Nurikabe могут быть краткими: судоку на сетке требует, чтобы Θ ( n ) было разрешено (если предлагается менее n - 1 , то нет никакого способа отличить отсутствующие символы) Нонограммы, очевидно, требуют, по крайней мере, одно значение для каждой строки или столбца, и тральщик должен иметь данные по крайней мере $n\times n$$\Theta(n)$$n-1$ из ячеек или там будут ячейки не рядом с данным (и чей статус поэтому не может быть определен). Ното время как данность головоломки Nurikabe должны подвести кthetas(п2), можно иметьO(1)Гивенс каждого такого размера, так чтоthetas(журнал(п))битов может быть достаточночтобы задать загадку Nurikabe размераnили инвертирования,kбитов может быть достаточно для указания экземпляра Nurikabe экспоненциального размера вk, что означает, что единственная гарантия состоит в том, что проблема заключается в NEXP.$1\over16$$\Theta(n^2)$$\mathrm{O}(1)$$\Theta(\log(n))$$n$$k$$k$

К сожалению, доказательства твердости Нурикабе, которые я нашел, используют все конструкции с данными постоянного размера, поэтому их экземпляры являются полиномиальными по размеру сетки, а не логарифмическими, и я не могу исключить, что все разрешимые 'лаконичны «Головоломки Nurikabe имеют дополнительную структуру, так что решения могут быть описаны и проверены так же кратко; например, один известный мне пример головоломки с двумя значениями размера Θ ( n 2 ) приводит к областям как включенных, так и выключенных ячеек, каждая из которых представляет собой объединение O ( 1 $\Theta(n^2)$$\Theta(n^2)$$\mathrm{O}(1)$прямоугольники и т.д. имеют краткое описание своих собственных. Кто-нибудь знает о дополнительных исследованиях, которые были сделаны в этой загадке за пределами основного результата NP-полноты, и, в частности, каких-либо дополнительных результатов сложности для возможных кратких случаев?

(примечание: об этом изначально спрашивали в math.SE , но ответов там пока не было, и это кажется подходящим уровнем исследования для этого сайта)

Вы, кажется, действительно спрашиваете: есть Nurikabe в NP?

Nurikabe является NP-сложным, так как можно создавать гаджеты полиномиального размера, которые можно использовать, чтобы свести NP-полную проблему к проблеме решения Nurikabe. Это то, что делают Хольцер, Кляйн и Кутриб, а также Макфейл и Фикс в их афише (обе ссылки из статьи в Википедии).

Обе группы авторов предполагают, что эта проблема тривиально в NP, и отбрасывают вопрос о членстве. Ваше беспокойство по поводу кратких примеров кажется очевидным - я не верю, что проблема в NP. Рассмотрим следующий способ формализации решения проблемы:

BINARY NURIKABE
Ввод: целые числа m и n в двоичном виде , представляющие доску Nurikabe, и список троек, каждый из которых указывает позицию на доске и положительное целое число, записанное в этой позиции.
Вопрос: можно ли раскрасить оставшиеся позиции доски двумя цветами, соблюдая ограничения Nurikabe?

$m$$n$$mn$

$(m-2)(n-2)$$m \times n$$mn-1$$\Theta(\log\, m + \log\, n)$

Тогда возникает вопрос: существуют ли сертификаты полиномиального размера для всех двоичных экземпляров Nurikabe, которые можно проверить за полиномиальное время?

Для меня не очевидно, что такие сертификаты обязательно существуют. Также не очевидно, как можно доказать, что краткие, быстро проверяемые сертификаты не могут существовать.

Тем не менее, ограничение на уникальные решения означает, что проблема на самом деле сложная для США , поэтому сопутствующая NP-сложная и, следовательно, вряд ли будет в NP. Дело в том, что если рассматривать «имеет уникальное решение» как ограничение Nurikabe (в отличие от желательной особенности экземпляров, представляемых людям), то недостаточно продемонстрировать, что существует решение, но нужно также продемонстрировать, что никакие другие решения не возможны. Одного этого требования тогда достаточно, чтобы убедиться, что проблема, вероятно, не в NP. Это верно даже для унарной версии проблемы.

В итоге: если ослабить требование уникальных решений и указать размер платы в одинарном виде, то проблема решения находится в NP; с неуникальными решениями и размером бинарной платы неясно, есть ли проблема решения в NP; и с уникальными решениями проблема решения сложна для США и, следовательно, вряд ли будет в NP, для любой кодировки размера платы.