Complejidad de encontrar una segunda solución dada una solución correcta a un problema NP-completo

Estoy tratando de averiguar si hay resultados generales o ejemplos sobre la completitud NP del problema de encontrar una segunda solución a un problema NP-completo. Más precisamente, estoy interesado en cualquier problema de la siguiente forma:

Dada una solución a una instancia I de un problema NP-completo, ¿hay una solución S ′ ≠ S para I ?$S$$I$$S' \neq S$$I$

Se agradecería cualquier ejemplo de problemas de este tipo, tanto NP-completo como no, o trabajo general, o incluso lo que se llama este tipo de problema (para que pueda hacer mi propia búsqueda).

Otra pregunta aborda este problema específicamente en relación con el SAT.

Espero no preguntar algo realmente básico; no parece haber ningún ejemplo en Garey y Johnson de este tipo de cosas.

Gracias
Mark C.

La pregunta parece resolverse mientras escribía esta respuesta, pero déjame publicar mi respuesta de todos modos.

Yato y Seta [YS03] (ambos son mis colegas cuando era estudiante) proponen un marco general para demostrar la integridad de NP de este tipo de problemas, donde se denominan problemas de otra solución o ASP y prueban la integridad de NP de Los ASP de muchos rompecabezas. Consideran una noción restringida de reducciones entre problemas de relación llamadas reducciones ASP, y muestran que la dureza NP de los ASP se conserva bajo las reducciones ASP y muestran que muchas reducciones conocidas pueden verse o modificarse a las reducciones ASP entre problemas de relaciones naturales.

[YS03] Takayuki Yato y Takahiro Seta. Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas. Transacciones de IEICE sobre Fundamentos de Electrónica, Comunicaciones y Ciencias de la Computación , E86-A (5): 1052-1060, mayo de 2003.

Dado un circuito de Hamilton en un gráfico, encuentre otro circuito de Hamilton. Esto es completo de FNP. Curiosamente, hay problemas en los que la "otra solución" está garantizada por un argumento de paridad. Por ejemplo: dado un circuito de Hamilton en un gráfico de 3 regulares, encuentre un segundo circuito de Hamilton. Tenga en cuenta que encontrar un circuito hamiltoniano en un gráfico de 3 regulares es NP-completo. Encontrar el segundo, dado que el gráfico es hamiltoniano, está en PPA.

Vea mi publicación de blog para más detalles.

Laurent Juban en Teorema de dicotomía para el problema de satisfacción única generalizado demostró un teorema de dicotomía para otro SAT definido como:

Entrada: una fórmula proposicional y una asignación satisfactoria (modelo) m de $\phi$$m$$\phi$

Pregunta: ¿Hay otra asignación satisfactoria de diferente de m ?$\phi$$m$

Aquí un extracto del artículo con el teorema de la dicotomía:

Teorema 1 (teorema de dicotomía). Sea un conjunto finito de relaciones lógicas. Si S satisface una de las condiciones (1) a (6) a continuación, OTRO SAT (S) y UNIQUE SAT (S) son solucionables en tiempo polinómico. De lo contrario, OTRO SAT (S) es N P completo y SAT ÚNICO es c o N P duro.$S$$S$$NP$$coNP$

1. Toda relación en es 0-válida y 1-válida.$S$

2. Toda relación en es complementaria.$S$

3. Toda relación en es Horn.$S$

4. Toda relación en es anti-cuerno.$S$

5. Toda relación en es afín.$S$

6. Cada relación en es 2SAT.$S$

Aquí hay otro ejemplo de este artículo LA COMPLEJIDAD COMPUTACIONAL DE RECONOCER CONJUNTOS CRÍTICOS :

$NP$

$G$

Pregunta : ¿Hay otra partición de borde diferente de la dada?

$NP$

$P$$P$

Pregunta : ¿Hay otra terminación para un cuadrado latino?