Problèmes naturels NP-complets avec les «grands» témoins

28

La question sur la théorie " Qu'est-ce que NP est limité aux témoins de taille linéaire? " Demande à propos de la classe NP limitée aux témoins de taille linéaire O(n) , mais

Existe-t-il des problèmes naturels NP-complets dans lesquels (oui) les instances de taille nécessitent des témoins de taille supérieure à ?nnn

De toute évidence, nous pouvons créer des problèmes artificiels comme:

  • L={1nww encodes a satisfiable formula and |w|=n}
  • L={φφ is SAT formula with more than |φ|2 satisfying assignments}

Après un rapide coup d'œil à G&J, chaque problème de PNJ naturel semble avoir des témoins (strictement) plus petits que .n

Y a-t-il une «raison / explication» pour cela?

Marzio De Biasi
la source
1
De nombreux problèmes ont une taille de témoin , comme l'isomorphisme du graphe et le chemin hamiltonien. Souhaitez-vous exclure les facteurs de polylogue, ou cela compte-t-il comme réponse? Θ(nlogn)
Joshua Grochow
12
En fait, la taille du témoin pour l'isomorphisme du graphique et le chemin hamiltonien pourrait être considérée comme sublinéaire dans l'entrée (étant donné que l'entrée est la matrice de contiguïté du graphique). n×n
Ryan Williams
1
Oh, c'est vrai ... d'oh.
Joshua Grochow
1
@MarzioDeBiasi Je pense que votre observation de petits témoins devrait être utilisée pour définir un problème NP-complet naturel .
Mohammad Al-Turkistany,
1
@MarzioDeBiasi - Je suis d'accord qu'une liste des affectations satisfaisantes suffit, mais pouvez-vous prouver qu'il n'y a pas de témoin plus court du problème? (peut-être une façon succincte de représenter les affectations nécessaires).
RB

Réponses:

10

Que diriez-vous du nombre de coloration de bord dans un graphique dense (aka indice chromatique )? On vous donne la matrice d'adjacence d'un graphe à sommets ( entrée bits), mais le témoin naturel décrivant la coloration a la taille . Bien sûr, il pourrait y avoir des preuves plus courtes pour les graphiques de classe 1 dans le théorème de Vizing .n 2 n 2 log nnn2n2logn

Voir aussi cette question éventuellement liée

Andreas Björklund
la source
2
Cela semble un bon exemple! Juste une note: le problème est NP-complet même pour les graphiques cubiques; dans ce cas, nous avons un témoin de taillebits est suffisant (deux bits pour chaque front), ce qui est inférieur à si nous utilisons la représentation de la matrice d'adjacence et je soupçonne qu'il est inférieur à la taille d'instance quel que soit le codage raisonnable que nous utilisons pour le graphique cubique. n 22|E|n2
Marzio De Biasi
8

Je suis venu avec des problèmes NP-tout à fait naturels qui nécessitent apparemment de longs témoins. Les problèmes, paramétrés par les entiers et sont les suivants:DCD

Entrée: Un TM une bande Question: Y a - t-il des , de telle sorte que fasse plus de pas sur une entrée de longueur ?n N M C n + D nM
nNMCn+Dn

Parfois, le complément du problème est plus facile à énoncer: un TM une bande donné s'exécute-t-il dans le temps , c'est-à-dire fait-il au plus des pas sur toutes les entrées de taille , pour tout ?C n + D C n + D n nMCn+DCn+Dnn

Le résultat complet est présenté ici . Fondamentalement, il est montré que si nous voulons vérifier si une MT à une bande s'exécute dans le temps , nous n'avons besoin de le vérifier que sur des entrées de longueur limitée par , où est le nombre des états de l'entrée TM. Le témoin serait donc l'entrée de longueur pour laquelle la limite de temps est violée. Il est également montré dans la référence que ces problèmes sont NP-complets pour tous les et .q O ( C ) q q O ( C ) C 2 D 1Cn+DqO(C)qqO(C)C2D1

Maintenant, si le témoin est une entrée qui viole le temps d'exécution, il doit être de longueur en général. Et l'entrée est de longueur . O ( q 2 )qΩ(C)O(q2)

David G
la source
3
Merci! Mais, pour être honnête, je trouve plus "naturel" (je sais que ce n'est pas un concept formel) le problème: "Étant donné une formule , décidez si elle a au moins affectations satisfaisantes" :-)| φ | 2φ|φ|2
Marzio De Biasi
Je comprends :). D'un autre côté, le problème de a la longueur du témoin dans la question, tandis que le problème des MTs obtient la longueur du témoin dans la preuve. De plus, la longueur du témoin n'est pas intentionnellement intégrée au problème. φ
David G
7

Voici un exemple, qui apparaît comme un problème naturel.

Instance: entiers positifs, et , tous délimités d'en haut par . k nd1,,dnkn

Question: Existe-t-il un graphe colorable avec la séquence de degrés ?d 1 , , d nkd1,,dn

Ici, l'entrée peut être décrite avec bits, mais le témoin peut nécessiter bits.Ω ( n 2 )O(nlogn)Ω(n2)

Remarque: Je n'ai pas de référence indiquant que ce problème particulier est en effet NP-complet. Mais l'exigence de colorabilité pourrait être remplacée par toute autre condition NP-complète; le problème deviendra probablement NP-complet pour une condition, sinon pour celle-ci.k

Andras Farago
la source
Pour moi, ce problème a le mauvais type de structure pour être NP-complet, sauf si P = NP. Les classes de graphiques définies par chaque séquence de degrés peuvent être très grandes, et bon nombre d'entre elles peuvent avoir des éléments à couleurs pour une raison triviale. n
András Salamon
@ AndrásSalamon En effet, je ne sais pas quelle est la complexité de ce problème, ni s'il peut être rendu NP-complet en choisissant une condition appropriée au lieu de colorabilité. D'un autre côté, je serais surpris si pour chaque propriété vérifiable de poly-temps le problème suivant se trouvait dans P : existe-t-il un graphe avec une séquence de degrés donnée, de sorte qu'il a également la propriété ? Q QkQQ
Andras Farago
Je suis d'accord qu'il semble peu probable que la séquence de degrés + la propriété soit toujours en P, mais peut-être que certains d'entre eux sont candidats au statut NP-intermédiaire?
András Salamon
@ AndrásSalamon Oui, je peux très bien imaginer que certains d'entre eux ont le statut NPI.
Andras Farago
6

C'est peut-être une "raison / explication" idiote, mais pour de nombreux problèmes NP-Complete, une solution est un sous-ensemble de l'entrée (sac à dos, couverture de vertex, clique, ensemble dominant, ensemble indépendant, coupe maximale, somme du sous-ensemble, ... ) ou une permutation ou affectation à un sous-ensemble de l'entrée (chemin hamiltonien, vendeur ambulant, SAT, isomorphisme graphique, coloration graphique, ...).

Nous pourrions essayer d'en savoir plus que cela, ou trouver une raison plus explicite, mais je ne sais pas s'il se passe quelque chose de plus profond ou non.

usul
la source
Je pense que c'est une bonne "première idée". Parfois, les problèmes ne peuvent pas être classés sans ambiguïté. Par exemple, SAT pourrait également être un problème de sous-ensemble («choisir un sous-ensemble de vraies variables»). Ou HAMCYCLE est-il un problème de permutation sur les sommets, ou un problème de sous-ensemble sur les arêtes? (BTW, peut-être que les "problèmes d'affectation" pourraient vraiment être des "problèmes de partition", pensez par exemple à 3 coloriages).
Juho
3

En ce qui concerne votre première question, Allender déclare (dans Amplifying Lower Bounds by Means of Self-Reductibility ) qu'aucun problème naturel de NP-complet n'est connu en dehors de NTIME (n). Cela signifie que tous les ensembles naturels connus NP-complets ont des témoins de taille linéaire.

Mohammad Al-Turkistany
la source
1
Notez que la longueur du chemin d'acceptation le plus long dans la machine de Turing non déterministe correspond à la taille du témoin.
Mohammad Al-Turkistany
1

Considérez la variante suivante du problème MAXCLIQUE .

Instance: Un circuit avec 2 n bits d'entrée, et de taille polynomiale bornée en n . Ce circuit détermine implicitement un graphe sur 2 n sommets, de sorte que chaque sommet est identifié avec une chaîne de n bits, et deux sommets sont connectés avec un bord si la chaîne de 2 n bits obtenue en concaténant les deux ID de sommet est accepté par C . Soit G ( C ) ce graphique. Notez qu'il a de façon exponentielle de sommets dans n , mais est toujours déterminée par la description de taille polynomiale de C .C2nn2nn2nCG(C)nC

Question: Est-ce que contient une clique de taille n k , où k est une constante fixe?G(C)nkk

Remarques:

  1. Le problème est NP-complet. Le confinement dans est évident. L'exhaustivité peut être prouvée en observant que si le circuit accepte uniquement des paires de sommets dans lesquelles chaque ID est au plus N = 2 n k , alors G ( C ) peut être un graphe N- sommet arbitraire plus de nombreux sommets isolés. (Un tel graphe N- sommet peut être encodé en C , car C est autorisé à avoir une taille polynomiale en n , et donc aussi en N. ) Alors la question devient: y a-t-il une clique de taille N / 2 dans un NNPN=2nkG(C)NNCCnNN/2Ngraphique -texte? Ceci est connu pour être NP-complet, pour le général . Le problème que N n'est pas arbitraire, il est limité à N = 2 n k , peut être éliminé par un remplissage approprié.NNN=2nk

  2. Le témoin naturel du problème d'origine est la clique de taille , qui peut être décrite par une chaîne longue O ( n k + 1 ) (une chaîne n bits pour chacun des n k sommets). Notez que k peut être une constante très grande, donc le témoin peut être beaucoup plus long que linéaire. (Même si la taille d'entrée est la description de C , plutôt que de n , ce témoin peut être encore beaucoup plus long, car k peut être choisi indépendamment de C. )nkO(nk+1)nnkkCnkC

  3. Le problème peut être considéré comme naturel, car il s'agit d'une variante de MAXCLIQUE .

  4. Quand Allender a écrit "aucun problème naturel NP-complet n'est connu en dehors de " (voir Amplifier les limites inférieures par des moyens d'auto-réductibilité , Section 7), il peut avoir eu un concept plus étroit de le naturel à l'esprit. Par exemple, le naturel pourrait être réduit à quelque chose que les gens veulent vraiment résoudre sur la base de motivations indépendantes et pratiques. Ce n'est pas suffisant si le problème n'est pas construit par diagonalisation.NTIME(n)

Andras Farago
la source
Je ne suis pas sûr de suivre votre réduction de Half-Clique à ce problème, pour établir l'exhaustivité de NP. Étant donné une instance -vertex de Half-Clique, à quel circuit correspond-elle? n
András Salamon
@ AndrásSalamon Soit un graphe N = 2 n k -vertex, servant de graphe d'entrée de Half-Clique. Alors C est le circuit qui accepte n'importe quelle paire de nœuds ( u , v ) , si u N ,GN=2nkC(u,v) (en nombres binaires) et ( u , v ) E ( G ) , sinon C rejette. (Ce C peut être implémenté comme un circuit de taille polynomiale.) Alors G ( C ) contiendra G ' sur les N premiersnœuds, plus 2 n - N nœuds isolés supplémentaires. Le graphe G ( C ) a une clique de taille n k précisément lorsque G uN,vN(u,v)E(G)CCG(C)GN2nNG(C)nkGa une demi-clique.
Andras Farago