Qu’est-ce qui est difficile en calcul ?
Calcul difficile : un problème pour lequel il n’existe aucun algorithme éprouvé permettant de le résoudre en un temps raisonnable. Plus le problème est grand, plus il est difficile à résoudre par tous les moyens.
Qu’est-ce qui rend certains problèmes de calcul difficiles et faciles ?
Un problème est » difficile » s’il nécessite (ou nous pensons qu’il nécessite) de » grandes » ressources de calcul pour être résolu, et » facile » s’il ne le fait pas. « Large » dépend du contexte mais, dans la plupart des contextes, un problème qui peut être résolu en temps polynomial est considéré comme » facile « .
Qu’est-ce que cela signifie pour un problème d’être NP-difficile ?
Un problème est NP – difficile si un algorithme pour le résoudre peut être traduit en un seul pour résoudre n’importe quel problème NP – problème (temps polynomial non déterministe ) . NP – difficile signifie donc « au moins aussi difficile que n’importe quel problème NP – « , bien qu’il puisse, en fait, être plus difficile.
Comment savoir si vous avez un problème NP-difficile ?
En termes simples, un problème est dit NP – difficile si la découverte d’un algorithme rapide pour résoudre le problème signifie qu’il y aura des algorithmes rapides pour résoudre tous les problèmes NP – difficiles .
Tous les problèmes d’optimisation sont-ils NP difficiles ?
Aucun problème d’optimisation n’est NP – complet , car seuls les problèmes de décision sont dans NP . Les problèmes d’optimisation peuvent avoir des problèmes de décision liés qui sont dans NP , et ces problèmes de décision liés peuvent être NP – complets .
Quel est le problème difficile NP avec exemple?
Exemples . Un exemple de problème NP – difficile est le problème de la somme des sous-ensembles de décision : étant donné un ensemble d’entiers, est-ce que tout sous-ensemble non vide d’entre eux s’additionne à zéro ? C’est un problème de décision et il se trouve qu’il est NP – complet .
Les problèmes d’optimisation peuvent-ils être dans NP?
La classe de complexité NP ne contient que des problèmes de décisions par définition. Il n’y a donc aucun problème d’optimisation .
Comment prouver qu’un problème d’optimisation est NP difficile ?
1 réponse. Un algorithme de temps polynomial pour résoudre la version d’ optimisation du problème résoudrait également la version de décision en temps polynomial (il suffit de comparer la valeur optimale à la valeur cible pour le problème de décision .) Ainsi, si le problème de décision est NP – Complet , alors l’ optimisation le problème est NP – Hard .
P peut-il être réduit à NP ?
C’est ce que signifie NP . (Par exemple, résoudre Sudoku est NP , car vous pouvez me montrer la solution et je peux vérifier qu’elle est correcte en temps polynomial). Tous les problèmes P sont NP . Ainsi, la « réduction polynomiale en temps d’un problème P à un problème NP » est assez triviale et ne prouve rien de très intéressant.
P est-il égal à NP ?
En gros, P est un ensemble de problèmes relativement faciles, et NP est un ensemble qui comprend ce qui semble être des problèmes très, très difficiles, donc P = NP impliquerait que les problèmes apparemment difficiles ont en fait des solutions relativement faciles.