si N=42, quel que soit le nombre n de nombres à additionner on peut résoudre le pb en O(n) opérations (le 42 influence juste la constante du O).
mais si N=10^n, on sera incapables de résoudre ça en temps polynomial en n, bien que la description du problème tienne encore sur O(n) bits... (la raison c'est qu'avec des N super élevés on peut encoder d'autres problèmes NP-complets comme 3-SAT, chose impossible si on se restreignait à N faible)
« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)