Jaka jest złożoność (być może zwięzłego) Nurikabe?

Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości, a także pewne drobne ograniczenia w obszarze komórek „off” musi być podłączony i nie może zawierać żadnych sąsiadujących regionów 2x2). Strona Wikipedii ma bardziej wyraźne zasady i przykładowe łamigłówki.

Ogólnie rzecz biorąc, tego rodzaju łamigłówki wydają się być kompletne NP, a Nurikabe nie jest wyjątkiem; wpadają w NP, ponieważ samo rozwiązanie służy jako (weryfikowalny wielomianowo) świadek problemu. Ale w przeciwieństwie do większości podobnych zagadek, instancje Nurikabe mogą być zwięzłe: Sudoku na siatce wymaga rozwiązania Θ ( n ), aby można było je rozwiązać (jeśli oferowanych jest mniej niż n - 1 , wówczas nie ma możliwości rozróżnienia brakujących symboli) , Nonogramy oczywiście wymagają co najmniej jednego podanego dla każdego wiersza lub kolumny, a Saper musi mieć co najmniej $n\times n$$\Theta(n)$$n-1$ komórek lub będą komórki obok danego (i których statusu nie można zatem ustalić). Ale podczas gdy dawcy łamigłówki Nurikabe muszą sumować się doΘ(n2), możliwe jest, żeO(1)daje każdy z tych rozmiarów, tak żeΘ(log(n))bitów może wystarczyć do określenia łamigłówki Nurikabe o rozmiarzen- lub odwróceniu,kbitów może wystarczyć do określenia instancji Nurikabe o wykładniczym rozmiarze wk, co oznacza, że ​​jedyną gwarancją jest to, że problem leży w NEXP.$1\over16$$\Theta(n^2)$$\mathrm{O}(1)$$\Theta(\log(n))$$n$$k$$k$

Niestety, dowody twardości Nurikabe za Znalazłem wszystkie konstrukcje użytku z Givens o stałym rozmiarze, więc ich przypadki są wielomian w rozmiarze siatki zamiast logarytmiczna, i nie mogę wykluczyć, że wszystkie rozwiązywalne „zwięzłe „Puzzle Nurikabe mają dodatkową strukturę, dzięki czemu rozwiązania można opisać i zweryfikować równie zwięźle; na przykład jeden znany mi przykład układanki z 2 rozmiarami Θ ( n 2 ) prowadzi do obszarów zarówno na komórkach włączonych, jak i wyłączonych, z których każdy jest związkiem O ( 1 $\Theta(n^2)$$\Theta(n^2)$$\mathrm{O}(1)$prostokąty, a więc mają zwięzły opis. Czy ktoś wie o dodatkowych badaniach, które zostały przeprowadzone w tej zagadce, wykraczających poza podstawowy wynik kompletności NP, a w szczególności o jakichkolwiek dalszych wynikach złożoności dla możliwie zwięzłych przypadków?

(uwaga: pierwotnie zostało to zadane na stronie math.SE , ale nie ma tam jeszcze żadnych odpowiedzi i wydaje się, że jest to odpowiedni poziom badawczy dla tej witryny)

Wygląda na to, że naprawdę pytasz: czy Nurikabe jest w NP?

Nurikabe jest trudny do NP, ponieważ można zbudować gadżety wielomianowe, których można użyć do zredukowania problemu NP-zupełnego do problemu decyzyjnego Nurikabe. To właśnie robią Holzer, Klein i Kutrib, a także McPhail i Fix w swoim plakacie (oba wymienione w artykule w Wikipedii).

Obie grupy autorów zakładają, że problem jest trywialny w NP i pomijają kwestię członkostwa. Twój niepokój o zwięzłe przypadki wydaje się trafiony - nie sądzę, że problem dotyczy NP. Rozważ następujący sposób sformalizowania problemu decyzyjnego:

BINARY NURIKABE
Wejście: liczby całkowite min w formacie binarnym , reprezentujące tablicę Nurikabe, oraz listę potrójnych, z których każda wskazuje pozycję na tablicy i dodatnią liczbę całkowitą zapisaną w tej pozycji.
Pytanie: czy pozostałe pozycje na planszy można pokolorować dwoma kolorami, uwzględniając ograniczenia Nurikabe?

$m$$n$$mn$

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

Twoje pytanie brzmi zatem: czy istnieją certyfikaty wielomianowe dla wszystkich binarnych instancji Nurikabe, które można sprawdzić w czasie wielomianowym?

Nie jest dla mnie oczywiste, że takie certyfikaty koniecznie istnieją. Nie jest też oczywiste, w jaki sposób można udowodnić, że zwięzłe, szybko weryfikowalne certyfikaty nie mogą istnieć.

Jednak ograniczenie do unikalnych rozwiązań oznacza, że problem jest faktycznie US -hard, więc co-NP-trudne, a zatem mało prawdopodobne, aby być w NP. Chodzi o to, że jeśli ktoś uważa, że ​​„ma unikalne rozwiązanie” jako ograniczenie Nurikabe (w przeciwieństwie do pożądanej cechy przypadków, które są przedstawiane ludziom), nie wystarczy wykazać, że istnieje rozwiązanie, ale należy również wykazać, że żadne inne rozwiązania nie są możliwe. Sam ten wymóg wystarczy, aby upewnić się, że problem prawdopodobnie nie występuje w NP. Dotyczy to nawet jednoznacznej wersji problemu.

Podsumowując: jeśli rozluźnia się wymagania dotyczące unikalnych rozwiązań i określa się jednokrotnie rozmiar płyty, wówczas problem decyzyjny leży w NP; przy nietypowych rozwiązaniach i rozmiarze płytki binarnej nie jest jasne, czy problem decyzyjny dotyczy NP; a dzięki unikalnym rozwiązaniom problem decyzyjny jest trudny w Stanach Zjednoczonych i dlatego jest mało prawdopodobne, aby był w NP, zarówno dla kodowania wielkości płyty.