En supposant que p= np, comment résoudre le problème de coloration graphique en polynôme?
https://cs.stackexchange.com/questions/121710
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
en supposant que nous avons $ \ sf p= np $ , comment puis-je montrer comment résoudre le problème de coloration graphique en temps polynomial?
donné un graphique $ g= (v, e) $ , trouver une coloration valide $ \ chi (g): V \ to \ to \ to \ \ {1,2, \ CDOT, k \} $ pour certains $ K $ satisfaisant la propriété qui $ (u, v) \ in e $ implique $ \ chi (u) \ ne \ chi (v) $ de manière àMinimiser le moins le nombre $ K $ de "couleurs".
La solution
Il y a deux cas:
-
$ p= np $ non de manière non constructive: cela signifie que nous avons dérivé une contradiction de l'hypothèse selon laquelle $ P \ neq np $ , et peut donc conclure que $ p= np $ par la loi du milieu exclu. Dans ce cas, nous avons aucune idée quel algorithme pour résoudre le graphique coloration dans le temps polynomial ressemble à un autre problème ou tout autre problème. Nous savons qu'on existe, car nous savons que si cela n'existe pas, nous pouvons dériver une contradiction. Donc, une preuve de ce formulaire est assez inutile pour résoudre rapidement les problèmes.
-
$ p= np $ de manière constructive. Dans ce cas, nous avons un algorithme de temps polynomial pour certains $ np $ -hard problème, disons $ l $ . Si $ L $ est NP-DUR, alors il doit résoudre un autre problème de la NP-dur en temps polynomial (c'est-à-dire qu'il réduit de ce problème). Ce problème, à son tour, réduit d'un autre problème ou a une réduction directe de chaque problème dans $ np $ . Nous continuons à suivre le sentier des réductions jusqu'à ce que nous arrivions à un avec une preuve directe (probablement 3SAT).
En composant ces réductions, nous obtenons un algorithme qui résout 3SAT en temps polynomial (car chaque réduction ne fait qu'un nombre polynomial d'appels à l'algorithme précédent, et notre algorithme de départ pour $ L $ fonctionne en temps polynomial.
Nous branchons ensuite cet algorithme dans la réduction de Theorem Cook-Levin , qui nous donne un moyen de simuler tout algorithme en cours d'exécution en polynôme avec un nombre polynomial d'appels vers un solveur 3SAT. Encore une fois, un nombre polynomial d'appels vers un algorithme de temps polynomial fonctionne dans du temps polynomial.
Autres conseils
si p= np, cela signifie qu'il y a un problème donné dans NP, par exemple, le problème "est $ g $ $ k $ -colourable?", où $ g $ est un graphique fini et $ k $ un entier, il y a un algorithme pour le résoudre en temps polynomial.
Malheureusement, notre problème n'est pas dans NP. Nous voulons trouver un $ k $ -colouring pour le minimum possible $ k $ . Maintenant, nous pouvons trouver le minimum possible $ k $ en temps polynomial juste en résolvant à plusieurs reprises le problème ci-dessus pour $ k= 1, 2, \ ldots $ , jusqu'à ce qu'il renvoie la réponse "Oui". (Notez que cela se produit à l'époque $ k $ atteint le nombre de sommets, sinon plus tôt, seul un nombre polynomial d'instances est nécessaire.)
mais maintenant que nous savons $ k $ , comment trouvons-nous une $ k $ -colouring ? Eh bien, si $ k $ est égal au nombre de sommets, c'est facile: chaque sommet doit avoir une couleur différente. Si $ k $ est inférieur au nombre de sommets, puis dans n'importe quelle coloration (et nous en savons qu'on existe), il y a deux sommets $ x $ et $ y $ de la même couleur (qui doit être non adjacent). Cela signifie que nous pouvons combiner $ x $ et $ y $ (retirez-les et remplacez-les par un nouveau sommet qui est adjacent à chaque voisin de $ x $ ou $ y $ ) et les mêmes travaux de coloration pour ce nouveau graphique. Donc, ce nouveau graphique est également $ K $ -colourable et a un sommet de moins.
Alors, ce que nous pouvons faire est de fonctionner sur toutes les paires de sommets non adjacents $ x, y $ et vérifiez si le nouveau graphique formé en combinant $ x $ et $ y $ est $ k $ - Colourble, jusqu'à ce que nous obtenions une réponse "oui" (cela doit éventuellement arriver). Nous répétons ensuite ce processus, ce qui permet de garder une trace de laquelle des sommets originaux ont été combinés pour former chaque sommet actuel jusqu'à ce que le graphique ait uniquement $ K $ sommets. Ceci divise les sommets du graphique d'origine dans k $ K $ , et nous pouvons simplement donner à chacun sa propre couleur pour obtenir une $ K $ -Colourage de $ g $ .
L'algorithme approximativement esquissé suivant, en supposant p= np, trouve une coloration du graphe d'entrée si l'on existe, en temps polynomial. S'il n'y a pas de tel 3 colorant, cependant, il ne se termine jamais.
Premièrement, apprenez à énumérer tous les algorithmes possibles (machines de Turing) et simuler le calcul de toute machine de turicing sur une entrée arbitraire.
Deuxièmement, apprenez à énumérer tous les algorithmes possibles avec un réveil de poly-time attaché. (Cela signifie que nous allons énumérer un cas particulier de machines de Turing qui font conceptuellement deux choses en parallèle; sur un ensemble de bandes, ils calculent le "problème principal", et sur une bande séparée, ils comptent juste à zéro d'un une des fonctions N, 2 * N ^ 2, 3 * N ^ 3, ..., où n est la longueur de l'entrée au problème principal, arrêt du calcul (peut-être prématurément du point de vue du problème principal) une fois que cela Le compte à rebours sur la bande séparée (appelé réveil) atteint zéro avant que le problème principal ne soit résolu. Donc, parfois, le calcul est terminé car une sortie a été prévue pour le problème principal, et parfois le calcul est terminé par le réveil, avec la sortie. bande contenant quoi que ce soit.)
L'ordre exact dans lequel les machines de Turing avec une réveil polynomial attenant sont énumérées doivent être exhaustives: il devrait être tel que nous allons rencontrer chaque combinaison d'une machine à trouble et d'une fonction de réveil parmi celles suggérées plus tôt ou plus tard.
Maintenant, apprenez à simuler toutes ces machines de Turing avec une réveil polynomiale attachée en parallèle, les commencer bien espacés dans le temps un par un. En particulier, assurez-vous que près de la moitié de la durée de fonctionnement totale est consacrée à la première machine de Turing avec une réveil polynomiale attachée dans l'énumération, près du quart du temps total de fonctionnement de la deuxième machine, presque un huitième de celui-ci à la troisième machine et ainsi de suite. (Nous veillons à ce que chaque machine Turing dans l'énumération obtient une gamme de fractions constante connue de temps d'exécution total, en supposant que nous continuons à courir au moins jusqu'à sa première transition.)
Comment pouvons-nous faire ça? Exemple: simuler une transition de la première machine. Ensuite, la même chose - une autre transition de la première machine. Puis une transition de la deuxième machine. Que tout cela: deux autres transitions de la première machine et une autre de la deuxième machine. Seulement alors effectuez la première transition de la troisième machine, suivie de tout ce qui est à nouveau (sept autres transitions au total) avant de simuler la première transition de la quatrième machine.
De temps en temps, une machine se termine, que ce soit en raison de son réveil ou de résoudre son problème principal (qui consistera rarement d'une production de 3 colorants du graphique d'entrée, mais qui se soucie). Si une machine s'est terminée, nous vérifions si elle a produit une coloration 3 valide du graphe d'entrée sur sa bande de sortie et, dans l'affirmative, nous terminons la totalité de la simulation de toutes les machines de Turing avec des réveils connectés, renvoyant la même coloration que le sortie.
Pour être honnête, je n'ai pas vérifié de près que je peux amortir la surcharge de l'attention d'une machine à une machine à une machine, la surcharge d'itération à travers les machines (c'est-à-dire générer l'état initial d'une nouvelle machine dans l'énumération ), et la surcharge de la vérification des états terminaux (si une machine de terminaison tombait sur une coloration 3 valide ou non); Mais je peux certainement m'assurer de passer plus de temps sur les transitions simulées de machines de Turning individuelles que sur tous ces types de frais généraux, c'est-à-dire que la surcharge totale finit de moins de 100%, encore une fois un facteur constant.
Maintenant, il est bien connu que la version de la fonction du 3 problème de coloration est réductible à sa version de décision. Il y a un simple algorithme de temps polynomial pour le problème de décision (par p= np) et donc l'algorithme auto-réduit qui identifie de manière fiable un exemple 3 colorant dans du temps polynomial chaque fois que l'on existe, se produit
===
(J'aimerais dire que cette simulation s'approche de la préservation même de l'exposant optimal de la recherche de la 3 coloration, mais cela ne serait tout simplement pas vrai. Le plus gros problème à cet égard est que le simulateur "universel" peut avoir moins de bandes et moins d'états que la machine simulée et simulant même
Une seule transition est un exercice coûteux; La simulation conserve du temps polynomial, mais pas l'exposant spécifique.)Malheureusement, une telle simulation devient une algorithme de temps polynomial pour la recherche de 3-colorants si nous l'équipent maintenant avec son propre réveil de temps polynomial (le ralentissant ainsi deux fois et garantissant qu'il se termine sur toute entrée dans la spécifie. limite de temps); Et cette dernière étape est constructive. Contrairement à toute partie de la construction jusqu'à présent, nous ne savons pas quel polynôme entre N, 2 * N ^ 2, 3 * N ^ 3, ... doit être choisi pour le réveil. Nous savons simplement qu'une réveil suffisamment libérale existe, de sorte que si nous l'attachons à notre machine (sinon spécifique) "universelle", nous obtiendrons un algorithme de temps polynomial faisant 3 colorants où qu'ils existent et rejetant (uniquement) des graphiques qui ne sont pas 3 Colorables ou entrées qui ne codent pas de graphiques.
La méthode de simulation universelle peut être étendue même à votre problème de coloration graphique à l'aide de la technique supplémentaire décrite dans cette réponse . Ce qui devient Messier, c'est que nous ne sommes alors plus capables de filtrer les "mauvaises réponses" qui sont facilement; Si une machine nous offre une 5 coloration, comment savons-nous si une 4 coloration existe-t-elle? La solution suffisante consiste simplement à attendre, soit une coloration à 4 colorants apparaîtra dans la sortie d'une meilleure machine enfant comportée ou non, avant que le réveil maître s'épuise. Encore une fois, la dernière étape sera non constructive: nous savons qu'avec un réveil de temps polynomial suffisamment libéral, nous obtenions un algorithme polynomial nous donnant des colorants optimaux, mais il est difficile de dire quel polynôme spécifique choisir si tout ce que nous savons est que P= np. Si nous choisissons une horloge de temps polynomiale trop agressive (insuffisante), non seulement, nous ne parvenons pas seulement à trouver la coloration optimale, mais nous émettrons parfois une coloration sous-optimale que nous avons essayé d'attendre, mais pas assez patiemment.
avoir p= np signifie que est un algorithme de temps polynomial.Cela ne signifie pas que nous savons un, ou nous allons jamais connaissez-en un, ou nous serons jamais en mesure de prouver il fonctionne dans du temps polynomial.
Et nous pourrions trouver un algorithme exécutant dans O (n ^ 10000), ce qui signifie que nous pouvons réellement résoudre aucune instance de taille> 1 .
.