Reconfiguración

En matemáticas discretas y ciencias de la computación teórica , los problemas de reconfiguración son problemas computacionales que implican la alcanzabilidad o conectividad de espacios de estados .

Aquí, un espacio de estados es un conjunto discreto de configuraciones de un sistema o soluciones de un problema combinatorio, llamadas estados, junto con un conjunto de movimientos permitidos que vinculan un estado con otro. Los problemas de reconfiguración pueden plantear las siguientes preguntas:

• Para una clase de problemas determinada, ¿el espacio de estados siempre está conectado? Es decir, ¿es posible transformar cualquier par de estados en otro mediante una secuencia de movimientos? Si no es así, ¿cuál es la complejidad computacional de determinar si el espacio de estados para un problema concreto está conectado?
• ¿Cuál es el diámetro del espacio de estados, el número más pequeño D tal que cualquier par de estados se puede transformar uno en el otro con como máximo D movimientos?
• Dados dos estados, ¿cuál es la complejidad de determinar si se pueden transformar uno en el otro, o de encontrar la secuencia más corta de movimientos para transformar uno en otro?
• Si los movimientos se eligen aleatoriamente con una distribución de probabilidad cuidadosamente seleccionada, de modo que la cadena de Markov resultante converja a una distribución uniforme discreta , ¿cuántos movimientos se necesitan en un paseo aleatorio para asegurar que el estado al final del paseo tenga una distribución casi uniforme? Es decir, ¿cuál es el tiempo de mezcla de la cadena de Markov ?

Algunos ejemplos de problemas estudiados en la reconfiguración son:

• Juegos o rompecabezas como el rompecabezas de 15 piezas o el cubo de Rubik . Este tipo de rompecabezas a menudo se puede modelar matemáticamente utilizando la teoría de grupos de permutación , lo que lleva a algoritmos rápidos para determinar si los estados están conectados; sin embargo, encontrar el diámetro del espacio de estados o el camino más corto entre dos estados puede ser más difícil. Por ejemplo, para${\displaystyle n\times n\times n}$Versión del Cubo de Rubik, el diámetro del espacio de estados es${\displaystyle \Theta (n^{2}/\log n)}$y la complejidad de encontrar las soluciones más cortas es desconocida, pero para una versión generalizada del rompecabezas (en la que algunas caras del cubo no están etiquetadas) es NP-difícil . ^{[ 1 ]} Otros rompecabezas de reconfiguración como Sokoban pueden modelarse como reconfiguración de tokens pero carecen de una estructura de teoría de grupos. Para tales problemas, la complejidad puede ser mayor; en particular, probar la alcanzabilidad para Sokoban es PSPACE-completo . ^{[ 2 ]}
• Distancia de rotación en árboles binarios y problemas relacionados de distancia de volteo en grafos de volteo . Una rotación es una operación que cambia la estructura de un árbol binario sin afectar el orden de izquierda a derecha de sus nodos, a menudo utilizada para reequilibrar árboles de búsqueda binaria . La distancia de rotación es el número mínimo de rotaciones necesarias para transformar un árbol en otro. El mismo espacio de estados también modela las triangulaciones de un polígono convexo y los movimientos que "voltean" una triangulación en otra eliminando una diagonal del polígono y reemplazándola por otra; problemas similares también se han estudiado en otros tipos de triangulación. Se conoce la distancia de rotación máxima posible entre dos árboles con un número dado de nodos, ^{[ 3 ]} pero sigue siendo un problema abierto si la distancia de rotación entre dos árboles arbitrarios se puede encontrar en tiempo polinomial . ^{[ 4 ]} Los problemas análogos para la distancia de volteo entre triangulaciones de conjuntos de puntos o polígonos no convexos son NP-difíciles. ^{[ 5 ] [ 6 ]}
• Reconfiguración de coloraciones de grafos . Los movimientos considerados para la reconfiguración de coloraciones incluyen cambiar el color de un solo vértice o intercambiar los colores de una cadena de Kempe . Cuando el número de colores es al menos dos más la degeneración de un grafo, el espacio de estados de las recoloraciones de un solo vértice es conexo, y la conjetura de Cereceda sugiere que tiene diámetro polinomial. Para menos colores, algunos grafos tienen espacios de estados desconectados. Para 3-coloraciones, probar la conectividad global del espacio de estados de recoloración de un solo vértice es co-NP-completo , ^{[ 7 ]} pero cuando dos coloraciones se pueden reconfigurar entre sí, la secuencia de reconfiguración más corta se puede encontrar en tiempo polinomial. ^{[ 8 ]} Para más de tres colores, la reconfiguración de un solo vértice es PSPACE-completa. ^{[ 9 ]}
• La lógica de restricciones no determinista es un problema combinatorio sobre orientaciones de grafos cúbicos cuyas aristas están coloreadas de rojo y azul. En un estado válido del sistema, cada vértice debe tener al menos una arista azul o al menos dos aristas que lleguen a él. Un movimiento en este espacio de estados invierte la orientación de una sola arista, preservando estas restricciones. Es PSPACE -completo comprobar si el espacio de estados resultante está conectado o si dos estados son alcanzables entre sí, incluso cuando el grafo subyacente tiene un ancho de banda limitado . ^{[ 10 ]} Estos resultados de dificultad se utilizan a menudo como base para reducciones que demuestran que otros problemas de reconfiguración, como los que surgen de juegos y rompecabezas, también son difíciles. ^{[ 11 ]}

• Recursos de reconfiguración combinatoria (incluida una bibliografía no exhaustiva )