En lisant l'article "Est-il temps de déclarer la victoire en comptant la complexité?" sur le blog "Godel's Lost Letter and P = NP" , ils ont mentionné la dichotomie pour les CSP. Après quelques liens après, googler et wikipeding, je suis tombé sur le théorème de Ladner : Théorème de Ladner: Si ,...
Étant donné une matrice binaire par (les entrées sont ou 1 ), le problème est de déterminer s'il existe deux vecteurs binaires v 1 ≠ v 2 tels que M v 1 = M v 2 (toutes les opérations effectuées sur Z ). Ce problème est-il difficile à NP?n M 0mmmnnnMMM000111v1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 =...
Le problème suivant est-il NP-difficile? Étant donné une configuration de carte pour brouillons internationaux , trouvez un mouvement juridique unique.n×nn×nn\times n Le problème correspondant pour les vérificateurs américains (ou versions anglaises) est trivialement résoluble en temps polynomial....
Considérez le problème de couverture de l'ensemble minimal avec les restrictions suivantes: chaque ensemble contient au plus éléments et chaque élément de l'univers se produit dans au plus ensembles.kkkfff Exemple: le cas et est équivalent au problème de couverture minimale des sommets dans les...
La complexité du problème suivant a-t-elle été étudiée? Entrée : un graphe cubique (ou régulier) , une borne supérieure naturelleG = ( V , E ) t333G = ( V, E)G=(V,E)G=(V,E)ttt Question : existe-t-il une partition de en parties de taille telle que la somme des ordres des sous-graphes correspondants...
Y a-t-il des références couvrant
Considérez le problème suivant: étant donné une formule CNF et une affectation qui satisfait cette formule, y a-t-il une autre affectation satisfaisante pour cette formule? Quelle est la complexité de ce problème? (C'est sûrement en NP, mais est-il aussi difficile en NP?) Que se passe-t-il si vous...
Pour tout , je dis qu'une séquence s d'entiers dans { 1 , … , n } est n -complète si, pour chaque permutation p de , écrite comme une séquence de paires entiers distincts , la séquence p est une sous-séquence de s , c'est-à-dire qu'il existe 1 ≤ i 1 < i 2 < ⋯ < i n ≤ | s |n>0n>0n >...
On sait qu'il est NP-complet de tester si un cycle hamiltonien existe dans un graphe à 3 réguliers, même s'il est planaire (Garey, Johnson et Tarjan, SIAM J.Comput.1976) ou bipartite (Akiyama, Nishizeki, et Saito, J. Inform. Proc. 1980) ou pour tester si un cycle hamiltonien existe dans un graphe à...
Il existe une littérature abondante et au moins un très bon livre exposant la dureté connue des résultats d'approximation pour les problèmes NP-difficiles dans le contexte d'erreur multiplicative (par exemple, l'approximation 2 pour la couverture des sommets est optimale en supposant UGC). Cela...
Existe-t-il des problèmes NP-complets pour lesquels un algorithme est connu que le temps d'exécution attendu est polynomial (pour une distribution sensible sur les instances)? Sinon, existe-t-il des problèmes pour lesquels l'existence d'un tel algorithme a été établie? Ou l'existence d'un tel...
Je m'intéresse au problème d'emballer des copies identiques de rectangles (2 dimensions) dans un polygone convexe (2 dimensions) sans chevauchements. Dans mon problème, vous n'êtes pas autorisé à faire pivoter les rectangles et pouvez supposer qu'ils sont orientés parallèlement aux axes. On vous...
On sait que le cycle hamiltonien (jambon en abrégé) est NP-complet et que le cycle planaire du jambon est NP-complet. La preuve pour Planar Ham Cycle n'est pas de Ham Cycle. Existe-t-il un joli gadget qui, étant donné un graphe G, remplacera tous les croisements par un gadget plan afin que vous...
Je fixe un langage régulier sur un alphabet , et je considère le problème suivant que j'appelle la planification de la lettre pour . De manière informelle, l'entrée me donne lettres et un intervalle pour chaque lettre (c'est-à-dire une position minimale et maximale), et mon objectif est de placer...
Pour une constante , on peut déterminer en temps linéaire, étant donné un graphe d'entrée G , si sa largeur d'arbre est ≤ k . Cependant, lorsque k et G sont donnés en entrée, le problème est NP-difficile. ( Source ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Cependant, lorsque le graphe d'entrée est...
Il y a clairement une réduction de CLIQUE à k-Color car ils sont tous deux NP-Complete. En fait, je peux en construire un en composant une réduction de CLIQUE à 3-SAT avec une réduction de 3-SAT à k-Color. Je me demande s'il y a une réduction directe raisonnable entre ces problèmes. Disons, une...
Le problème Not All Equal -SAT (NAE k -SAT), étant donné un ensemble C de clauses sur un ensemble X de variables booléennes telles que chaque clause contient au plus k littéraux, demande s'il existe une affectation de vérité des variables telles que chaque clause contient au moins un vrai et au...
Cette question est liée à une réponse que j'ai postée en réponse à une autre question. Le problème des 3 partitions est le problème suivant: Instance : entiers positifs a 1 ,…, a n , où n = 3 m et la somme des n entiers est égale à mB, de sorte que chacun a i satisfait B / 4 <a i <B / 2....
La formulation exacte du titre est due à Anand Kulkarni (qui a proposé la création de ce site). Cette question a été posée à titre d'exemple, mais je suis incroyablement curieux. Je connais très peu de choses sur la géométrie algébrique, et en fait, je n'ai aussi qu'une compréhension superficielle...
C'est dans la ligne des " Algorithmes du livre ". Bien que les réductions soient également des algorithmes, je pensais qu'il était douteux que l'on pense à une réduction en réponse à la question sur les algorithmes du livre. D'où une requête distincte! Les réductions de toutes sortes sont les...