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

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$

cc.complexity-theory np Mohammad Al-Turkistany
fonte

O problema promessa UniqueSAT é no

(não a mesma que

), que é um subconjunto de

(não o mesmo que

) .

P r o m i s e U P

$\mathsf{PromiseUP}$

U P

$\mathsf{UP}$

P r o m i s e F e w P

$\mathsf{PromiseFewP}$

F e w P

$\mathsf{FewP}$

Joshua Grochow

Um preenchimento de SAT responderia à sua pergunta?

Kaveh #

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

arestas e, novamente, existem apenas

testemunhas (que são subexponenciais no tamanho da entrada ). Mas nós realmente queremos medir em termos de

. No entanto, não é óbvio que os #vertices sejam a medida certa.

m \log n

$m \log n$

n^{2}

$n^2$

2^{n}

$2^n$

n

$n$

daniello

@ 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

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

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 com limite superior do número de soluções" não é muito preciso e, se , todo problema tem um verificador com qualquer número de soluções desejadas (incluindo zero e todas as seqüências possíveis) . $NP$ $NP$ $P = NP$ $NP$

Portanto, temos que fazer uma definição, para responder à sua pergunta. Para , digamos que um problema "tenha no máximo soluções" se, para alguma constante houver um verificador de tempo tal que, para cada comprimento de entrada e para cada de comprimento , existem distintos $s : {\mathbb N} \rightarrow {\mathbb N}$ $NP$ $L$ $s(n)$ $c$ $O(n^c)$ $V$ $n$ $x \in L$ $n$ de comprimento $y_1,\ldots,y_{s(n)}$ $n^c$ de modo que aceita para todos os , e rejeita todos os outros de comprimento $V(x,y_i)$ $i$ $V(x,y)$ $y$ . $n^c$

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

Todo problema de eu conheço (definido por algum verificador natural) tem um óbvio correspondente $NP$ $\#P$ versão contagem -completo (com o mesmo verificador).
For any $NP$ -complete problem defined with a verifier having at most $poly(n)$ solutions (or even $2^{n^{o(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(n^c)$ solutions. Then the natural counting "decision" version of $L$ , which we define as

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

$FP^{NP[O(\log n)]}$ $O(\log n)$ $NP$ $x$ $k$ $NP$ : the witness, if it exists, is simply the number of $y_i$ 's making $V$ accept, which we know to be at most $O(n^c)$ . 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 $\#P \subseteq FP^{NP[O(\log n)]}$ . This looks unlikely; the whole polynomial time hierarchy would basically collapse to $P^{NP[O(\log n)]}$ .

If you assume $s(n) = 2^{n^{o(1)}}$ in the above, you would still get an unlikely consequence. You would show that $\#P$ can be computed in $2^{n^{o(1)}}$ time with an $NP$ oracle. That's more than enough to prove, for instance, that $EXP^{NP} \neq PP$ and subsequently $EXP^{NP} \not\subset P/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