Problème complet avec borne quasi polynomiale sur le nombre de solutions

FewP est la classe des problèmes avec polynôme lié au nombre de solutions (dans la taille d'entrée). On ne connaît pas problème -complete dans . Je voudrais savoir jusqu'où nous pouvons étendre cette observation. $NP$ $NP$ $fewP$

Existe-t-il un problème naturel de complet avec une limite supérieure quasi-polynomiale sur le nombre de solutions (témoins)? Existe-t-il une conjecture largement acceptée qui exclurait une telle possibilité? $NP$

Naturel signifie que le problème n'est pas un problème artificiel pour répondre à la question (ou à des questions similaires) et que les gens sont intéressés par le problème indépendamment (tel que défini par Kaveh).

EDIT: La prime sera accordée à ce problème naturel de complet ou à un argument raisonnable excluant l'existence de tels problèmes (en utilisant des conjectures théoriques de complexité largement acceptées). $NP$

Motivation: Mon intuition est que la complétude impose une limite inférieure superpolynomiale (ou même exponentielle) au nombre de témoins. $NP$

cc.complexity-theory np Mohammad Al-Turkistany
la source

Le problème de promesse UniqueSAT se trouve dans (différent de ), qui est un sous-ensemble de (différent de ).

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

Un rembourrage de SAT répondrait-il à votre question?

Kaveh

C'est tout le problème - ce n'est pas le cas; la taille d' entrée est le nombre de bits en entrée, et (rares) les instances 3-sat ont la taille . Le nombre de variables n'est qu'un aspect (paramètre) de l'entrée, donc pour d'autres problèmes (par exemple des problèmes de graphe), il faudrait spécifier de quoi on mesure le nombre de témoins en termes de. Par exemple, pour la coupe maximale, le graphique d'entrée peut avoir arêtes, et là encore il n'y a que témoins (ce qui est sous-exponentiel en taille d' entrée ). Mais nous voulons vraiment mesurer en termes de . Cependant, il n'est pas évident que le #vertices soit la bonne mesure.

m \log n

$m \log n$

n^{2}

$n^2$

2^{n}

$2^n$

n

$n$

daniello

@Kaveh Oui, vous devez donc supposer que Mohammad a pensé à celui qui a du sens dans sa question. De plus, comme vous pouvez le voir, le zoo de complexité est d'accord avec ma définition. En général, dans toute classe de complexité intéressante, la définition ne devrait pas changer si vous remplissez l'entrée par un polynôme.

domotorp

@downvoters Pourquoi diable les gens votent-ils contre cette question? Je veux dire au moins que quelqu'un pourrait donner une raison à cela ...

domotorp

Réponses:

C'est une question très intéressante.

Tout d'abord, une remarque de clarification. Notez que la "borne supérieure du nombre de témoins" n'est pas la propriété d'un problème de calcul en soi, mais d'un vérificateur particulier utilisé pour décider d'un problème , tout comme une "borne supérieure du nombre d'états" ne serait pas un propriété d'un problème mais d'une machine de Turing le décidant. Donc, dire " problème avec la limite supérieure du nombre de solutions" n'est pas tout à fait exact, et si alors chaque problème a un vérificateur avec un certain nombre de solutions souhaitées (y compris zéro et toutes les chaînes possibles) . $NP$ $NP$ $P = NP$ $NP$

Nous devons donc faire une définition, pour répondre à votre question. Pour , disons qu'un problème "a au plus solutions" si pour une constante il y a un vérificateur de temps tel que, pour chaque longueur d'entrée et pour chaque de longueur , il y a distinctement $s : {\mathbb N} \rightarrow {\mathbb N}$ $NP$ $L$ $s(n)$ $c$ $O(n^c)$ $V$ $n$ $x \in L$ $n$ de longueur telle queaccepte pour tout, etrejette tous les autresde longueur . $y_1,\ldots,y_{s(n)}$ $n^c$ $V(x,y_i)$ $i$ $V(x,y)$ $y$ $n^c$

Tout ce que je pense pouvoir dire pour le moment, c'est ceci:

Chaque problème -complet que je connais (défini par un vérificateur naturel) a une version de comptage -complete correspondante correspondante évidente (avec le même vérificateur). $NP$ $\#P$
Pour tout problème complet défini avec un vérificateur ayant au plus solutions (ou même solutions) la version de comptage correspondante n'est probablement pas complète. $NP$ $poly(n)$ $2^{n^{o(1)}}$ $\#P$

Plus de détails: Supposons que est complet, avec un vérificateur qui a au plus solutions. Ensuite, la version de «décision» de comptage naturel de , que nous définissons comme $L$ $NP$ $V$ $O(n^c)$ $L$

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

est calculable en , qui est une fonction de temps polynomial avec des requêtes à . C'est parce que décider si le nombre de solutions à est au plus est dans : le témoin, s'il existe, est simplement le nombre de faisant accepter , que nous savons être au plus $FP^{NP[O(\log n)]}$ $O(\log n)$ $NP$ $x$ $k$ $NP$ $y_i$ $V$ $O(n^c)$ . Ensuite , nous pouvons binaires recherche en utilisant ce problème pour calculer le nombre exact de solutions à . $NP$ $L$

Par conséquent, un problème complet de ce type ne peut pas être étendu à un problème complet de la manière habituelle, sauf si . Cela semble peu probable; toute la hiérarchie polynomiale temporelle s'effondrerait essentiellement en . $NP$ $\#P$ $\#P \subseteq FP^{NP[O(\log n)]}$ $P^{NP[O(\log n)]}$

Si vous supposez que dans ce qui précède, vous obtiendriez toujours une conséquence improbable. Vous montreriez que peut être calculé en fois avec un oracle C'est plus que suffisant pour prouver, par exemple, que et ensuite $s(n) = 2^{n^{o(1)}}$ $\#P$ $2^{n^{o(1)}}$ $NP$ $EXP^{NP} \neq PP$ $EXP^{NP} \not\subset P/poly$ . Non pas que ces séparations soient peu probables, mais il semble peu probable qu'elles soient prouvées en donnant un algorithme de sous-expiration -oracle pour le permanent. $NP$

Soit dit en passant, je n'ai rien dit de trop perspicace ici. Il existe presque certainement un argument comme celui-ci dans la littérature.

Ryan Williams
la source

En effet, c'est une réponse perspicace.

Mohammad Al-Turkistany,