À propos de $P=NP?$

Nous savons déterminer la complexité d'une algorithme. Nous attribuons typiquement à un problème la complexité algorithmique du meilleur algorithme connu pour le résoudre.

Une complexité algorithmique qui s'exprime sous la forme d'un polynôme est typiquement un problème qu'il est raisonnable de confronter et pour lequel des optimisations peuvent ramener un problème difficile à un niveau de difficulté plus raisonnable. On parle ici de la famille des problèmes de complexité $P$.

Quand un problème est tel que sa complexité algorithmique ne s'exprime pas sous forme d'un polynôme, on dit qu'il appartient à la famille des problèmes $NP$ (non-déterministe polynômial), au sens où seule une procédure de décision non-déterministe (une sorte d'oracle) pourrait ramener la complexité de l'algorithme en question à quelque chose s'exprimant sous la forme d'un polynôme.

La famille des problèmes NP-complets est particulièrement intéressante, au sens où elle se compose de problèmes $NP$ qui ont ceci en commun qu'il existe un algorithme de complexité polynomiale pour traduire chacun d'eux en un autre de la même famille, et et au sens où dans chaque cas il existe un algorithme de complexité polynomiale pour vérifier qu'une solution est correcte.

La question de savoir si $P=NP$ ou si $P \ne NP$ est l'un des problèmes les plus difficiles et les plus fondamentaux de l'informatique. C'est typiquement en attaquant des problèmes NP-complets que l'on cherche à résoudre cette question particulièrement profonde.

Incarnations célèbres des problèmes NP-complets

Bien que la NP-complétude soit un domaine vaste contenant une infinité de variantes, certaines formulations du problème $P=NP?$ sont plus célèbres que d'autres. En voici quelques-unes (une liste plus riche est disponible sur https://en.wikipedia.org/wiki/List_of_NP-complete_problems)

Problème de la satisfaction d'expressions booléenne (SAT)

Le théorème de Cook-Levin est à l'origine de l'exploration de la question dont nous discutions ici, et a trait à la satisfaction d'une formule booléenne. Soit une expression logique à $n$ variables, déterminer s'il existe une combinaison de valeurs pour ces variables qui permette de satisfaire cette expression entre dans la catégorie des problèmes NP-complets.

Par satisfaire ici, on entend faire en sorte que l'évaluation de l'expression entière donne VRAI. Certaines expressions (la plus simple étant $p \land \lnot p$) ne peuvent être satisfaites.

De manière générale, dans le pire cas :

• Déterminer si une expression à une seule variable peut être satisfaite demande de la vérifier avec deux valeurs
• Déterminer si une expression à deux variables peut être satisfaite demande de la vérifier avec quatre valeurs
• Déterminer si une expression à trois variables peut être satisfaite demande de la vérifier avec huit valeurs
• Déterminer si une expresssion à $n$ variables peut être satisfaite demande de la vérifier avec $2^n$ valeurs, ce qui n'est vraiment pas une complexit polynomiale.

Explications plus détaillées :

• https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

Problème du commis voyageur (Travelling Salesman Problem, TSP)

J'aime bien cette variante car elle me semble l'une des plus simples à exprimer pour des non-mathématicien(ne)s. Essentiellement : supposons un commis voyageur, dont le rôle est d'apporter des paquets à divers endroits, un peu comme un facteur le ferait pour la poste.

Le problème du commis voyageur est simple : quel est le plus court chemin passant par chacun des lieux à visiter (une seule fois dans chaque cas) et le ramenant à son point de départ?

Supposons, pour simplifier le problème, un petit village de cinq maisons et un bureau de poste, qui est le point de départ et d'arrivée de notre commis. Supposons aussi qu'il existe un chemin entre chacun des endroits (ce qui est le pire cas envisageabke), pour que le propos soit le plus simple et le plus direct possible. Dans ce cas :

• Initialement, notre commis a cinq options
• Une fois une première option choisie, il lui en reste quatre pour la prochaine maison
• Il lui en reste ensuite trois
• Puis deux
• Puis une seule maison, suite à quoi il reviendra à son point de départ.

Exprimé sous forme d'une formule, la complexité de ce problème pour une village de cinq maisons est $O(5 \times 4 \times 3 \times 2 \times 1 \times 1)=O(5!)$. Le problème est que pour $n$ maisons, la complexité de ce problème est $O(n!)$ ce qui est dément, et n'est nettement pas une complexité polynomiale.

Pour quelques explications plus détaillées :

• https://en.wikipedia.org/wiki/Travelling_salesman_problem
• http://www.math.princeton.edu/tsp/
• http://www.math.uwaterloo.ca/tsp/

#ifndef VILLE_H
#define VILLE_H
#include <iosfwd>
#include <vector>
class Ville {
   std::vector<std::vector<int>> distances;
   const int nvilles;
public:
   Ville(int nvilles);
   int nb_villes() const noexcept {
      return nvilles;
   }
   const std::vector<int>& operator[](int n) const {
      return distances[n];
   }
   std::vector<int>& operator[](int n) {
      return distances[n];
   }
};
std::ostream& operator<<(std::ostream&, const Ville&);
#endif

#include "Ville.h"
#include <random>
#include <string>
#include <ostream>
using namespace std;
//
// Complexité (nvilles == N)
// - O(N^2)
//
Ville::Ville(int nvilles) : nvilles{nvilles}, distances{ nvilles, vector<int>(nvilles) } {
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<> de{ 0, 1000 };
   for (int i = 0; i < nb_villes(); i++) {
      distances[i][i] = 0;
      for (int j = i + 1; j < nb_villes(); j++)
         distances[i][j] = distances[j][i] = de(prng);
   }
}
//
// Complexité (v.nb_villes() == N)
// - O(N^2)
//
ostream& operator<<(ostream &os, const Ville &v) {
   for (int i = 0; i < v.nb_villes(); ++i)
      os << '\t' << static_cast<char>('a' + i);
   os << endl;
   for (int i = 0; i < v.nb_villes(); ++i) {
      os << static_cast<char>('a' + i);
      for (int j = 0; j < v.nb_villes(); ++j)
         os << '\t' << v[i][j];
      os << endl;
   }
   return os;
}

#include "Ville.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <thread>
#include <chrono>
#include <tuple>
#include <future>
#include <numeric>
#include <iomanip>
using namespace std;
using namespace std::chrono;
class Visite {
   int netapes;
   bool termine;
   vector<bool> deja_visite;
   vector<int> chemin_courant;
   vector<int> chemin_meilleur;
   Ville &ville;
   void trouver_plus_court_chemin() {
      ++netapes;
      if (none_of(begin(deja_visite), end(deja_visite), [](bool b) { return !b; })) {
         if (chemin_meilleur.empty())
            chemin_meilleur = chemin_courant;
         else {
            int dist_meilleur = 0,
                dist_courant = 0;
            for (int i = 1; i < ville.nb_villes(); i++) {
               dist_meilleur += ville[chemin_meilleur[i-1]][chemin_meilleur[i]];
               dist_courant += ville[chemin_courant[i-1]][chemin_courant[i]];
            }
            dist_meilleur += ville[chemin_meilleur[ville.nb_villes()-1]][chemin_meilleur[0]];
            dist_courant += ville[chemin_courant[ville.nb_villes()-1]][chemin_courant[0]];
            if (dist_courant < dist_meilleur)
               chemin_meilleur = chemin_courant;
         }
      } else {
         for (int i = 0; i < ville.nb_villes(); ++i)
            if (!deja_visite[i]) {
               deja_visite[i] = true;
               chemin_courant.push_back(i);
               trouver_plus_court_chemin();
               chemin_courant.pop_back();
               deja_visite[i] = false;
            }
      }
   }
public:
   int nb_etapes() const noexcept {
      return netapes;
   }
   bool est_termine() const noexcept {
      return termine;
   }
   Visite(Ville &v) : ville(v), deja_visite(v.nb_villes(), false), netapes{}, termine{} {
   }
   const vector<int>& TSP() {
      trouver_plus_court_chemin();
      termine = true;
      return chemin_meilleur;
   }
};
template <class F, class M>
   auto tester(F f, M minu) {
      auto avant = minu.now();
      auto res = f();
      auto apres = minu.now();
      return make_pair(res, apres - avant);
   }
int main() {
   constexpr const auto SEP = "----------------------------------------";
   vector<system_clock::duration> temps_tests;
   vector<int> etapes;
   const int MAX_TESTS = 12;
   for (int n = 1; n <= MAX_TESTS; ++n) {
      Ville v{n};
      cout << "Ville de " << n << " arrets:\n" << v << endl;
      Visite visite{ v };
      auto progres = async(
         launch::async, [&visite] {
            for (string s; !visite.est_termine(); this_thread::sleep_for(500ms)) {
               for_each(begin(s), end(s), [](char) { cout << '\b'; });
               s = "Etape(s): " + to_string(visite.nb_etapes());
               cout << s;
            }
         }
      );
      system_clock::duration duree;
      vector<int> chemin;
      tie(chemin, duree) = tester([&visite] { return visite.TSP(); }, system_clock{});
      temps_tests.push_back(duree);
      etapes.push_back(visite.nb_etapes());
      cout << "\n\n" << SEP << "\nMeilleur chemin (index de villes):\n\n-->\t";
      for (auto & n : chemin)
         cout << static_cast<char>('a' + n) << '\t';
      cout << "\n\nDistance totale: ";
      int distance_totale = 0;
      for (vector<int>::size_type i = 1; i < chemin.size(); ++i)
         distance_totale += v[chemin[i-1]][chemin[i]];
      distance_totale += v[chemin[chemin.size()-1]][chemin[0]];
      cout << distance_totale
           << "\n\n" << SEP << "\nNb total d'etapes: " << visite.nb_etapes()
           << " en " << duration_cast<milliseconds>(duree).count() << " ms.\n"
           << SEP << "\n" << endl;
      progres.wait();
   }
   cout << "\n\nTemps des tests (ms):";
   auto largeur = accumulate(begin(temps_tests), end(temps_tests), 0, [](int so_far, system_clock::duration d) {
      auto res = 0;
      auto n = duration_cast<milliseconds>(d).count();
      while (n) {
         n /= 10;
         ++res;
      }
      return res;
   });
   for (vector<int>::size_type i = 0; i < etapes.size(); ++i)
      cout << "\n\t" << setw(largeur) << duration_cast<milliseconds>(temps_tests[i]).count()
           << " ms. pour " << etapes[i] << " etapes";
   cout << "\n\n" << SEP << "\n" << endl;
}

Lectures complémentaires

Quelques liens pour enrichir le propos.

• La description officielle du problème d'établir lequel de $P=NP$ et $P \ne NP$ est vrai est décrit sur http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
• Collection de liens sur ce problème : http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
• Liens à faire entre ce problème et celui de la nature quantique de l'Univers, texte de 2014 : https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a
• Les conséquences de trouver la réponse à ce problème, résumés dans un article de 2009 par John Markoff : http://www.nytimes.com/2009/10/08/science/Wpolynom.html?_r=3&ref=science&
• L'état des recherches dans ce dossier, colligés par Lance Fortnow en 2009 : http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

Le théorème Cook-Levin :

• https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
• http://www.theoremoftheday.org/LogicAndComputerScience/Cook/TotDCook.pdf

Il arrive régulièrement qu'une preuve ou une réfutation de $P=NP$ ou de $P \ne NP$ soit proposée. Quelques exemples parmi plusieurs :

• https://romvf.wordpress.com/2011/01/19/open-letter/
• https://cartesianproduct.wordpress.com/2011/02/27/no-proof-of-pnp-after-all-yet/
• http://www.andrebarbosa.eti.br/The_Cook-Levin_Theorem_is_False.pdf
• https://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/

Le blogue Gödel's Lost Letter and P=NP de R. J. Lipton et Ken Regan traite régulièrement du problème $P=NP?$. Quelques-uns de leurs textes suivent :

• Texte de 2009 décrivant ce qui se produirait s'il était démontré que $P=NP$? http://rjlipton.wordpress.com/2009/08/20/what-will-happen-when-pnp-is-proved/
• Le problème est-il mal posé? Texte de 2009 : https://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem/
• Une preuve du théorème de Cook, texte de 2013 : https://rjlipton.wordpress.com/2013/10/10/proving-cooks-theorem/
• En 2010, une preuve de $P \ne NP$ a été proposée par Vinay Deolalikar et a beaucoup fait discuter (voir http://gregbaker.ca/blog/2010/08/07/p-n-np/, http://www.scottaaronson.com/blog/?p=456, http://www.ugcs.caltech.edu/~stansife/pnp.html et ce qui suit... remarquez les dates sur les articles qui suivent; il y en a à peu près chaque jour) :
  • le texte en soi : http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
  • présentation en surface de cette possible preuve : https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
  • texte mettant en relief quelques-uns des points plus « rugueux » de cette proposition : https://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
  • suggestions, appuis et compléments d'autres luminaires de ce domaine : https://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/
  • réplique de Vinay Deolalikar aux critiques de sa proposition : https://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%E2%89%A0np-proof/
  • une faille irrémédiable? https://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/
• À propos de la difficulté inhérente de démontrer $P=NP$ ou $P \ne NP$ :
  • en 2011, texte qui met en relief qu'il est plus facile de croire à la magie qu'à une démonstration formelle de $P \ne NP$ :  https://rjlipton.wordpress.com/2009/10/11/magical-results-and-pnp/
  • texte de 2012 qui présente des « barrières » infranchissables à la résolution de ce problème, du moins selon certains angles d'approche : https://rjlipton.wordpress.com/2012/09/26/how-not-to-prove-integer-factoring-is-in-p/
  • texte de 2012 qui cherche à exprimer pourquoi un problème comme TSP résiste tellement à une expression simplificatrice : https://rjlipton.wordpress.com/2012/11/29/barriers-to-pnp-proofs/
• Malgré la faible probabilité qu'une proposition de preuve pour ce problème s'avère juste, mieux vaut les examiner avec attention. Ce texte de 2014 explique pourquoi : https://rjlipton.wordpress.com/2014/04/19/in-praise-of-pnp-proofs/
• En 2014, une démonstration plaçant des bornes sur un autre problème réputé difficile laisse croire qu'il se pourrait que $P=NP$ s'avère : https://rjlipton.wordpress.com/2014/02/28/practically-pnp/

Un  autre blogue intéressant sur les questions ayant trait à la complexité algorithmique est celui de Lance Fortnow et Bill Gasarach. Quelques textes :

• Qu'est-ce qui donne lieu de croire que $P \ne NP$? Texte de 2014 : http://blog.computationalcomplexity.org/2014/03/why-do-we-think-p-ne-np-inspired-by.html
• le texte ci-dessus est inspiré d'un autre texte (de 2006), par Scott Aaronson cette fois, listant dix raisons de croire que $P \ne NP$ : http://www.scottaaronson.com/blog/?p=122
• Si vous découvrez un algorithme de complexité polynomiale résolvant un problème réputé NP-complet, devriez-vous le révéler publiquement? Texte de 2014 : http://blog.computationalcomplexity.org/2014/04/should-you-reveal-p-np-algorithm.html
• Avons-nous fait des progrès sur le front de cette question? Texte de 2015 : http://blog.computationalcomplexity.org/2015/08/have-we-made-progress-on-p-vs-np.html (mais un indice : on a surtout identifié des approches qui ne fonctionnent pas!)

Résoudre des problèmes NP-Complets en passant par des chemins novateurs :

• Utiliser des moteurs biologiques, article de 2016 par John Timmer : http://arstechnica.com/science/2016/02/np-complete-problem-solved-with-biological-motors/