Czy optymalne rozwiązanie kostki Rubika n-n-n-NP jest trudne?

Rozważ oczywiste uogólnienie Kostki Rubika . Czy NP jest trudne do obliczenia najkrótszej sekwencji ruchów, która rozwiązuje dany kodowany sześcian, czy też istnieje algorytm czasu wielomianowego? $n\times n\times n$

[Niektóre powiązane wyniki są opisane w moim ostatnim poście na blogu .]

— Jeffε
źródło

Sądzę, że dane wejściowe podano jako sześć n × n siatek wykonanych z {1,…, 6}. Czy problem dotyczy NP? Czy istnieje łatwa wielomianowa górna granica liczby ruchów w wersji n × n × n kostki Rubika?

— Tsuyoshi Ito

Dzięki za informację. Czy jest jakieś odniesienie?

— Tsuyoshi Ito

Czy problem staje się łatwiejszy, jeśli rozluźnia się: „Biorąc pod uwagę konfigurację, stwórz rozwiązanie, które wymaga co najwyżej Boskiej liczby (n, n, n) ruchów”? Tak właśnie działał algorytm rozwiązania Rubika. Nie szukali najkrótszych, ponieważ zajęłoby to zbyt długo.

— Aaron Sterling

Czy wiemy, że średnica dostępnej przestrzeni konfiguracji wynosi ?

Θ (n^{2})

$\Theta(n^2)$

— Andy Drucker,

@Andy: Ładne pytanie! („Jaka jest funkcja Boga dla n?”)

— Jeffε

Odpowiedzi:

Jeden z moich artykułów został właśnie wysłany do arXiv i dotyczy tego pytania: optymalne rozwiązanie Kostki Rubika jest NP-zupełne.

— Michaił Rudoy
źródło

Gratulacje!!

— Jeffε

Nowy artykuł Demaine, Demaine, Eisenstat, Lubiw i Winslow robi częściowy postęp w tej kwestii --- daje algorytm wielomianowy do optymalnego rozwiązywania kostek i pokazuje twardość do optymalnego rozwiązywania tego, co możesz nazwać „częściowo kolorowymi” sześcianami. Pokazuje także, że przestrzeń konfiguracyjna kostki ma średnicę . $n \times O(1) \times O(1)$ $\mathsf{NP}$ $n \times n \times n$ $\Theta(n^2/\log n)$

Słodkie!

Kolejne możliwe pytanie, które sugeruje ich praca: czy istnieje stała rodzina częściowo pokolorowanych kostek, po jednym dla każdej wartości , tak że optymalnym rozwiązaniem z danej konfiguracji jest -ciężko? $n \times n \times n$ $n$ $\mathsf{NP}$

— Andy Drucker
źródło

OK i jeszcze jedno pytanie: jaka jest złożoność ustalenia, czy dwa niestandardowe zabarwienie kostki są równoważne? (Dwa przypadki do rozważenia: całkowite lub częściowe zabarwienie).

n \times n \times n

$n \times n \times n$

— Andy Drucker,

W porządku, jeszcze jedno pytanie, a potem przestanę: czy istnieje wyraźna sekwencja konfiguracji wymagających rozwiązania ? (W artykule wykorzystano argument liczenia dla dolnej granicy).

Ω (n^{2} / \log n)

$\Omega(n^2/\log n)$

— Andy Drucker,

Może to być błąd, więc daj mi znać, jeśli go zauważysz.

Wydaje się, że odpowiedź brzmi „nie” lub przynajmniej, że problem ten jest zawarty w NP. Uzasadnienie tego jest bardzo proste. Chodzi o to, aby zbudować z innego pytania: „Czy możesz przejść między konfiguracją A a konfiguracją B w krokach S lub mniej?”

Najwyraźniej to nowe pytanie dotyczy NP, ponieważ istnieje algorytm do rozwiązania kostki z dowolnej możliwej do rozwiązania konfiguracji, a więc przejście przez stan rozwiązany wymaga tylko do przejścia między dowolnymi dwiema konfiguracjami . Ponieważ jest tylko wielomianowa liczba ruchów, zestaw ruchów pomiędzy dwiema konfiguracjami może być użyty jako świadek tego nowego pytania. $O(n^2)$ $O(n^2)$

Teraz, po pierwsze, jeśli wybierzemy konfigurację B jako stan rozwiązany, mamy problem z pytaniem, czy możliwe jest rozwiązanie kostki w krokach lub mniejszych, które są zawarte w NP. $S$

Teraz wybierzmy inną konfigurację dla B, którą nazwiemy co wymaga kroków do rozwiązania. Teraz, gdy pytamy, czy jest możliwe, aby uzyskać między konfiguracji A i w krokach lub mniej, znów mamy problem w NP z sekwencją ruchów jako świadka. Ponieważ jednak wiemy, że wymaga kroków do rozwiązania, wiemy, że jeśli możliwe jest przejście między A i w krokach , to wymaga co najmniej kroki, aby rozwiązać kostkę z konfiguracji A. $B_{hard}$ $n_{hard} \approx n^2$ $B_{hard}$ $S'$ $B_{hard}$ $n_{hard}$ $B_{hard}$ $S'$ $n_{hard} - S'$ $n \times n \times n$

Mamy więc świadków zarówno dla dolnej granicy kroków i dolnej granicy kroków do rozwiązania z konfiguracji A. Jeśli teraz jako minimalną liczbę ruchów wymaganych do rozwiązania kostki, zaczynając od konfiguracji A, to jeśli wybieramy dolną i górną granicę, aby były równe (tj. i ), to mamy świadka, że to rozwiązanie jest optymalne ( ze świadków dwóch NP problemy związane z granicami). $n_{hard} - S'$ $S$ $S_0$ $S' = n_{hard} - S_0$ $S = S_0$

Na koniec potrzebujemy sposobu na wygenerowanie . Prawdopodobnie potrzebujemy najtrudniejszej możliwej konfiguracji, ale ponieważ nie wiem, jak to znaleźć, sugeruję po prostu obrócenie co drugą płaszczyznę jeden raz wokół osi x, a następnie co czwartą płaszczyznę (utrzymywanie stałej płaszczyzny środkowej) za jednym razem oś Z. Wierzę, że prowadzi to do stanu, który wymaga kroków do rozwiązania. $B_{hard}$ $O(n^2)$

Tak więc nie mam pełnego konstruktywnego dowodu, ale każde optymalne rozwiązanie wymagające mniej niż wyraźnie ma świadka. Niestety, aby uchwycić wszystkie możliwe konfiguracje, potrzebujesz . $n_{hard}$ $n_{hard} = \mbox{God's number}(n)$

EDYCJA: Regularność konfiguracji Superflip sprawia, że wydaje się prawdopodobne, że wygenerowanie dla może być stosunkowo łatwe (tj. W P). $B_{hard}$ $n_{hard} = \mbox{God's number}(n)$

— Joe Fitzsimons
źródło

Zgrabny pomysł. Jednak nie zakłada to, że najkrótszą ścieżkę między dwoma oddalonymi od siebie punktami można przejść przez dowolny inny punkt. Odnosi się to wyraźnie do punktów na sferach (jeśli lecisz z bieguna północnego na biegun południowy, równie dobrze możesz latać Tahiti), ale czy jest jakiś powód, aby tak było w przypadku konfiguracji kostek Rubika?

— Peter Shor,

@Peter Shor: Cześć Peter, nie chciałem sugerować, że przejście przez od A do rozwiązania było najkrótszą ścieżką. W rzeczywistości takie podejście nie powinno działać w takim przypadku. Chodzi o to, że jeśli potrzeba co najmniej kroków, aby przejść z do rozwiązanej konfiguracji, to jeśli przejdziemy od do rozwiązania przez musimy przejść dalej od rozwiązanej konfiguracji , przed powrotem. (ciąg dalszy)

B_{h a r d}

$B_{hard}$

n_{h a r d}

$n_{hard}$

B_{h a r d}

$B_{hard}$

A

$A$

B_{h a r d}

$B_{hard}$

— Joe Fitzsimons

(ciąg dalszy) Zakładam, że A jest łatwiejsze do rozwiązania niż (mniej kroków). Ponieważ wiemy, że potrzeba co najmniej kroki, aby rozwiązać z , i wiemy, że możemy dostać się do w co najwyżej kroków od A potem mamy . Użyłem tego, aby uzyskać dolną granicę na , podczas gdy rozwiązywanie bezpośrednio daje górną granicę na .

B_{h a r d}

$B_{hard}$

n_{h a r d}

$n_{hard}$

B_{h a r d}

$B_{hard}$

B_{h a r d}

$B_{hard}$

n_{h a r d}

$n_{hard}$

n_{h a r d} - S^{'} \leq S_{0} \leq n_{h a r d} + S^{'}

$n_{hard}-S' \leq S_0 \leq n_{hard} + S'$

S_{0}

$S_0$

S_{0}

$S_0$

— Joe Fitzsimons,

@Joe: Źle mnie zrozumiałeś. Myślę, że twoje podejście działa dobrze tylko wtedy, gdy istnieje stosunkowo krótka ścieżka od B do rozwiązania, które przechodzi przez A. Nie wiem, czy to prawda dla kostki Rubika (więc nie mówię twoje podejście nie działa, wystarczy, że jest więcej rzeczy do udowodnienia).

_{h a r d}

$_\mathrm{hard}$

— Peter Shor,

@Joe: nie martw się publikowaniem na wpół przemyślanych odpowiedzi. Zrobiłem to samo (i nie jestem jedyny). I nie jestem przekonany, że takie podejście jest całkowicie bezwartościowe. Spodziewam się, że pokazanie, że dokładny dystans nie jest NP-trudny, nie zadziała, ale może to może powiedzieć coś o przybliżeniu go.

— Peter Shor,