Quels sont les problèmes pratiquement insolubles dans le monde de la programmation ?

Question

Le problème du voyageur de commerce est dit être pratiquement "insoluble" lorsque le nombre de nœuds augmente.

Quels autres problèmes de programmation sont considérés comme insolubles ?

Answer 1

Tout d'abord, il y a une grande différence entre les problèmes insolubles et les problèmes difficiles à résoudre. Je sais que cela semble évident, mais beaucoup de gens qualifient les problèmes difficiles (comme le voyageur de commerce) d'insolubles alors qu'il vaut mieux dire qu'ils ne sont pas résolubles efficacement, c'est-à-dire en temps polynomial.

Le problème insoluble le plus connu est le problème de la halte. Voir cette page pour plus d'informations. Une technique courante pour montrer qu'un problème est insoluble consiste à montrer qu'il est équivalent au problème du halting.

Answer 2

Le problème de la halte . Prouvé insoluble.

Answer 3

Créer un DRM incassable pour le contenu non interactif, où les utilisateurs prévus peuvent toujours utiliser le contenu ...

Answer 4

Internet Explorer 6

Answer 5

Les problèmes indécidables ne peuvent être résolus par aucun algorithme.

http://en.wikipedia.org/wiki/Undecidable%5Fproblem

Les problèmes NP complets peuvent être résolus en temps polynomial de manière non déterministe. Ils sont donc bel et bien résolubles, surtout rapidement sur un ordinateur quantique.

Parmi les exemples de problèmes indécidables, citons le problème de l'arrêt, qui consiste à déterminer, pour un algorithme donné, si celui-ci finit par s'arrêter ou s'il continue indéfiniment (par exemple, dans une boucle infinie). Alan Turing a prouvé que le problème de Halting est indécidable.