Un p’tit 1/4h de science sur P≠NP ?

Le problème P≠NP est une question fondamentale en informatique théorique qui interroge la relation entre deux types de problèmes.

P représente les problèmes que l’on peut résoudre rapidement avec un ordinateur, comme trier une liste ou additionner des nombres.

NP désigne les problèmes dont on peut vérifier rapidement une solution, même si on ne sait pas la trouver rapidement.

Par exemple, trouver une aiguille dans une botte de paille est difficile, mais une fois trouvée, il est facile de confirmer qu’il s’agit bien d’une aiguille.

La question est donc : si la vérification est rapide, la résolution l’est-elle aussi ?

Les chercheurs pensent que P≠NP, c’est-à-dire qu’il existe des problèmes dont les solutions sont vérifiables rapidement, mais pas trouvables rapidement.