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

11

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

анонимное
источник
10
Случайное самовосстановление (это скорее определение, чем основное свойство, но я подозреваю, что статья в Википедии даст вам хорошее начало для выяснения того, что вы хотите знать.)
Питер Шор
1
@PeterShor комментарий -> ответить?
Суреш Венкат

Ответы:

18

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

Питер Шор
источник
15

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

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

NPcoNP

Дана Мошковиц
источник