J
Du wirfst da ein paar Sachen durcheinander, und zwar: Laufzeit eines Algorithmus und Komplexität eines Problems.
Grundsätzlich gilt folgendes: Die Komplexität eines Problems ist die Laufzeit des schnellsten Algorithmus, der dieses Problem löst. Und eben nicht die Laufzeit eines beliebigen Algorithmus.
Betrachten wir mal das Sortierproblem. Eingabe ein array mit n Zahlen, Ausgabe ein Array mit den gleichen n Zahlen. Auch hier gibt es n! viele Möglichkeiten.
Trotzdem existieren Algorithmen, die sowas in Polynomialzeit lösen.
Damit ein Problem nicht in P liegt muss man nicht einen Algorithmus angeben, der langsamer ist, sondern man muss zeigen, dass es keinen Algorithmus gibt (garkeinen geben kann!), der das Problem in Polynomialzeit löst. Das ist im allgemeinen bedeutend schwieriger.
Die Schranken, die Du vorgeschlagen hast beschränken zwar die Anzahl der Möglichkeiten, aber es könnte ja auch Algorithmen geben, die noch viel schlauer vorgehen. Ich glaube ich hatte im Netz mal was gefunden, dass das n-Damen-Problem ebenfalls in Linearzeit lösbar ist.