Kann ein NP-hartes Problem im Durchschnitt polynomisch sein?

Ich frage mich, ob es -harte Probleme gibt, die im Durchschnitt "polynomisch" sind. Ich denke, es gibt zwei Möglichkeiten, dies zu interpretieren. $NP$

Wenn , kann es einen Algorithmus geben, der ein -hartes Problem mit einer amortisierten (Durchschnittsfall) Laufzeit von für eine Konstante löst ? $P \neq NP$ $NP$ $O(n^k)$ $k$
Gibt es irgendwelche Probleme, die -hart sind, die auch in oder sogar ? $NP$ $BPP$ $PP$

Kann jemand eine dieser Fragen beantworten oder eine Referenz angeben?

complexity-theory reference-request np-complete probabilistic-algorithms amortized-analysis jmite
quelle

Diese Frage tauchte vor einiger Zeit

lPlant

Ah, ausgezeichnet! Soll ich diese Frage dann schließen / löschen?

Jmite

@jmite: Dies kann nützlich sein, um hier zu bleiben, also vielleicht eine schnelle (Selbst-) Antwort mit einer Referenz hier posten?

Raphael

Ich möchte nur darauf hinweisen, dass die Amortisation nicht der durchschnittlichen Laufzeit entspricht.

Gardenhead

P H \subseteq P^{P P}

$PH \subseteq P^{PP}$

Kann ein NP-hartes Problem im Durchschnitt polynomisch sein?

Antworten: