Problem z Super Mario Galaxy

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?

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 $P$$s$$P$$v$$p$$\ell$$P$$P$

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 $P$$s$$v$$\ell$

Ł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 ) ℓ $P$$O(1)$$\ell$$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 £ -l$n$$[0,1]^2$$(0,1/2)$$(1,0)$$\lfloor \ell \rfloor$$\lfloor \ell \rfloor$$O(\log \ell)$czas przez wyszukiwanie wykładnicze, co stanowi wykładniczą poprawę w stosunku do naiwnego algorytmu. Czas wielomianem i zawsze osiągalne?$n$$\log \ell$

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

1. $P$$\pi$

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(\ell))$

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(\ell))$

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. :)