O "Segundo X está NP-completo" implica "X está NP-completo"?

11

O problema do "segundo " é o problema de decidir a existência de outra solução diferente de uma determinada solução, por exemplo.X

Para algumas problemas -Complete, a segunda versão solução é -completo (decidir a existência de uma outra solução para o problema conclusão quadrado latino parcial), enquanto para outros é tanto trivial (Segunda NAE SAT) ou ele não pode ser -completo (Segundo ciclo hamiltoniano em gráficos cúbicos) sob conjectura de complexidade amplamente aceita. Estou interessado na direção oposta.N P N PNPNPNP

Assumimos natural problema onde há naturais verificador eficiente que verifica natural interessante relação onde é uma instância de entrada e é um curto testemunho de adesão em . Todas as testemunhas são indistinguíveis do verificador. A validade das testemunhas deve ser decidida executando o verificador natural e ele não tem conhecimento de nenhuma testemunha correta (os dois exemplos nos comentários são soluções por definição). X ( x , c ) x c x XNPX(x,c)xcxX

O "Segundo está NP-completo" implica " está NP-completo" para todos os problemas "naturais" ?X XXXX

Em outras palavras, existe algum problema "natural" que essa implicação falha? X. Ou equivalente,

Existe algum problema "natural" no e não é conhecido como completo, mas o seu segundo problema no é completo?N P N P X N PXNPNPXNP

EDIT : Graças aos comentários de Marzio, não estou interessado em contra-exemplos inventados. Estou interessado apenas em contra-exemplos naturais e interessantes para problemas NP-completos semelhantes aos acima. Uma resposta aceitável é ou uma prova da implicação acima ou um contra-exemplo "Segunda X problema", que é definido para natural, interessante, e bem conhecido problema .N P XXNPX

EDIT 2 : Graças à discussão frutífera com David Richerby, eu editei a pergunta à ênfase que o meu interesse é apenas em problemas naturais .X

EDIT 3 : motivação: Em primeiro lugar, a existência de tais implicação pode simplificar o provas de muitos -completeness problemas. Em segundo lugar, a existência da implicação vincula a complexidade de decidir a exclusividade da solução ao problema de decidir a existência de uma solução para os problemas de .N P N PNPNPNP

Mohammad Al-Turkistany
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Bjørn Kjos-Hanssen
Seu EDIT 3 e EDIT 1 parecem não estar alinhados. Se você deseja que este seja um resultado geral, útil para simplificar as provas de completude de NP, também não é possível dizer que deseja apenas contra-exemplos "não inventados". Além disso, seria útil ter uma definição de "natural / interessante", que não fosse baseada na opinião pessoal.
22619 Chris Jefferson

Respostas:

9

Não,

Considere o problema "Encontre um subconjunto de um conjunto de números inteiros S que soma 0".

Esse problema é trivial, pois é possível retornar o conjunto vazio.

No entanto, encontrar uma segunda solução após retornar o conjunto vazio é o conhecido problema de soma de subconjuntos, que é conhecido como NP-complete.

Chris Jefferson
fonte
4
A menos que você possa definir um problema "não natural", isso não importa. As pessoas definem centenas de variantes de problemas, como soma de subconjuntos e SAT.
91819 Chris Jefferson
5
@ Mohammad: Aqui está outro contra-exemplo; Deixo para você decidir se é natural ou não: um jogo de bimatriz sempre tem pelo menos um equilíbrio de Nash e é difícil para NP decidir se um jogo de bimatriz tem mais de um equilíbrio de Nash [Gilboa e Zemel, GEB 1989] . A construção usa uma fórmula SAT f e produz um jogo com um certo equilíbrio de Nash de forma conhecida que sempre existe, de modo que o jogo tenha um segundo equilíbrio se a fórmula f for satisfatória.
Rahul Savani
4
f:{0,1,2,,2n1}{0,1}f(0)=0f(2n1)=1kf(k)=0f(k+1)=1
3
NP completo não significa que todas as instâncias são difíceis, apenas algumas são. Existem muitas instâncias triviais de soma de subconjuntos (todos os problemas que contêm 1 e - 1 por exemplo) e muitos problemas fáceis de SAT (2 SAT por exemplo), mas o SAT como um todo ainda está completo com NP.
22619 Chris Jefferson
3
A resposta deve ser um subconjunto do conjunto de números inteiros S. {} é um subconjunto de S, pois o conjunto vazio é um subconjunto de todos os conjuntos. {φ} não é um subconjunto de S, como S não contém φ
Chris Jefferson
0

ASPNP

NP

Mohammad Al-Turkistany
fonte
1
Seu problema era se a completude NP da segunda solução implica a completude NP. O que eles mostram é mais fraco, eles exigem a completude do ASP, pois o completamento do NP não é suficiente, conforme indicado nos comentários da sua pergunta.
Domotorp # 30/14
2
Se alguém ler isso, esta resposta está errada. É fácil produzir um problema em que o Second X é NP-completo, mas X não é NP-completo. Por exemplo (como discutido nos comentários acima), o problema de encontrar um subconjunto de um conjunto de números inteiros igual a 0 é o Segundo X NP-completo, porque é NP-completo depois que rejeitamos a primeira solução fácil do conjunto vazio .
22420 Chris
2
ΠΠ[2]ΠΠΠ[2]Π[2]Π
Sasho Nikolov
4
É um pouco estranho que alguém faça uma pergunta, responda e aceite-a enquanto a discussão está em andamento.
Chandra Chekuri 8/10/19
1
@ MohammadAl-Turkistany Meu comentário foi dizer que sua resposta parece ter recuperado a lógica e não responde sua própria pergunta. Não disse nada sobre o exemplo de Chris (o que para mim parece bom, mas não quero entrar nesse argumento nos comentários).
Sasho Nikolov