Quando "X é NP-completo" implica "#X é # P-completo"?

29

Deixe denotar um problema (de decisão) no NP e deixe # denotar sua versão de contagem.XX

Em que condições é sabido que "X é NP-completo" "#X é # P-completo"?

É claro que a existência de uma redução parcimoniosa é uma dessas condições, mas isso é óbvio e a única condição de que tenho conhecimento. O objetivo final seria mostrar que nenhuma condição é necessária.

Falando formalmente, deve-se começar com o problema de contagem # definido por uma função e depois definir o problema de decisão em uma string de entrada como ?f : { 0 , 1 } N X s f ( s ) 0Xf:{0,1}NXsf(s)0

Tyson Williams
fonte
2
Você está procurando algo mais do que "X é NP-completo sob reduções parcimoniosas"?
Joshua Grochow
3
@usul: Não. Se abandonarmos a suposição de que X é NP-completo, a correspondência bipartida está em P (então definitivamente não é parcimoniosamente NP-completo assumindo ), mas sua versão contadora é # P-concluída. No entanto, se realmente queremos X NP-complete, então, de cabeça para baixo, não conheço um problema X tal que: 1) X seja NP-complete, 2) X não seja NP-complete sob reduções parcimoniosas, e 3) #X é # P-completo. Mas eu realmente não pensei sobre isso. PNP
Joshua Grochow
13
Mas existe um problema que nega isso? ou seja, X é NP-completo e #X não é # P-completo?
Suresh Venkat
6
@YoshioOkamoto: isso prova que #X ∈ #P implica que X ∈ NP . Está na direção errada e perde o problema da perfeição. O que estamos vendo é essencialmente quais requisitos adicionais são necessários para que exista uma redução muitos-para-um para problemas de decisão no NP (para problemas de decisão arbitrários ou de um problema completo do NP ) implica a existência de um redução de contagem eficiente para problemas no #P (para problemas de contagem arbitrários ou de um problema completo do #P ).
Niel de Beaudrap
3
@ColinMcQuillan Pode ser declarado ao contrário. Comece com um problema de contagem e defina um problema de decisão perguntando se a saída é diferente de zero.
Tyson Williams

Respostas:

23

O artigo mais recente sobre essa questão parece ser:

Noam Livne, Uma nota sobre # P-completude das relações testemunha de NP , Information Processing Letters, Volume 109, Edição 5, 15 de fevereiro de 2009, páginas 259–261 http://www.sciencedirect.com/science/article/pii/ S0020019008003141

o que fornece algumas condições suficientes.

Curiosamente, a introdução afirma "Até o momento, todos os conjuntos completos de NP conhecidos têm uma relação definidora que é #P concluída", portanto a resposta ao comentário de Suresh é "nenhum exemplo é conhecido".

Colin McQuillan
fonte
6

Fischer, Sophie, Lane Hemaspaandra e Leen Torenvliet. "Reduções isomórficas de testemunhas e busca local". NOTAS DE PALESTRAS EM MATEMÁTICA PURA E APLICADA (1997): 207-224.

No início da seção 3.5, eles fazem a seguinte pergunta "Em particular, existem conjuntos completos de NP que, em relação a algum esquema de testemunha, não estão #P-completos?"

E então eles provam no Teorema 3.1 que "Se houver um conjunto NP completo L que, com relação a alguma relação de testemunha R não for # P-completo, então ".PP # PLP P#P

Tayfun Pay
fonte