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

NP Complet Les questions sont comme ça.

Answer 2

Problème de correspondance postale :

Étant donné deux listes de mots (a1, a2, , an) et (b1, b2, , bn), trouvez une séquence d'indices pour que les mots concaténés soient égaux.

Par exemple, étant donné les listes (1 : a, 2 : ab, 3 : bba) et (1 : baa, 2 : aa, 3 : bb), la séquence (3, 2, 3, 1) est une solution puisque bba+ab+bba+a = bb+aa+bb+baa.

Ce problème semble pouvoir être résolu par un algorithme (il s'agit simplement de trouver une séquence pour que les chaînes de caractères correspondent, rien de complexe comme les machines de Turing n'est impliqué) ; mais il est indécidable, tout comme le problème de l'arrêt.

Answer 3

Amener les programmeurs à documenter leur code.

Answer 4

En fait, les problèmes NP-complets, comme le voyageur de commerce, sont difficiles à résoudre. en général mais une instance spécifique (ou même le plus dans un certain domaine [par exemple, la compilation de code Haskell]) peut être facile à résoudre !

Il existe un grand nombre de problèmes qui sont, en théorie, incroyablement difficiles - mais comme les cas difficiles sont très rares et plutôt artificiels, ils sont en fait très faciles à résoudre. Deux exemples de ce phénomène que je trouve particulièrement intéressants sont tous deux NP complets. La vérification de type en Haskell est l'un d'eux : en fait, l'inférence de type générale en Haskell est pire que NP complète : la validation de type est NP-complète ; l'inférence de type est NP-dure. Mais sur du code réel, c'est effectivement approximativement linéaire. L'autre problème est un problème logique appelé 3-SAT. J'ai assisté une fois à une excellente conférence d'un type nommé Daniel Jackson, qui parlait d'un langage de spécification formel qu'il avait conçu, appelé Alloy. Alloy réduit la vérification de ses spécifications à 3-SAT. Dan expliquait cela en disant : "La mauvaise nouvelle est que l'analyse des spécifications d'Alloy est 3-SAT, donc exponentielle et NP-complète. Mais la bonne nouvelle est que l'analyse des spécifications d'Alloy est 3-SAT, et que nous pouvons donc la résoudre très rapidement.

- MarkCC

Answer 5

Tous les langages de programmation ne peuvent pas avoir des problèmes résolubles. Par exemple, je préfère faire un regrep avec perl qu'avec applescript. La plupart des langages de programmation tels que le PHP ont des "bugs" qui ne peuvent être résolus tant que quelqu'un de l'équipe php ne corrige pas le moteur php.

Il peut vouloir dire que le code devient très très compliqué et qu'il ne vaut pas la peine de terminer le projet parce qu'il prend trop de temps.