Natknąłem się na otwarty problem postawiony przez Davida Eppsteina i jestem zainteresowany jego złożonością. Doszedł do wniosku, że jest kompletny NP.
Dane wejściowe: przez macierzy zer i jedynek, sekwencja zer i jedynek
Pytanie: Czy istnieje ścieżka przez sąsiednie wpisy macierzy, obejmujące każdy wpis macierzy dokładnie raz, a wartości pasują do podanej sekwencji?
Czy ktoś udowodnił, że problem jest naprawdę trudny?
Odpowiedzi:
W lutym ubiegłego roku otrzymałem wiadomość e-mail od hiszpańskiego studenta Nila Mamano, z dowodem, że ten problem jest w rzeczywistości NP-zupełny, poprzez redukcję ścieżki Hamiltonianów na wykresach siatkowych. Nie wiem, czy został jeszcze opublikowany. Redukcja zastępuje każdy wierzchołek wykresu siatki 2 x 2 blokami 1, a każdą krawędź, ścianę lub brakujący wierzchołek 2 x 2 blokiem zer. Sekwencja wejściowa naprzemiennie zmienia podsekwencje czterech zer i czterech zer tyle razy, ile potrzeba, aby pokryć wszystkie wierzchołki, a następnie wypełnia resztę sekwencji zerami. Aby dopasować sekwencję wejściową, ścieżka przez siatkę musi wyrównać podsekwencje czterech jedynek z 2x2 blokami jedynek z redukcji, tworząc ścieżkę hamiltonowską; jeśli taka ścieżka istnieje, to „