Czy problem trudny dla NP może być średnio wielomianowy?

Zastanawiam się, czy są jakieś problemy twarde typu , które w przeciętnym przypadku są `` wielomianowe ''. Sądzę, że istnieją dwa sposoby interpretacji tego? $NP$

Jeśli , czy może istnieć algorytm rozwiązujący problem twardości z zamortyzowanym (przypadkiem średnim) czasem pracy dla stałej ? $P \neq NP$ $NP$ $O(n^k)$ $k$
Czy są jakieś problemy, które są -hard które są również w , a nawet ? $NP$ $BPP$ $PP$

Czy ktoś może odpowiedzieć lub podać referencje odpowiadające na którekolwiek z tych pytań?

— jmite
źródło

To pytanie pojawiło się w teorii CS jakiś czas temu, oto link cstheory.stackexchange.com/questions/496/…

— lPlant

Ach, świetnie! Czy mam wtedy zamknąć / usunąć to pytanie?

— jmite

@jmite: To może być przydatne do trzymania się tutaj, więc może opublikuj szybką (własną) odpowiedź z referencją tutaj?

— Raphael

Chciałbym tylko zauważyć, że amortyzacja nie jest tym samym, co średni czas trwania sprawy.

— ogrodnik

P H \subseteq P^{P P}

$PH \subseteq P^{PP}$

Wydaje się, że na pytanie CSTheory.SE udzielono odpowiedzi .

Podsumowanie: jest rzeczywiście możliwe.

$O(n)$

$NP$

— jmite
źródło