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

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. $NP$ $NP$ $NP$

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). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

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

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? $X$ $NP$ $NP$ $X$ $NP$

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 . $X$ $NP$ $X$

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 . $NP$ $NP$ $NP$

cc.complexity-theory unique-solution 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:

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

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

@ 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

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

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

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

$ASP$ $NP$

$NP$

Mohammad Al-Turkistany
fonte

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

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

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Sasho Nikolov

É 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

@ 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