Qu'est-ce que la NP-complétude ?

Sans rentrer dans les détails techniques, on dit d'un algorithme ou d'un problème qu'il est NP-complet si le temps de réponse à une petite question peut être arbitrairement grand. Par arbitrairement grand on entend totalement disproportionné par rapport à la simplicité de la question. 

Oui, mais tout ça n'est que de la théorie ?

Rassurez-nous, ça ne peut pas arriver, si ?
D'ailleurs ça ne m'est jamais arrivé.

Hé bien détrompez-vous, ça peut arriver puisqu'on vous le dit.

1. Lancez Eric 0.1b .

2. Copiez-collez la contine de la souris verte dans la console : 

join
  ([Mouse*mouse] Attribut [Color:Green])
  ([Run*run] Agent mouse)
  (run Location [Grass])
  (run Then [Catch*catch])
  (catch Agent [Person:I*i])
  (catch Patient mouse)
  (catch Instrument [Tail*tail])
  (tail Of mouse)
  (catch Then [Show*show])
  (show Agent i)
  (show Experiencer [Fellow Citizen*fellows])
  (show Then [Tell*tell])
  (tell Agent fellows)
  (tell Experiencer i)
  (tell Theme [Proposition*prop])
  (prop Statement [Dip#1*dip1])
  (dip1 Agent i)
  (dip1 Patient mouse)
  (dip1 In [Liquid Oil])
  (dip1 Then [Dip#2*dip2])
  (dip2 Agent i)
  (dip2 Patient mouse)
  (dip2 In [Liquid Water])
  (dip2 Then [Make*make])
  (make Agent i)
  (make Theme [Snail*snail])
  (snail Attribut [Temperature Hot])
  (tell Then [Put#1*put1])
  (put1 Agent i)
  (put1 Patient mouse)
  (put1 In [Hat*hat])
  (i Possess hat)
  (put1 Then [Say#1*say1])
  (say1 Agent mouse)
  (say1 Experiencer i)
  (say1 Theme [Temperature*temp])
  (temp Attribut [Too High])
  (say1 Then [Put#2*put2])
  (put2 Agent i)
  (put2 Patient mouse)
  (put2 In [Drawer*drawer])
  (put2 Then [Say#2*say2])
  (say2 Agent mouse)
  (say2 Experiencer i)
  (say2 Theme [Light*light])
  (light Attribut [Too Low])
  (say2 Then [Put#3*put3])
  (put3 Agent i)
  (put3 Patient mouse)
  (put3 In [Trousers*trousers])
  (i Possess trousers)
  (put3 Then [Poo*poo])
  (poo Agent mouse)
  (poo Repeat [Times 3]).

3. Copiez-collez cette requête :

select
  ([*] Then [*])([*] Then [*])([*] Then [*])
  ([*] Then [*])([*] Then [*])([*] Then [*])
  ([*] Then [*])([*] Then [*])([*] Then [*]).

4. Allez faire la sieste. Lissez le cycle de DUNE .

C'est grave docteur ?

C'est impossible à diagnostiquer. L'exemple donné ci-dessus est clairement pathologique puisque le graphe demandé est sacrément non-connexe . Cependant rien ne dit que ça ne pourrait jamais arriver dans des conditions normales d'utilisation. Heureusement on constate (empiriquement) que ça serait l'exception plutôt que la règle.

Appel à témoins

Si jamais vous aviez la chance d'observer un comportement étrange (une réponse sans fin, un temps de réponse anormalement long,...) veuillez me MP l'exemple des données et la question qui ont engendré (de façon reproductible) le comportement pathologique. Ce genre d'information est d'une valeur capitale pour moi.

Merci à vous d'avoir lu cet article.