Por que a variante de contagem de um problema de decisão difícil não é automaticamente difícil?

14

É sabido que o 2-SAT está em P. No entanto, parece bastante interessante que contar o número de soluções para uma determinada fórmula do 2-SAT, ou seja, # 2-SAT seja # P-difícil. Ou seja, temos um exemplo de um problema para o qual a decisão é fácil, mas a contagem é difícil.

Mas considere um problema arbitrário de NP-completo (digamos 3-COL). Podemos dizer imediatamente algo sobre a dureza de sua variante de contagem?

Realmente o que estou perguntando é: por que precisamos de outra prova para mostrar que uma variante de contagem de um problema de decisão difícil também é # P-difícil? (Às vezes, você vê reduções parcimoniosas que preservam o número de soluções e assim por diante). Realmente, se o problema da contagem fosse fácil, você também poderia resolver automaticamente o problema da decisão! Então, como não poderia ser difícil? (OK, talvez seja difícil, mas não tenho certeza sobre qual definição de difícil).

Gideon
fonte

Respostas:

15

A razão pela qual não é um teorema automático de que "a decisão é difícil implica que a contagem é difícil" é que essas duas declarações usam definições diferentes de "difícil".

  • Um problema de decisão é difícil se for NP- completo sob reduções polinomiais de muitas-uma (também conhecidas como reduções de Karp, também conhecidas como reduções de mapeamento de tempo polinomial).

  • Um problema de contagem é difícil se for #P completo com reduções de Turing em tempo polinomial (também conhecidas como reduções de Cook).

Assim, se um problema de decisão for NP- completo, sabemos que o problema de contagem correspondente é NP- difícil, mas essa não é a definição do que é um problema de contagem-difícil. Ser completo #P parece ser uma afirmação muito mais forte do que apenas ser NP - duro - Toda mostrou que os problemas completos #P são difíceis para toda a hierarquia polinomial sob reduções aleatórias, portanto, como uma classe de complexidade, o #P se sente muito mais próximo para PSPACE do que para  NP .

Indo na direção oposta, é claramente verdade que, se o problema de contagem é fácil, no sentido de estar em  FP , então o problema de decisão está em  P . Afinal, se você puder contar com eficiência, certamente poderá dizer se a resposta é diferente de zero. No entanto, apenas porque a versão da contagem "não é difícil" (ou seja, não é # P- completa) não implica que seja "fácil" (ou seja, no  FP ). O teorema de Ladner se estende a  #P , então, se FP ** # P **, existe uma hierarquia infinita de classes de complexidade distintas entre elas, para que o nosso problema de contagem "não-difícil" possa estar completo para qualquer uma dessas aulas e, portanto, não ser "fácil" 

Dito isto, não creio que tenhamos contra-exemplos de que um problema de decisão seja NP- completo significa que a versão de contagem é # P- completa. Portanto, não é um teorema, mas é empiricamente verdadeiro.

David Richerby
fonte
De fato. A propósito do último parágrafo, você pode encontrar um pouco mais de discussão sobre esse ponto em cstheory.stackexchange.com/q/16119/5038 .
DW
1. o problema de contagem não está definido exclusivamente para um problema de NP, é necessário corrigir o verificador de um problema de NP antes de falar sobre sua versão de contagem. 2. dureza na complexidade é dificuldade relativa , não dificuldade absoluta . Então, quando dizemos que um problema é difícil, a pergunta óbvia é relativa a que e sob que tipo de comparação?
Kaveh