La notion de réductions de temps polynomiales (réductions Cook) est l'abstraction d'un concept très intuitif: résoudre efficacement un problème en utilisant un algorithme pour un problème différent. Cependant, dans la théorie de la complétude de , la notion de dureté de N P est capturée par des...
Ce problème est sorti de mon récent article de blog , supposons que l'on vous donne une visite TSP, est-il co-NP-complet pour déterminer s'il est minime? Plus précisément, le problème suivant est NP-complet: Instance: étant donné un graphe complet G avec des arêtes pondérées par des entiers...
Je m'intéresse au problème suivant: étant donné un ensemble X et des sous-ensembles X_1, ..., X_n de X, trouver une coloration des éléments de X avec k couleurs de telle sorte que les éléments de chaque X_i sont tous de couleurs différentes. Plus précisément, je regarde le cas où tous les X_i sont...
Ai-je raison de comprendre que prouver un problème NP complet est un succès en recherche? Si oui,
Récemment, j'ai rencontré la variante suivante de coloration des bords. Étant donné un graphe connexe non orienté, trouvez une coloration des arêtes qui utilise le nombre maximal de couleurs tout en satisfaisant également la contrainte selon laquelle, pour chaque sommet , les arêtes incidentes à...
Supposons que l'on vous donne un graphe H. connecté, simple et non orienté Le problème de coupe sans H est défini comme suit: Étant donné un graphe simple et non orienté G, existe-t-il une coupure (partition des sommets en deux ensembles non vides, L, R) de sorte que les graphes induits par les...
Considérons le problèmeQQQ suivant Q : On nous donne un entier et k intervalles [ l i , r i ] avec 1 ≤ l i ≤ r i ≤ 2 n . On nous donne également 2 n entiers d 1 , … , d 2 n ≥ 0 . La tâche consiste à sélectionner un nombre minimum d'intervalles [ l i , r i
Je cherche à savoir s'il y a des résultats généraux ou des exemples concernant l'exhaustivité NP du problème de trouver une deuxième solution à un problème NP-complet. Plus précisément, je suis intéressé par tout problème de la forme suivante: Étant donné une solution à une instance d'un problème...
J'ai récemment lu une preuve qui avait pour but de montrer qu'un problème était fortement NP-difficile, simplement en le réduisant (en temps polynomial) à partir d'un problème fortement NP-difficile. Cela n'avait aucun sens pour moi. J'aurais pensé que vous deviez montrer que tous les nombres...
Il est connu que l'intersection de trois matroïdes généraux est NP-difficile ( source ), ce qui se fait par réduction du cycle hamiltonien. La réduction utilise un matroïde graphique et deux matroïdes de connectivité. Un cas particulier d'un problème sur lequel je travaille peut être résolu par...
Je m'intéresse à deux questions concernant les langages contextuels (CSL) et l'exhaustivité: Existe-t-il une notion d'exhaustivité pour CSL et quelles langues sont complètes? Existe-t-il des CSL naturels qui sont NP-complets? Pour 2., je peux certainement penser à des langages NP-complets naturels...
Étant donné un simple graphe non orienté GGG , trouver un sous-ensemble A≠∅A≠∅A\neq \emptyset de sommets, tel que pour tout sommet x∈Ax∈Ax\in A au moins la moitié des voisins de xxx sont également dans AAA , et la taille de AAA est minimale. Autrement dit, nous recherchons un cluster, dans lequel...
Les algorithmes de hachage de mot de passe couramment utilisés fonctionnent comme ceci aujourd'hui: salez le mot de passe et introduisez-le dans un fichier KDF. Par exemple, en utilisant PBKDF2-HMAC-SHA1, le processus de hachage de mot de passe est DK = PBKDF2(HMAC, Password, Salt, ...). Parce que...
Dans le problème de l' emballage de rectangle, on se donne un ensemble de rectangles et délimitant rectangle . La tâche consiste à trouver un emplacement de intérieur de sorte qu'aucun des rectangles ne se chevauche. Généralement, l'orientation de chaque rectangle est fixe. Autrement dit, les...
Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation a 1 x 1 + a 2 x 2 + . . . + a n x n = b , où toutes les...
Supposons que . N P I est la classe de problèmes en N P qui ne sont ni en P ni en N P -hard. Vous pouvez trouver une liste des problèmes supposés être N P I ici .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPje\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Le théorème de Ladner...
Je recherche des problèmes connus pour être des PNJ pour les graphes dirigés mais qui ont un algorithme polynomial pour les graphes non orientés. J'ai vu la question concernant l'inverse des problèmes «dirigés» qui sont plus faciles que leur variante «non dirigée» , mais je recherche la dureté du...
J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...
J'ai posé cette question sur Stack Overflow il y a un moment: Problème: la vente de Bob . Quelqu'un a également suggéré de poser la question ici. Quelqu'un a déjà posé une question liée à ce problème ici - sous- forêt de poids minimum de cardinalité donnée - mais pour autant que je comprends cela...
Un ensemble de frappe d'une famille est un sous-ensemble de tel que pour . Le problème pour trouver un ensemble de frappe minimum d'une famille donnée est NP-difficile en général, car il généralise le problème de couverture de vertex. Maintenant ma question est:H ⋃ n i = 1 S i H ∩ S i ≠ ∅ 1 ≤ i ≤...