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 N P z zamortyzowanym (przypadkiem średnim) czasem pracy O ( n k ) dla stałej k ?$P \neq NP$$NP$$O(n^k)$$k$
• Czy są jakieś problemy, które są -hard które są również w B P P , a nawet P P ?$NP$$BPP$$PP$

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

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

Podsumowanie: jest rzeczywiście możliwe.

$O(n)$

$NP$