От худшего к среднему

Существуют ли проблемы, сложность которых в среднем одинакова с их сложностью в худшем случае? Каковы основные свойства этих проблем, которые позволяют свести наихудший случай к среднему?

Этот тип проблемы был предметом небольшого изучения. Вы можете найти ссылки, прибегая к помощи случайного самовосстановления, и статья в Википедии - хорошее место для начала чтения. Есть еще много открытых вопросов.

В записи Википедии, на которую ссылается Питер, упоминается несколько важных примеров проблем, которые приводят к сокращению в наихудшем случае до среднего, например, в постоянном. Кратчайшая векторная проблема (а также связанные с ней задачи решетки) является еще одним важным примером, см. Статью Айтаи и то, что последовало за ней (работы Регева, Мичансио, Пайкерта, ...).

Одно из общих замечаний, которые мы имеем в отношении проблем с редукцией от худшего к среднему, - это следующее (началось с работы Фейгенбаума и Фортнау ): (по крайней мере, для неадаптивных редукций) эти проблемы вряд ли будут завершено для классов, которые (вероятно) не закрыты в дополнении (например, они вряд ли будут NP-полными).

$NP \cap coNP$