La reconfiguración se preocupa por las relaciones entre las soluciones a una instancia de problema, donde la reconfiguración de una solución a otra es una secuencia de pasos de tal manera que cada paso produce una solución intermedia factible. El espacio de soluciones se puede representar como un , donde dos vértices representando soluciones son adyacentes si una se puede formar a partir de la otra en un solo paso. El trabajo en esta área abarca tanto preguntas estructurales (¿Está conectado el grafo de reconfiguración?) como algorítmicas (¿Cómo se puede encontrar la secuencia más corta de pasos entre dos soluciones?) Esta encuesta discute técnicas, resultados y futuras direcciones en el área.