Complexidade de encontrar uma segunda solução, dada a solução correta para um problema NP-completo

Estou procurando descobrir se existem resultados gerais ou exemplos relativos à completude de NP do problema de encontrar uma segunda solução para um problema de NP-completo. Mais precisamente, estou interessado em qualquer problema da seguinte forma:

Dada uma solução para uma instância de um problema NP-completo, existe uma solução para ?I S ' ≠ S $S$$I$$S' \neq S$$I$

Seria apreciado qualquer exemplo de problema desse tipo, NP-completo e não, ou trabalho geral, ou mesmo o que esse tipo de problema é chamado (para que eu possa fazer corretamente minha própria pesquisa) seria apreciado.

Outra pergunta aborda esse problema especificamente como referente ao SAT.

Espero não estar perguntando algo realmente básico; parece não haver exemplos em Garey e Johnson desse tipo de coisa.

Obrigado
Mark C.

A pergunta parece ter sido resolvida enquanto eu escrevia esta resposta, mas deixe-me postar minha resposta de qualquer maneira.

Yato e Seta [YS03] (ambos são meus colegas quando eu era estudante) propõem uma estrutura geral para provar a completude de NP desse tipo de problemas, onde são chamados de Outros problemas de solução ou ASPs e provar a completude de NP de os ASPs de muitos quebra-cabeças. Eles consideram uma noção restrita de reduções entre problemas de relação chamados reduções de ASP e mostram que a dureza NP dos ASPs é preservada sob reduções de ASP e mostram que muitas reduções conhecidas podem ser de fato vistas ou modificadas para reduções de ASP entre problemas de relações naturais.

[YS03] Takayuki Yato e Takahiro Seta. Complexidade e integridade de encontrar outra solução e sua aplicação em quebra-cabeças. Transações do IEICE sobre fundamentos de eletrônica, comunicações e ciências da computação , E86-A (5): 1052-1060, maio de 2003.

Dado um circuito Hamilton em um gráfico, encontre outro circuito hamilton. Isso é completo para o FNP. Curiosamente, existem problemas em que a "outra solução" é garantida por um argumento de paridade. Por exemplo: Dado um circuito de Hamilton em um gráfico tridimensional, encontre um segundo circuito de Hamilton. Observe que encontrar um circuito hamiltoniano no gráfico 3-regular é NP-completo. Encontrar o segundo, dado que o gráfico é hamiltoniano, está no PPA.

Veja minha postagem no blog para mais detalhes.

Laurent Juban, no Teorema da Dicotomia, para o Problema Generalizado de Satisbilidade Única, provou ser um teorema da dicotomia para Outro SAT definido como:

Entrada: uma fórmula proposicional e uma atribuição satisfatória (modelo) m de $\phi$$m$$\phi$

Pergunta: Existe outra atribuição satisfatória de diferente de m ?$\phi$$m$

Aqui está um trecho do artigo com o teorema da dicotomia:

Teorema 1 (Teorema da Dicotomia). Seja um conjunto finito de relações lógicas. Se S satisfizer uma das condições (1) a (6) abaixo, OUTRO SAT (S) e UNIQUE SAT (S) são solucionáveis ​​em tempo polinomial. De outro modo, outro sab (S) é N P -completo e ORIGINAL sab (S) é c o N P -Hard.$S$$S$$NP$$coNP$

1. Toda relação em é 0 válida e 1 válida.$S$

2. Toda relação em é complementar.$S$

3. Toda relação em é Horn.$S$

4. Toda relação em é anti-Horn.$S$

5. Toda relação em é afim.$S$

6. Toda relação em é 2SAT.$S$

Aqui está outro exemplo deste artigo: A COMPLEXIDADE COMPUTACIONAL DO RECONHECIMENTO DE CONJUNTOS CRÍTICOS :

$NP$

$G$

Pergunta : Existe outra partição de borda diferente da fornecida?

$NP$

$P$$P$

Pergunta : Existe outra conclusão em um quadrado latino?