problema completo com ligação quase polinomial ao número de soluções

15

FewP é a classe de NP -os problemas com polinomial ligada do número de soluções (no tamanho da entrada). Não é conhecido nenhum NP problema -completo em fewP . Estou interessado em até onde podemos esticar essa observação.

Existe alguma naturais NP problema -completo com quase-polinomiais limite superior no número de soluções (testemunhas)? Existe uma conjectura amplamente aceita que excluiria essa possibilidade?

Natural significa que o problema não é artificialmente inventado para responder à pergunta (ou similar) e as pessoas estão interessadas no problema de forma independente (conforme definido por Kaveh).

EDIT: A recompensa será concedido a tão natural problema -completo ou um argumento razoável excluir a existência de tais problemas (usando conjecturas complexidade da teoria amplamente aceitos).NP

Motivação: Meu intuição é que -completeness impõe super-polinomiais (ou mesmo exponenciais) um limite inferior da quantidade de testemunhas.NP

Mohammad Al-Turkistany
fonte
1
O problema promessa UniqueSAT é no (não a mesma que L P ), que é um subconjunto de P r o m i s e F e W P (não o mesmo que F e W P ) . PromiseUPUPPromiseFewPFewP
Joshua Grochow
3
Um preenchimento de SAT responderia à sua pergunta?
Kaveh #
1
Esse é o ponto todo - não é; o tamanho da entrada é o número de bits na entrada e as instâncias de 3 sat (esparsas) têm o tamanho . O número de variáveis ​​é apenas um aspecto (parâmetro) da entrada; portanto, para outros problemas (digamos, problemas de gráfico), seria necessário especificar o que está sendo medido em termos de número de testemunhas. Por exemplo, para o corte máximo, o gráfico de entrada pode ter n 2 arestas e, novamente, existem apenas 2 n testemunhas (que são subexponenciais no tamanho da entrada ). Mas nós realmente queremos medir em termos de n . No entanto, não é óbvio que os #vertices sejam a medida certa. mlognn22nn
daniello
2
@ Kaveh Sim, então você deve assumir que Mohammad pensou no que faz sentido em sua pergunta. Além disso, como você pode ver, o zoológico de complexidade concorda com minha definição. Em geral, em qualquer classe de complexidade interessante, a definição não deve mudar se você preencher a entrada por um polinômio.
Domotorp 9/11
5
@ downvoters Por que diabos as pessoas estão votando contra essa pergunta? Quero dizer, pelo menos, alguém poderia dar uma razão para isso ... #
1111 domotorp

Respostas:

11

Esta é uma questão muito interessante.

Primeiro, uma observação esclarecedora. Note-se que "limite superior do número de testemunhas" é não uma propriedade de um problema computacional em si, mas de um verificador específico usado para decidir um problema, apenas como um "limite superior ao número de estados" não seria um propriedade de um problema, mas de uma máquina de Turing que o decide. Portanto, dizer " problema N P com limite superior do número de soluções" não é muito preciso e, se P = N P , todo problema N P tem um verificador com qualquer número de soluções desejadas (incluindo zero e todas as seqüências possíveis) .NPNPP=NPNP

Portanto, temos que fazer uma definição, para responder à sua pergunta. Para , digamos que um problema N P L "tenha no máximo s ( n ) soluções" se, para alguma constante c, houver um verificador de tempo O ( n c ) V tal que, para cada comprimento de entrada n e para cada x L de comprimento n , existem distintos y 1 , , y s ( ns:NNNPLs(n)cO(nc)VnxLn de comprimento n cy1,,ys(n)ncde modo que aceita para todos os i , e V ( x , y ) rejeita todos os outros y de comprimento nV(x,yi)iV(x,y)y .nc

Tudo o que acho que posso dizer no momento é o seguinte:

  1. Todo problema de eu conheço (definido por algum verificador natural) tem um óbvio correspondente # PNP#P versão contagem -completo (com o mesmo verificador).
  2. For any NP-complete problem defined with a verifier having at most poly(n) solutions (or even 2no(1) solutions) the corresponding counting version probably isn't #P-complete.

More details: Suppose L is NP-complete, with a verifier V that has at most O(nc) solutions. Then the natural counting "decision" version of L, which we define as

CountL(x):=the number of y such that V(x,y) accepts

FPNP[O(logn)]O(logn)NPxkNP: the witness, if it exists, is simply the number of yi's making V accept, which we know to be at most O(nc). Then we can binary search using this NP problem to compute the exact number of solutions to L.

Therefore, an NP-complete problem of this kind could not be extended to a #P-complete problem in the usual way, unless #PFPNP[O(logn)]. This looks unlikely; the whole polynomial time hierarchy would basically collapse to PNP[O(logn)].

If you assume s(n)=2no(1) in the above, you would still get an unlikely consequence. You would show that #P can be computed in 2no(1) time with an NP oracle. That's more than enough to prove, for instance, that EXPNPPP and subsequently EXPNPP/poly. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time NP-oracle algorithm for the Permanent.

By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.

Ryan Williams
fonte
Indeed it is insightful answer.
Mohammad Al-Turkistany