Le problème du cycle hamiltonien (HC) consiste à trouver un cycle passant par tous les sommets d'un graphe non orienté donné. Le problème des vendeurs ambulants (TSP) consiste à trouver un cycle qui passe par tous les sommets d'un graphique pondéré sur les bords et minimise la distance totale...
Voici le problème: Nous avons un carré avec des nombres de 1..N dans certaines cellules. Il est nécessaire de déterminer s'il peut être complété par un carré magique. Exemples: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Ce problème est-il NP-complet?...
Étant donné un automate A (déterministe ou non déterministe, je pense que cela n'a pas beaucoup d'importance) et un seuil n , A accepte-t-il un mot contenant au plus n lettres distinctes? (Par k lettres différentes, je veux dire que aabaa a deux lettres distinctes, a et b .) J'ai montré que ce...
Est-il difficile de trouver la solution la plus simple à un système d'équations linéaires? Plus formellement, considérons le problème de décision suivant: Instance: Un système d'équations linéaires avec des coefficients entiers et un nombre ccc . Question: Existe-t-il une solution au système avec...
Je m'intéresse à la complexité du problème des ensembles dominants (DSP) dans certaines classes de graphes spécifiques qui sont des sous-classes de graphes d' accord . Un graphe est un graphe de chemin non orienté s'il s'agit du graphe d'intersection de sommets d'une famille de chemins dans un...
Un de mes amis me pose le problème de planification suivant sur l'arbre. Je trouve que c'est très propre et intéressant. Y a-t-il une référence pour cela? Problème: Il y a un arbre , chaque arête a un coût de déplacement symétrique de 1 . Pour chaque sommet v i , il existe une tâche qui doit être...
Dans le problème d'extensibilité, on nous donne une partie de la solution et nous voulons décider si nous pouvons l'étendre à une solution complète. Certains problèmes d'extensibilité peuvent être résolus efficacement tandis que d'autres problèmes d'extensibilité transforment un problème facile en...
Est-il connu si le problème posé par le sommet de rétroaction sur les graphes planaires non orientés de degré borné est
Quelqu'un peut-il énumérer des problèmes bien connus qui remplissent les conditions suivantes: 1. has a generalization problem that is known to be NP-complete 2. has not been proved to be NP-complete nor has a known polynomial time solution.
Il y a quelque temps, j'ai publié une demande de référence pour les problèmes de graphe où nous voulons trouver une partition à 2 des bords où les deux ensembles remplissent une propriété sans rapport avec leur cardinalité. J'essayais de prouver que le problème suivant est NP-difficile: Étant donné...
Treewith est un paramètre de graphique important qui indique à quel point un graphique est proche d'être un arbre (bien que pas dans un sens topologique strict). Il est bien connu que le calcul de la largeur d'arbre est NP-difficile. Existe-t-il des classes naturelles de graphiques où la largeur...
Le problème de partition est faiblement NP-complet car il a un algorithme de temps polynomial (pseudo-polynomial) si les entiers d'entrée sont délimités par un polynôme. Cependant, la partition 3 est un problème fortement NP-complet même si les entiers d'entrée sont délimités par un polynôme. En...
Considérons le problème où on nous donne en entrée un graphe acyclique dirigé , une fonction d'étiquetage λ de V vers un ensemble L avec un ordre total < L (par exemple, les entiers), et où on nous demande de calculer le plus petit tri topologique lexicographiquement de G en termes de λ . Plus...
Considérez le problème suivant. Entrée: Un graphique non orienté . Sortie: Un graphique H qui est un mineur de G avec la densité de bord la plus élevée parmi tous les mineurs de G , c'est-à-dire avec le rapport le plus élevé | E ( H ) | / | V ( H ) |
En répondant à cette question sur cstheory , j'ai (officieusement) prouvé à la volée le théorème suivant: Théorème : Pour tout fixe, le probem du cycle hamiltonien reste NP-complet même s'il est limité à des graphes bipartites planaires non orientés de degré 3 maximum qui ne contiennent pas de...
La largeur de l'arbre mesure la proximité d'un graphique avec un arbre. Plusieurs problèmes NP-difficiles sont traitables sur des graphiques avec une largeur d'arbre bornée. Si un problème reste NP-dur sur les arbres, la largeur de l'arbre ne peut pas nous sauver. C'était la motivation derrière une...
Cette question est similaire aux problèmes NP-difficiles sur les arbres : Il existe un grand nombre de problèmes NP-complets qui sont traitables sur les cographies . Y a-t-il des problèmes connus qui restent NP-complets lorsqu'ils sont limités aux cographies? Pour être plus précis, je suis...
Considérez le problème suivant, Étant donné un ensemble de nombres positifs { a 1 , … , a n } dans lesquels k ≥ 3 est une constante, nous voulons partitionner l'ensemble en m sous-ensembles de taille k de sorte que le produit de la somme de chaque sous-ensemble est maximisé.n = k mn=kmn = k m{ a1,...
Sudoku est un puzzle bien connu qui est NP-complet. Le Sudoku binaire est une variante qui n'autorise que les chiffres et 1 . Les règles sont les suivantes.000111 Chaque ligne et chaque colonne doit contenir un nombre égal de zéros et de uns. Chaque ligne et chaque colonne est unique. Aucune ligne...
Cette question est motivée par ce post, pouvez-vous identifier la somme de deux permutations en temps polynomial? et mon intérêt pour les propriétés de calcul des permutations. Une séquence de différences d'une permutation π de nombres 1 , 2 , … n + 1 est formée en trouvant la différence entre tous...