Juego de paridad
Se juega un juego de paridad en un gráfico dirigido de colores , donde cada nodo ha sido coloreado por una prioridad, uno de (generalmente) un número finito de números naturales . Dos jugadores, 0 y 1, mueven una ficha (única, compartida) a lo largo de los bordes del gráfico. El propietario del nodo en el que cae el token selecciona el nodo sucesor, lo que da como resultado una ruta (posiblemente infinita) , llamada juego.
El ganador de una jugada finita es el jugador cuyo oponente no puede moverse. El ganador de un juego infinito está determinado por las prioridades que aparecen en el juego. Normalmente, el jugador 0 gana una jugada infinita si la prioridad más grande que ocurre infinitamente a menudo en la jugada es par. De lo contrario, el jugador 1 gana. Esto explica la palabra "paridad" en el título.
Los juegos relacionados con los juegos de paridad se usaron implícitamente en la prueba de decidibilidad de Rabin de la teoría de segundo orden de n sucesores, donde se demostró la determinación de tales juegos. [2] El teorema de Knaster-Tarski conduce a una prueba relativamente simple de la determinación de los juegos de paridad. [3]
Además, los juegos de paridad están determinados sin historial. [3] [4] [5] Esto significa que si un jugador tiene una estrategia ganadora, entonces ese jugador tiene una estrategia ganadora que depende solo de la posición actual del tablero y no del historial de la jugada.
Resolver un juego de paridad jugado en un gráfico finito significa decidir, para una determinada posición inicial, cuál de los dos jugadores tiene una estrategia ganadora. Se ha demostrado que este problema está en NP y co-NP , más precisamente en UP y co-UP, [6] así como en QP (tiempo cuasipolinomial). [7] Sigue siendo una pregunta abierta si este problema de decisión se puede resolver en PTime .
Dado que los juegos de paridad se determinan sin historial, resolver un juego de paridad dado es equivalente a resolver el siguiente problema simple de teoría de gráficos. Dado un color finito dirigida gráfico bipartito con n vértices , y V de color con los colores de 1 a m , hay una función de elección de seleccionar un solo borde saliente de cada vértice de , de manera que el subgrafo resultante tiene la propiedad de que en cada ciclo el color más grande es uniforme.
