Problem z Super Mario Galaxy

140

Załóżmy, że Mario chodzi po powierzchni planety. Jeśli zacznie chodzić ze znanego miejsca, w ustalonym kierunku, na określoną odległość, jak szybko możemy ustalić, gdzie się zatrzyma?

wprowadź opis zdjęcia tutaj

Bardziej formalnie, załóżmy, że otrzymujemy wypukły politop w 3-przestrzeni, punkt początkowy na powierzchni , wektor kierunku (w płaszczyźnie pewnej ścianki zawierającej ) i odległość . Jak szybko możemy ustalić, który aspekt Mario zatrzyma się w środku? (Z technicznego punktu widzenia załóżmy, że jeśli Mario wejdzie w wierzchołek , natychmiast eksploduje; na szczęście prawie nigdy tak się nie dzieje.)s P v p P PPsPvpPP

Lub jeśli wolisz: załóżmy, że otrzymamy wcześniej polytop , punkt źródłowy i wektor kierunku . Po wyprzedzającym, jak szybko możemy odpowiedzieć na pytanie dla danej odległości ?s v Psv

Łatwo jest wyśledzić ślady Mario, szczególnie jeśli ma tylko trójkątne ścianki. Ilekroć Mario wejdzie w aspekt przez jedną z jego krawędzi, możemy w czasie określić, przez którą z dwóch pozostałych krawędzi musi przejść. Chociaż czas działania tego algorytmu jest linią prostą w szeregu przejściach krawędzi, jest nieograniczona w funkcji wielkości wejściowych, ponieważ odległość może być dowolnie większy niż średnica . Czy możemy zrobić lepiej?O ( 1 ) PPO(1)P

(W praktyce długość ścieżki nie jest właściwie nieograniczona; istnieje górna granica globalna pod względem liczby bitów potrzebnych do reprezentacji danych wejściowych. Ale naleganie na liczby całkowite rodzi pewne dość nieprzyjemne problemy numeryczne - Jak obliczyć dokładnie, gdzie zatrzymać? - więc trzymajmy się prawdziwych danych wejściowych i dokładnej prawdziwej arytmetyki).

Czy jest coś nietypowego na temat złożoności tego problemu?

Aktualizacja: W świetle komentarza Julkiewicza wydaje się jasne, że czas działania rzeczywistej pamięci RAM ograniczony wyłącznie w kategoriach (złożoność polytopa) jest niemożliwy. Rozważ szczególny przypadek dwustronnego kwadratu jednostkowego , w którym Mario zaczyna od i idzie w kierunku . Mario zatrzyma się z przodu lub z tyłu kwadratu w zależności od parzystości liczby całkowitej . Nie możemy obliczyć funkcję piętro w stałym czasie rzeczywistym na RAM, chyba że jesteśmy szczęśliwi zrównując PSPACE i P . Ale możemy obliczyć w[ 0 , 1 ] 2 ( 0 , 1 / 2 ), ( 1 , 0 ) O ( log ) n log £ -ln[0,1]2(0,1/2)(1,0)O(log)czas przez wyszukiwanie wykładnicze, co stanowi wykładniczą poprawę w stosunku do naiwnego algorytmu. Czas wielomianem i zawsze osiągalne?nlog

Jeffε
źródło
5
Pomyślałem o prostszym problemie: mamy prosty wielokąt i wiązkę światła podróżującą z danego punktu. Kiedy osiągnie krawędź, zostaje po prostu dublowane. Chcemy wiedzieć, gdzie wiązka zakończy swój skok po danej odległości. Można go (prawie) sprowadzić do tego, przyjmując polytop, który jest pryzmatem o bardzo małej wysokości z górnymi i dolnymi bokami w kształcie danego wielokąta. Może rozwiązanie tego pierwszego może pomóc.
julkiewicz
3
„[T] im wielomian in i log l” nie ma dla mnie sensu. Jeśli zależy to od l, musi również zależeć od współrzędnych P, a jeśli dodasz log wszystkich liczb na wejściu, to jest dokładnie liczba bitów potrzebna do przedstawienia danych wejściowych, gdy współrzędne wejściowe są ograniczone do liczb całkowitych. Myślę, że patrzysz na złożoność czasu na prawdziwej pamięci RAM, gdy dane wejściowe są podawane jako ciąg bitowy.
Tsuyoshi Ito
4
Nawet podjęcie decyzji, czy Mario kiedykolwiek uderzy w wierzchołek (niezależnie od ), wydaje się trudne. Myślę, że natknęliśmy się tutaj na wiele niewiadomych w dziedzinie dynamiki bilarda.
Joseph O'Rourke
2
Nie bardzo powiązane, ale ten artykuł o NP-Kompletności Super Mario jest naprawdę niesamowity: arxiv.org/pdf/1203.1895v1.pdf
Lamine
10
„Może dlatego jest tak wysoko oceniany”, powiedział ktoś całkowicie apatyczny wobec teorii złożoności.
Jeffε

Odpowiedzi:

7

Ten problem jest bardzo, bardzo trudny. Możemy to uprościć, aby ułatwić, w następujący sposób.

  1. Pπ

  2. Możemy założyć, że polytop nie jest tak naprawdę trójwymiarowy, ale jest „podwójnym” wielokąta; to wygląda trochę jak poszewka na poduszkę. Możemy jeszcze bardziej uprościć i założyć, że wielokąt ma równe i równoległe boki; na przykład kwadrat, jak w grze Astroids.

O(log())

Jeśli nie zakładamy racjonalności, ale zakładamy, że polytop jest podwójną częścią wielokąta, wówczas dyskutujemy na temat teorii „wycinania sekwencji w irracjonalnym bilardie”. Wydaje się, że w zasadzie nic tu nie wiadomo; na przykład patrz ostatnie zdanie tej wypowiedzi Corinny Ulcigrai.

Jeśli nie przyjmiemy żadnego założenia, cóż, nie mogę nic wymyślić w literaturze.

O(log())

Sam Nead
źródło
0

Myślę, że możesz zrobić lepiej niż liniowy. Jestem nowy w informatyce teoretycznej, więc wybacz mi, jeśli to śmieci.

Kilka ogólnych pomysłów (o różnej wartości):

  • Jeśli nadamy każdemu aspektowi symbol, orbitę Mario nad nim można opisać jako ciąg, gdzie ostatecznym symbolem w ciągu jest odpowiedź.
  • Możemy założyć bez utraty ogólności, że Mario zaczyna na krawędzi (po prostu cofnij się i przedłuż l do krawędzi)
  • Przestrzeń 2D pozycji początkowych i kątów można podzielić na następną krawędź. Więc zaczynając od krawędzi a, x jednostek od dołu, pod kątem a, kończymy na krawędzi V po przekroczeniu jednego aspektu.
  • W tym momencie jesteśmy na innej krawędzi z inną orientacją, więc możemy wywoływać funkcję rekurencyjnie, aby podzielić przestrzeń na partycje ciągów 2-symbolowych i tak dalej.
  • W tym momencie jesteśmy skończeni, jeśli powiemy, że przestrzeń musi być dyskretyzowana, aby problem mógł zostać zaimplementowany na TM. Oznacza to, że każda orbita musi być okresowa, ponieważ na dyskretyzowanej planecie jest tylko wiele punktów. Możemy obliczyć funkcję opisaną powyżej, dopóki nie znajdziemy orbit dla wszystkich punktów początkowych i nie zapiszemy tych informacji. Wtedy problemem staje się O (1).
  • Może to trochę głupiec. Niektórzy googling mówią mi, że prawie wszystkie orbity bilardowe wewnątrz racjonalnych wypukłych wielokątów są okresowe (tj. Okresowe orbity są gęste). Tak więc dla (powiedzmy) planet kwadratowych to samo podejście może działać.
  • Innym podejściem byłoby rozważenie systemu jako generatora / rozpoznawania ciągów znaków (ponownie poprzez przypisanie każdemu aspektowi własnego symbolu). Jeśli język ma znaną klasę złożoności, to twoja odpowiedź. Jeśli poszerzysz rodzinę polytopów do niewypukłych i dowolnego wymiaru, możesz uchwycić bardzo szeroką klasę języków.

To naprawdę nie stanowi odpowiedzi, ale muszę wrócić do pracy. :)

Piotr
źródło
10
„W tym momencie jesteśmy skończeni, jeśli powiemy, że przestrzeń musi zostać zdyskretyzowana, aby problem mógł zostać zaimplementowany na TM. Oznacza to, że każda orbita musi być okresowa, ponieważ na dyskretnej planecie jest tylko wiele punktów”. Właśnie zniszczyłeś interesującą część problemu. Ja nie chce zakładać wejście jest dyskretny; Chcę rozwiązać rzeczywisty ciągły problem, mimo że wymaga to idealnego komputera, który potrafi wykonywać dokładną arytmetykę w stałym czasie. W szczególności ścieżka Mario nigdy nie musi dotykać wierzchołka.
Jeffε
Uznałem, że to było zbyt łatwe. Możesz wykonać ciągłą wersję na skończonej maszynie, o ile można dokładnie opisać punkt początkowy i planetę. Możesz po prostu reprezentować ścieżkę symbolicznie (w stylu matematycznym). Musisz tylko ocenić pewne granice, aby znaleźć aspekt, w którym się znajdziesz. Jeśli możesz udowodnić, że ścieżka jest prawie na pewno okresowa (tak jak w przypadku bilarda na racjonalnych wypukłych wielokątach), nadal możesz zastosować tę samą sztuczkę, ale wynik nie byłoby bardzo praktyczne.
Peter
12
Niestety, ogólna geodetyka na ogólnych wielościanach nie jest okresowa. (W szczególności ogólne wielokąty nie są racjonalne.)
Jeffε
Myślę, że ty (Peter) odwołujesz się do artykułu „Okresowe orbity bilardowe są gęste w racjonalnych wielokątach”. Ten sposób nie oznacza, że ścieżki są okresowe generycznych w racjonalnych wielokątów. W rzeczywistości można policzyć tylko wiele ścieżek okresowych (aż do równoległości), więc nie mają one szans na bycie rodzajowym.
Sam Nead,
W rzeczywistości w wielokącie „Veech” ścieżki „wyjątkowo ergodyczne” są w pełni miarą. Jeśli więc wyślemy Mario, jest to losowy kierunek, (a) nigdy nie uderzy w wierzchołek (jak mówi Jeffe w opisie problemu), (b) jego ścieżka nigdy się nie zamknie, i (c) w dużych skalach sekwencja odwiedzane twarze będą wyglądać losowo (ze względu na właściwość „słabego mieszania”). To nie sugeruje negatywnej odpowiedzi na problem - na przykład cyfry pi również wyglądają losowo ...
Sam Nead