О современном состоянии
теории Average case complexity Левина
Аннотация
Для многих NP-полных задач (например, для задачи выполнимости) имеются
полиномиальные алгоритмы,
которые работают правильно для всех входов за исключением ничтожной их
доли (по естественному распределению
вероятностей на входах). Однако для некоторых задач (и естественных
распределений на входах) такие алгоритмы
построить не удается. Для анализа этого явления Левин предложил в 1985
году понятие NP-полной для типичного
входа задачи. В докладе будет рассказано о современном состоянии
теории таких задач.