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

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

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

É 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 ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity Tyson Williams
fonte

Você está procurando algo mais do que "X é NP-completo sob reduções parcimoniosas"?

Joshua Grochow

@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.

P \neq N P

$P \neq NP$

Joshua Grochow

Mas existe um problema que nega isso? ou seja, X é NP-completo e #X não é # P-completo?

Suresh Venkat

@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

@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:

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

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 ". $_L$ ${\bf P}$ $\not =$ ${\bf P^{\bf \#P}}$

Tayfun Pay
fonte