Problema de Super Mario Galaxy

140

Supongamos que Mario camina sobre la superficie de un planeta. Si comienza a caminar desde un lugar conocido, en una dirección fija, por una distancia predeterminada, ¿qué tan rápido podemos determinar dónde se detendrá?

ingrese la descripción de la imagen aquí

Más formalmente, supongamos que se nos da un politopo convexo en 3 espacios, un punto de partida en la superficie de , un vector de dirección (en el plano de alguna faceta que contiene ) y una distancia . ¿Qué tan rápido podemos determinar qué faceta de Mario se detendrá adentro? (Como punto técnico, suponga que si Mario entra en un vértice de , explota de inmediato; afortunadamente, esto casi nunca sucede).PsPvpPP

O si lo prefiere: suponga que se nos proporciona el politopo , el punto fuente y el vector de dirección de antemano. Después del preprocesamiento, ¿con qué rapidez podemos responder la pregunta para una distancia dada ?Psv

Es fácil seguir los pasos de Mario, especialmente si solo tiene facetas triangulares. Cada vez que Mario ingresa a una faceta a través de uno de sus bordes, podemos determinar en tiempo cuál de los otros dos bordes debe dejar pasar. Aunque el tiempo de ejecución de este algoritmo es solamente lineal en el número de cruces por borde, es sin límites en función del tamaño de entrada, ya que la distancia podría ser arbitrariamente grande que el diámetro de . ¿Podemos hacerlo mejor?PO(1)P

(En la práctica, la longitud de la ruta no es realmente ilimitada; hay un límite superior global en términos de la cantidad de bits necesarios para representar la entrada. Pero insistir en entradas enteras plantea algunos problemas numéricos bastante desagradables: ¿cómo calculamos exactamente dónde detener? - así que ceñámonos a las entradas reales y a la aritmética real exacta).

¿Se sabe algo no trivial sobre la complejidad de este problema?

Actualización: a la luz del comentario de julkiewicz, parece claro que un tiempo de ejecución de RAM real limitado únicamente en términos de (la complejidad del politopo) es imposible. Considere el caso especial de una unidad cuadrada de dos lados , con Mario comenzando en y caminando en dirección . Mario se detendrá en el frente o en la parte posterior de la plaza dependiendo de la paridad del número entero . No podemos calcular la función de piso en un tiempo constante en la memoria RAM real, a menos que estemos contentos equiparar PSPACE y P . Pero podemos calcular enn[0,1]2(0,1/2)(1,0)O(log)tiempo por búsqueda exponencial, que es una mejora exponencial sobre el algoritmo ingenuo. ¿Es el tiempo polinomio en y siempre se puede lograr?nlog

Jeffε
fuente
55
Pensé en un problema más simple, es decir: tenemos un polígono simple y un haz de luz que viaja desde un punto dado. Cuando llega a un borde, simplemente se refleja. Queremos saber dónde terminará el haz su recorrido después de la distancia dada. Podría (casi) reducirse a este, tomando un politopo que es un prisma de una altura muy pequeña con los lados superior e inferior en forma de un polígono dado. Quizás resolver esto primero podría ayudar.
julkiewicz
3
"[T] ime polynomial in ny log l" no tiene sentido para mí. Si depende de l, también debe depender de las coordenadas de P, y si agrega el registro de todos los números en la entrada, ese es exactamente el número de bits necesarios para representar la entrada cuando las coordenadas de entrada están restringidas a enteros. Creo que está viendo la complejidad del tiempo en una RAM real cuando la entrada se da como una cadena de bits.
Tsuyoshi Ito
44
Incluso decidir si Mario alguna vez golpea un vértice (independiente de ) parece difícil. Creo que aquí nos encontramos con muchas incógnitas en el área de la dinámica del billar.
Joseph O'Rourke
2
No está realmente relacionado, pero este documento sobre NP-Completeness de Super Mario es realmente sorprendente: arxiv.org/pdf/1203.1895v1.pdf
Lamine
10
"Quizás es por eso que tiene una calificación tan alta", dijo alguien completamente apático sobre la teoría de la complejidad.
Jeffε

Respuestas:

7

Este problema es muy muy difícil. Podríamos simplificarlo para que sea más fácil, de la siguiente manera.

  1. Podemos suponer que la suma del ángulo sobre cada vértice del politopo es un múltiplo racional de . Esto elimina la mayoría de los "politopos", pero todavía hay muchas posibilidades interesantes: por ejemplo, los sólidos platónicos.πPπ

  2. Podemos suponer que el politopo no es verdaderamente tridimensional, sino que es el "doble" de un polígono; esto se parece un poco a una funda de almohada. Podemos simplificar aún más y suponer que el polígono tiene lados iguales y paralelos; por ejemplo un cuadrado, como en el juego Astroids.

Si hacemos ambas suposiciones, entonces hay una gran teoría. (Encontrar un algoritmo para el cuadrado es un ejercicio difícil que involucra la expansión de fracción continua del ángulo de la trayectoria de Mario. Es posible lograr un resultado similar para el octágono regular pero más difícil. Las soluciones para el cuadrado y el octágono implican pensar en cómo codificar eficientemente "secuencias de corte para una geodésica en una superficie de traducción". La mayoría de los otros polígonos racionales conducirán rápidamente a problemas abiertos.) Una referencia inicial, que incluye una referencia adicional a la discusión de Caroline Series sobre el toro cuadrado, son estas diapositivas de Diana Davis.O(log())

Si no asumimos la racionalidad, pero asumimos que el politopo es el doble de un polígono, entonces estamos discutiendo la teoría de "cortar secuencias en billares irracionales". Parece que esencialmente no se sabe nada aquí; por ejemplo, vea la oración final de esta charla de Corinna Ulcigrai.

Si no hacemos ninguna suposición, bueno, no puedo pensar en nada en la literatura.

Finalmente, supongo que hay una solución para el problema de Super Mario Galaxy para los sólidos platónicos. Este es un buen problema para un estudiante graduado que se inicia en el billar racional. Por ejemplo, el caso del dodecaedro "debería" seguir la tesis de Diana Davis. (Pero comience con el tetraedro, que se derivará de un análisis de secuencias de corte para el toro hexagonal).O(log())

Sam Nead
fuente
0

Creo que puedes hacerlo mejor que lineal. Soy nuevo en informática teórica, así que perdóname si esto es basura.

Algunas ideas generales (de valor variable):

  • Si le damos un símbolo a cada faceta, la órbita de Mario sobre ellas se puede describir como una cadena, donde el símbolo final de la cadena es la respuesta.
  • Podemos suponer sin pérdida de generalidad que Mario comienza en un borde (solo camina hacia atrás y extiende l hasta el borde)
  • El espacio 2D de las posiciones iniciales y los ángulos se puede dividir en el siguiente borde. Entonces, comenzando en el borde a, x unidades desde la parte inferior, con un ángulo de a, terminamos en el borde V después de cruzar una faceta.
  • En ese punto, estamos en otro borde con otra orientación, por lo que podemos llamar a la función de forma recursiva para subdividir el espacio en particiones de cadenas de 2 símbolos, etc.
  • En este punto, hemos terminado si decimos que el espacio debe ser discretizado para que el problema se implemente en una TM. Eso significa que cada órbita debe ser periódica porque solo hay finitos puntos en el planeta discreto. Podemos calcular la función descrita anteriormente hasta que tengamos órbitas para todos los puntos de partida y almacenemos esta información. Entonces el problema se convierte en O (1).
  • Tal vez sea un poco policía. Algunas búsquedas en Google me dicen que casi todas las órbitas de billar dentro de los polígonos convexos racionales son periódicas (es decir, las órbitas periódicas son densas). Entonces, para un (digamos) planetas cuadrados, el mismo enfoque podría funcionar.
  • Otro enfoque sería considerar el sistema como un generador / reconocedor de cadenas (nuevamente asignando a cada faceta su propio símbolo). Si el idioma tiene una clase de complejidad conocida, esa es su respuesta. Si amplía la familia de politopos a formas no convexas y de cualquier dimensión, puede capturar una clase muy amplia de idiomas.

Esto realmente no constituye una respuesta, pero necesito volver al trabajo. :)

Peter
fuente
10
"En este punto, terminamos si decimos que el espacio debe ser discretizado para que el problema se implemente en una TM. Eso significa que cada órbita debe ser periódica porque solo hay finitos puntos en el planeta discretizado". Acaba de destruir la parte interesante del problema. Yo no quiero suponer que la entrada es discreta; Quiero resolver el problema continuo real, aunque esto requiere una computadora ideal que pueda hacer aritmética real exacta en tiempo constante. En particular, el camino de Mario no necesita tocar un vértice.
Jeffε
Pensé que eso era demasiado fácil. Podrías hacer la versión continua en una máquina finita, siempre y cuando el punto de partida y el planeta puedan describirse de manera finita. Puede representar la ruta simbólicamente (estilo matemático). Solo necesita evaluar ciertos límites para encontrar en qué faceta termina. Si puede probar que el camino es casi seguro periódicamente (como lo es para el billar en polígonos convexos racionales), aún puede aplicar el mismo truco, pero el resultado No sería muy práctico.
Peter
12
Por desgracia, las geodésicas genéricas en poliedros genéricos no son periódicas. (En particular, los polígonos genéricos no son racionales).
Jeffε
Usted (Peter), creo, se refiere al artículo "Las órbitas periódicas de billar son densas en polígonos racionales". Esto no significa que las rutas periódicas sean genéricas en los polígonos racionales. De hecho, solo hay muchos caminos periódicos contables (hasta el paralelismo), por lo que no tienen posibilidades de ser genéricos.
Sam Nead
De hecho, en un polígono "Veech" los caminos "únicamente ergódicos" son una medida completa. Entonces, si enviamos a Mario en una dirección aleatoria, él (a) nunca golpeará un vértice (como dice Jeffe en la declaración del problema), (b) su camino nunca se cerrará, y (c) a gran escala, la secuencia de las caras visitadas se verán al azar (debido a una propiedad de "mezcla débil"). Esto no sugiere una respuesta negativa al problema - por ejemplo, los dígitos de pi también miran al azar ...
Sam Nead