Um problema difícil de NP pode ser polinomial em média?

Eu estou querendo saber se existem problemas -Hard que são `` polinomial" no caso da média. Eu acho que existem duas maneiras de interpretar isso? $NP$

Se , pode haver um algoritmo de resolução de um problema -Hard com amortizado (caso médio) tempo de execução por uma constante ? $P \neq NP$ $NP$ $O(n^k)$ $k$
Existem problemas que são -Hard que também estão em , ou mesmo ? $NP$ $BPP$ $PP$

Alguém pode responder ou fornecer uma referência respondendo a uma dessas perguntas?

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

Esta questão surgiu no CS teoria há um tempo atrás, aqui está o link cstheory.stackexchange.com/questions/496/...

lPlant

Ah, excelente! Devo fechar / excluir esta pergunta então?

jmite

@ jmite: Isso pode ser útil para se manter por aqui, então talvez poste uma resposta rápida com uma referência aqui?

Raphael

Gostaria apenas de salientar que amortizado não é o mesmo que tempo médio de execução.

Gardenhead

P H \subseteq P^{P P}

$PH \subseteq P^{PP}$

Um problema difícil de NP pode ser polinomial em média?

Respostas: