Questions sur les problèmes les plus difficiles en NP, c'est-à-dire ceux qui peuvent être résolus en temps polynomial par des machines de Turing non déterministes.
J'aimerais savoir s'il y a eu des travaux reliant le code juridique à la complexité. En particulier, supposons que nous ayons le problème de décision "Compte tenu de ce recueil de lois et de ce cas particulier, le défendeur est-il coupable?" À quelle classe de complexité appartient-il? Il y a des...
Les problèmes de sac à dos sont facilement résolus par une programmation dynamique. La programmation dynamique s'exécute en temps polynomial; c'est pourquoi nous le faisons, non? J'ai lu qu'il s'agit en réalité d'un problème NP-complet, ce qui voudrait dire que résoudre le problème en problème...
Existe-t-il des problèmes NP-complets pour lesquels des algorithmes sous-exponentiels ont fait leurs preuves? Je demande des informations générales sur les cas, je ne parle pas de cas particuliers traitables ici. Par sub-exponentielle, j'entends un ordre de croissance supérieur aux polynômes, mais...
J'ai lu l'article de Wikipédia sur " Liste des problèmes NP-complets " et constaté que des jeux comme Super Mario, Pokemon, Tetris ou Bonbons Crush Saga sont sans fin. Comment puis-je imaginer la n-complétude d'un jeu? Les réponses n'ont pas besoin d'être trop précises. Je veux juste avoir un...
Supposons que je suis un programmeur et que j'ai un problème NP-complet dont j'ai besoin pour le résoudre. Quelles méthodes sont disponibles pour traiter les problèmes des PNJ? Existe-t-il une enquête ou quelque chose de similaire sur ce
Existe-t-il des problèmes connus dans (et non dans ) qui ne sont pas terminés? Je crois comprendre qu'il n'y a actuellement aucun problème connu dans ce cas, mais cela n'a pas été exclu comme une possibilité. NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP} S'il y a un problème qui est (et non ) mais pas...
Ainsi, le problème de décision TSP (Traveling salesman problem) est NP complet . Mais je ne comprends pas comment je peux vérifier qu'une solution donnée à TSP est en fait optimale en temps polynomial, étant donné qu'il n'y a aucun moyen de trouver la solution optimale en temps polynomial (car le...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
J'ai un ensemble de paires. Chaque paire est de la forme (x, y) telle que x, y appartiennent à des entiers de la plage [0,n). Donc, si le n est 4, alors j'ai les paires suivantes: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) J'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant...
Comme on le voit dans cette récente bande XKCD et ce récent article de blogde Peter Norvig (et une histoire de Slashdot mettant en vedette ce dernier), "regex golf" (qui pourrait mieux être appelé le problème de séparation des expressions régulières) est le casse-tête de définir l'expression...
Je prends un cours de complexité et j'ai du mal à trouver des réductions entre les problèmes de PNJ. Comment puis-je trouver des réductions entre les problèmes? Y a-t-il une astuce générale que je peux utiliser? Comment dois-je aborder un problème qui me demande de prouver qu'un problème est un...
Il est apparu à beaucoup que dans toutes les preuves de complétude que j'ai lues (dont je me souviens), il est toujours trivial de montrer qu'un problème se trouve dans , et de montrer qu'il s'agit de -hard est la partie ... difficile. Quels sont les problèmes compliqués par dont les vérificateurs...
Énoncé informel du problème: Étant donné une chaîne, par exemple , nous voulons colorer certaines lettres rouges et certaines lettres bleues (et certaines pas du tout), de sorte que la lecture des lettres rouges de gauche à droite donne le même résultat que la lecture seules les lettres...
Cette question a été inspirée par un commentaire sur StackOverflow . En plus de connaître les problèmes NP-complets du livre Garey Johnson, et bien d'autres; existe-t-il une règle empirique pour savoir si un problème ressemble à un problème NP-complet? Je ne cherche pas quelque chose de rigoureux,...
Je m'intéresse à la meilleure façon d'enseigner la complétude NP aux majors en informatique. En particulier, devrions-nous l'enseigner en utilisant des réductions Karp ou en utilisant des réductions Turing? Je pense que les concepts de complétude et de réduction de NP sont quelque chose que chaque...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . Définition du problème Logical Min Cut (LMC) Supposons que est un digraphe non pondéré, et sont deux sommets de , et est accessible à partir de . Le problème...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . Je suis légèrement confus par une terminologie que j'ai rencontrée concernant la complexité des problèmes d'optimisation. Dans une classe d'algorithmes, j'ai...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 7 ans . Dans cet article de Wikipédia sur le problème de la clique dans la théorie des graphes, il déclare au début que le problème de...
Disons qu'il existe un programme tel que si vous donnez un Sudoku partiellement rempli de n'importe quelle taille, il vous donne le Sudoku complet correspondant. Pouvez-vous traiter ce programme comme une boîte noire et l'utiliser pour résoudre le TSP? Je veux dire, y a-t-il un moyen de représenter...
Je cherche des indices dans une question posée par mon moniteur. Je viens donc de comprendre que ce problème de décision est N P - c o m p l e t eNP-complete\sf{NP\text{-}complete} : Dans un graphe , y a-t-il un arbre couvrant dans qui contient un ensemble exact de S = { x 1 , x 2 , … , x n } comme...