Re: Типы NP-полных задач

From

Alexander Chislov ()

To

Stanislav Shwartsman

Date

2002-08-19T16:59:07Z

Area

RU.ALGORITHMS

From: Alexander Chislov <arch-vile@rnd.runnet.ru>

SS>  Самые известные, базовые проблемы (которые мы в
SS> ВУЗе изучали):

SS>  1. Circuit-SAT

SS>	Given a boolean combination circuit composed
SS> of AND-OR-NOT gates,
SS>	is satifable ?

SS>  2. Boolean Formula Satisfiability (CNF-SAT,
SS> 3-CNF-SAT)

SS>  3. Clique

SS>  4. Vertex Cover

SS>  5. Set Cover

SS>  6. Hamilton Cycle

SS>  7. Travelling Salesman Problem

SS>  Дерево редукции:

SS>  7 -> 6 -------> 2 -> 1
SS>  5 -> 4 -> 3 /

SS>  Надо - могу PDF с лекциями выслать. На англите.
SS> Основные проблемы
SS>  (см. выше) с доказательствами.


Привет!
Вышли и мне, плиз, лекции по NP задачам. Особенно интересуют задачи про 
р-центры и р-медианы.
Спасибо.

 
-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)