Обсуждаются основные понятия теории вычислительной сложности. Наряду с хорошо известными классами P, NP и NPC рассматривается иерархия классов NP-трудных задач с точки зрения их аппроксимируемости. Вводятся классы PTAS, APX и понятия наиболее сложных задач в этих классах. Обсуждаются типичные представители этих классов среди оптимизационных задач.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 2007, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2007, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:51)