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

From

Stanislav Shwartsman (2:400/520)

To

Alexander Shmidt

Date

2002-07-28T22:20:49Z

Area

RU.ALGORITHMS

Hello Alexander!

27 Jul 02 11:38, you wrote to me:

 AS>>> Именно _зачач_ - да, сколько угодно придумать можно, но именно
 AS>>> типов, АФАИК - 7 (по крайней мере так пишут на всех сайтах
 AS>>> всевозможных ВУЗов в разделах планов учебы).
 SS>>  Что значит типов ?
 SS>>  Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и
 AS> Хотя бы эти опиши, если не трудно.

 AS> Кстати, VERTEX COVER - это, случайно, не "выпуклая оболочка"?

 Выпуклая оболочка это тривильный алгоритм, выполнимый за время n*log(n),
 где кол-во точек-вершин. Этот алгоритм в любом ВУЗе проходят на
 вычислительной геометрии.

 SS>> которые по причине их относительной простоты изучают в ВУЗах
 SS>> никак не являются ТИПАМИ NP-полных задач. Вообще не слышал ни
 SS>> слова о какой-либо классификации в этой области.

 AS> Ничего возразить не могу. Просто, в свое время, искал инфу по
 AS> NP-полным задачам и все время натыкался на текст учебного плана
 AS> какого-нибудь ВУЗа, где была строчка: "7 основных типов NP-полных
 AS> задач". Стало интересно, что за...

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

 1. Circuit-SAT

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

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

 3. Clique

 4. Vertex Cover

 5. Set Cover

 6. Hamilton Cycle

 7. Travelling Salesman Problem

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

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

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

 SS>>  Список NP-полных задач получается очень просто. Сначала была
 SS>> одна известная NP-полная задача, потом была доказана, что
 SS>> существует редукция другой задачи к этой первой и NP-полных задач
 SS>> стало две. Список задач пополняется путем доказательства редукции
 SS>> твоей задачи к любой задаче из списка.

 AS> Печально. Хотелось бы, чтобы хоть как-то были описаны основные группы
 AS> подобных между собой задач, а то лопатить тысячу примеров...

 IMHO не существует основных групп ...

 SS>>>> An Annotated List of Selected NP-complete Problems
 SS>>>> Там перечисленно 88 проблем, вот первая десятка:
 AS>>> Чувствую, придется все перечитать. :(
 SS>>  Это я еще скромный сайтик выбрал. Есть списки длинной в тысячу
 SS>> проблем и более.
 AS> Во-во.

 SS>>  То есть как ни анализируй ТОЧНО опеределить местонахождение мины
 SS>> не удастся. Например известно, что осталась только одна мина и
 SS>> есть 2 клетки кандидата на ее местонахождение. Что будешь делать ?

 AS> Я ж тебе говорю: речь ведется о случае, когда начальное положение
 AS> задано так, что заведемо имеет аналитическое решение. То есть,
 AS> предложеный тобой случай противоречит условию и нами не
 AS> рассматривается.

 И где это в условии задачи так было сказано ?
 И вообще - нефиг спорить, у нас и других проблем хватает !

 AS> Т.ч. была задача, и писали люди алгоритмы ее решения, и проходили
 AS> решения по тестам. И придумывали друг другу контрпримеры, на которых у
 AS> одних алгоритм срабатывал, а у других - комп медитировал над заданием
 AS> часами. (И я там был, и решенье носил, не все тесты прошло да в зачет
 AS> не попало :) )

 AS>>> ЗЫ: и все-таки, задачу о нахождении наименьшег гамильтонова пути
 AS>>> можно свести к ЗК(ака - наименьший гамильтонов цикл)? Идеи есть,
 AS>>> но они сыроваты...
 SS>>  А IMHO если можно, то уже даавно свели. Посмотри в списках.

 AS> Спасибо, обязательно гляну (один препод интересовался ссылкой, где
 AS> было бы определено, что задача о нахождении наименьшего гамильтонова
 AS> цикла - NP-полная).

 Это мы на лекциях проходили :)

    E-mail: gate@fidonet.org.il
    Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye !
Stanislav     (AKA Night's Man)                        [Team Technion]
---
 * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)