• Февраль 11, Март 3, Апрель 14, 2008
  • Николай Верещагин
  • О современном состоянии теории Average case complexity Левина
  • Аннотация
  • Для многих NP-полных задач (например, для задачи выполнимости) имеются полиномиальные алгоритмы, которые работают правильно для всех входов за исключением ничтожной их доли (по естественному распределению вероятностей на входах). Однако для некоторых задач (и естественных распределений на входах) такие алгоритмы построить не удается. Для анализа этого явления Левин предложил в 1985 году понятие NP-полной для типичного входа задачи. В докладе будет рассказано о современном состоянии теории таких задач.
  • конспект доклада: ps