Reve complexe
Par Arthur Milchior le dimanche 20 décembre 2009, 21:00 - Informatique - Lien permanent
Je sais pas pourquoi j'ai rêve ça tout à l'heure, et ça m'est resté au réveil.
Et si, pour une raison étrange et encore inconnue, la question P=?NP avait la réponse étrange suivante:
Pour tout algorithme polynomiale décidant un langage NP-complet, il est impossible de prouver qu'il est polynomiale et décide le langage. Autrement dit, quand bien même P=NP, et quand bien même on aurait un tel algorithme polynomiale, il serait impossible de prouver que cet algo est le bon...
En tout cas, ça assurerait encore du boulot pour les gens de complexité et d'algorithmique pour un bon bout de temps, ce serait bien... quoi que.
Oui, je fais des rêves bizarres.