Может ли NP-трудная задача быть полиномиальной в среднем?

Мне интересно, есть ли какие-нибудь -hard проблемы, которые являются «полиномиальными» в среднем случае. Я думаю, что есть два способа интерпретировать это? $NP$

Если , может ли быть алгоритм, решающий задачу -hard, с амортизированным (в среднем случае) временем работы для константы ? $P \neq NP$ $NP$ $O(n^k)$ $k$
Есть ли какие-либо проблемы, связанные с твердостью, которые также есть в или даже ? $NP$ $BPP$ $PP$

Может ли кто-нибудь ответить или предоставить ссылку на любой из этих вопросов?

complexity-theory reference-request np-complete probabilistic-algorithms amortized-analysis jmite
источник

Этот вопрос всплыл в теории CS некоторое время назад, вот ссылка cstheory.stackexchange.com/questions/496/…

lPlant

Ах, отлично! Должен ли я закрыть / удалить этот вопрос?

Jmite

@jmite: Это может быть полезно, чтобы сохранить здесь, так что, возможно, опубликовать быстрый (само) ответ со ссылкой здесь?

Рафаэль

Я просто хотел бы отметить, что амортизация не соответствует среднему времени выполнения.

садовод

P H \subseteq P^{P P}

$PH \subseteq P^{PP}$

Может ли NP-трудная задача быть полиномиальной в среднем?

Ответы: