"Ich sage nur, dass ich für ein Problem, das in NP, aber nicht in P liegt, einen mehr als polynomiell großen Suchraum durchsuchen muss. (Was zu beweisen wäre, das räume ich ein.)" Dann liefere diesen Beweis bitte. Genau dieser fehlt nämlich. Und das führt uns zurück zur ursprünglichen Frage ob P != NP.
Diesen Beweis liefere ich dir gerne, er ist nämlich sehr leicht: Wenn ich nur einen polynomiell großen Suchraum durchsuchen muss und die Lösung in polynomieller Zeit überprüft werden kann, dann ist das Problem in P. Diese Aussage ist logisch äquivalent zu der Aussage: Wenn ein Problem nicht in P ist, dann muss ich einen größeren als polynomiellen Suchraum durchsuchen oder die Lösung kann nicht in polynomieller Zeit überprüft werden. Per definitionem kann die Lösung eines Problems, das in NP ist, in polynomieller Zeit überprüft werden. Daraus folgt, dass ich bei einem Problem, das in NP, aber nicht in P ist, einen größeren als polynomiellen Suchraum durchsuchen muss (die Lösung kann aber in polynomieller Zeit überprüft werden).
Zumindest das wäre also bewiesen.