Probleme vermutet, aber nicht einfach erwiesen

Wir haben viele Probleme, wie die Faktorisierung, die stark vermutet, aber nicht bewiesen werden, dass sie außerhalb von P liegen. Gibt es Fragen mit der entgegengesetzten Eigenschaft, nämlich, dass sie stark vermutet werden, aber nicht bewiesen werden, dass sie innerhalb von P liegen?

Eine der plausiblen Antworten wäre vor zwei Jahrzehnten das Testen der Primalität : Es gab Algorithmen, die in randomisierter Polynomzeit abliefen, und Algorithmen, die in deterministischer Polynomzeit unter einer plausiblen zahlentheoretischen Vermutung abliefen, aber keine bekannten deterministischen Polynomzeitalgorithmen. Im Jahr 2002 änderte sich dies mit dem bahnbrechenden Ergebnis von Agrawal, Kayal und Saxena, dass der Primärtest in P. enthalten ist. Daher können wir dieses Beispiel nicht mehr verwenden.

Ich würde Polynomidentitätstests als Beispiel für ein Problem anführen, bei dem die Wahrscheinlichkeit groß ist, dass es sich um P handelt, bei dem es jedoch niemandem gelungen ist, dies zu beweisen. Wir kennen randomisierte Polynom-Zeit-Algorithmen zum Testen der Polynomidentität, aber keine deterministischen Algorithmen. Es gibt jedoch plausible Gründe zu der Annahme, dass die randomisierten Algorithmen derandomisiert werden können.

Beispielsweise wird in der Kryptographie stark angenommen, dass hochsichere Pseudozufallsgeneratoren existieren (z. B. ist AES-CTR ein vernünftiger Kandidat). Und wenn dies zutrifft, sollte das Testen der Polynomidentität in P erfolgen. (Verwenden Sie beispielsweise einen festen Startwert, wenden Sie den Pseudozufallsgenerator an und verwenden Sie dessen Ausgabe anstelle von Zufallsbits. Es würde eine enorme Verschwörung erfordern, damit dies fehlschlägt. ) Dies kann mit dem Zufalls-Orakel-Modell formalisiert werden. Wenn wir Hash-Funktionen haben, die durch das Zufalls-Orakel-Modell geeignet modelliert werden können, folgt daraus, dass es einen deterministischen Polynom-Zeit-Algorithmus zum Testen der polynomiellen Identität gibt.

Weitere Informationen zu diesem Argument finden Sie in meiner Antwort zu einem verwandten Thema und meinen Kommentaren zu einer verwandten Frage .

Es ist eine schwierige Frage, weil es keinen Konsens gibt. Es gibt immer noch Leute , die vermuten , dass .$P=NP$

Aber meiner Meinung nach ist der Graph Isomorphism das bemerkenswerteste Problem bei einer signifikanten Vermutung, dass es sich um handelt$P$

Aber niemand weiß es wirklich.

Im Allgemeinen wird die "Vermutung, dass es in " selten sein. Wir nehmen nur an, dass ein Problem in P liegt, wenn wir dafür bereits keinen polynomialen Zeitalgorithmus haben. Aber nach all den Jahren keinen P- Algorithmus dafür finden zu können , wird wahrscheinlich eher als "Beweis" dafür gesehen, dass das Problem schwierig und nicht einfach ist.$P$$P$$P$

$\sf NP\cap coNP$$e^{O(\sqrt{n})}$$n$$\sf P$