Questions liées à la complexité (informatique) de la résolution de problèmes
La plupart des méthodes de cryptage actuelles, telles que RSA, reposent sur la factorisation entière, qui n'est pas considérée comme un problème complexe, mais appartient au BQP, ce qui la rend vulnérable aux ordinateurs quantiques. Je me demande pourquoi il n’existe pas d’algorithme de chiffrement...
Il y a beaucoup de tentatives pour prouver soit ou , et naturellement beaucoup de gens réfléchissent à la question, ayant des idées pour prouver la direction dans laquelle ils veulent aller.P ≠ N PP = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Je sais qu'il a été prouvé...
Normalement, dans les algorithmes, nous ne nous soucions pas de la comparaison, de l'addition ou de la soustraction de nombres - nous supposons qu'ils sont exécutés dans le temps . Par exemple, nous supposons cela lorsque nous disons que le tri basé sur la comparaison est O ( n log n ) , mais...
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...
Je pense avoir une compréhension raisonnable des complexités telles que , et .Θ ( n ) Θ ( n 2 )O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) En termes de liste, est une recherche constante, donc il ne fait que prendre la tête de la liste. est l'endroit où je parcourrais toute la...
J'ai une compréhension de haut niveau du problème et je comprends que s'il était absolument "avéré" d'être vrai avec une solution fournie, cela ouvrirait la porte à la résolution de nombreux problèmes du domaine de l'informatique.P=NPP=NPP=NP Ma question est la suivante: si quelqu'un publiait une...
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...
Pourquoi en informatique, toute complexité au plus polynomiale est considérée comme efficace? Pour toute application pratique (a) , les algorithmes de complexité sont bien plus rapides que les algorithmes qui s'exécutent dans le temps, par exemple n 80 , mais le premier est considéré comme...
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...
Il semble que sur ce site, les gens corrigent souvent les autres pour avoir confondu "algorithmes" et "problèmes". Quelle est la différence entre ceux-ci? Comment savoir quand je devrais envisager des algorithmes et des problèmes? Et quel est leur lien avec le concept de langage dans la théorie des...
Dans la théorie de la calculabilité et de la complexité (et peut-être dans d'autres domaines), les réductions sont omniprésentes. Il en existe de nombreuses sortes, mais le principe reste le même: montrez qu'un problème est au moins aussi complexe qu'un autre problème en mappant des instances de à...
Dans les algorithmes et la complexité, nous nous concentrons sur la complexité asymptotique des algorithmes, c'est-à-dire la quantité de ressources qu'un algorithme utilise lorsque la taille de l'entrée va à l'infini. En pratique, nous avons besoin d’un algorithme qui fonctionnerait rapidement pour...
La programmation linéaire (LP) est en P et la programmation entière (IP) est NP-difficile. Mais comme les ordinateurs ne peuvent manipuler les nombres qu’avec une précision finie, un ordinateur utilise en pratique des entiers pour la programmation linéaire. Pour cette raison, LP et IP ne...
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...
Un de mes collègues et moi-même venons de tirer quelques notes d’un de nos professeurs. Les notes indiquent qu'il existe des tâches qu'il est possible de résoudre en temps polynomial (appartiennent à la classe de PF) mais qui ne sont PAS vérifiables en temps polynomial (ne font pas partie de la...
Il y a nnn bacs et mmm type de balles. La iii ième bin a des étiquettes a i , jai,ja_{i,j} pour 1 ≤ j ≤ m1≤j≤m1\leq j\leq m , c'est le nombre attendu de billes de type jjj . Vous commencez avec b jbjb_j boules de type jjj . Chaque boule de type jjj a un poids w jwjw_j et veut placer les boules dans...
Je me demande s'il existe un bon exemple pour un problème NP-difficile facile à comprendre qui n'est pas NP-complet et non indécidable? Par exemple, le problème d'arrêt est NP-Hard, pas NP-Complete, mais il est indécidable. Je crois que cela signifie que c'est un problème pour lequel une solution...
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...
Il existe un algorithme polynomial facile pour décider s'il existe un chemin entre deux nœuds dans un graphe orienté (il suffit de faire un parcours de graphe de routine avec, disons, la profondeur en premier). Cependant, il semble que, de manière surprenante, le problème devienne beaucoup plus...