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

From

Alexander Shmidt (2:464/34.74)

To

Stanislav Shwartsman

Date

2002-07-27T11:38:04Z

Area

RU.ALGORITHMS

      ><  ┼  ><  ┼  ><   Хау, бледнолицый  Stanislav!   ><  ┼  ><  ┼  ><
    (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)

 Эй, уважаемые Stanislav Shwartsman и Alexander Shmidt! Что за "Типы NP-полных задач", а где же яйца?!

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

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

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

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

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

 AS>>>> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
 SS>>> Это самостоятельный первоапрельский прикол.
 AS>> В каком смысле?
 SS>  В том самом смысле, что статья, в которой "сапер" называется сабжем
 SS>  была написана к 1 апреля. Между прочим в этой эхе этот вопрос уже
 SS>  несколько раз обсуждался.
Помню, было такое. Но я с этой задачей на заочной олимпиаде встречался и ее специфичность показалось довольно интересной.

 SS>>> Между прочим я русским языком тебе в нетмыле объяснял, что
 SS>>> "сапер" в общем виде задача не разрешимая. Существует несколько
 SS>>> раскладов, при которых просто невозможно определить где мина из
 SS>>> известных данных. Остается только наугад, а значит задача
 SS>>> решения не имеет.
 AS>> Тут перебор ведется так: в месте, где неределенно - мина может
 AS>> стоять, а может и не стоять, ставится фиктивная мина и
 AS>> анализируется, возможен ли такой расклад (возможно придется
 AS>> ставить еще фиктивные мины и если все они не могут стоять на
 AS>> своих местах - это одна из причин, почему эта не может стоять на
 AS>> поставленном нами месте; тут, очевидно, можем падать в такую
 AS>> зверскую рекурсию, что дай нам боже дожить до такой техники, чтоб
 AS>> это правильно посчитать). Если получилось, что мина стоять на
 AS>> этом месте ну никак не может - открываем поле. И так далее...
 SS>  И так далее, пока не придем к положению, с которого не знаем куда
 SS>  продолжать. Сейчас опять начнется спор, а где-то через месяц
 SS> найдется кто-то, кому не лень сесть и построить пример, не имеющий
 SS> решения.
Да че там придумывать - в "сапера", что ли, не играли? :)

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

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

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

Good bye, mister Shwartsman                     _
                                               /_|  _  _    _/
                                     Smith,   (  | (/ (- /) /   Smith...
                                                  _/
... Относись к себе так, как хочешь, чтоб относились к тебе (c) XAR
--- Что за омлет, а где ВинАмп?
 * Origin: Масяня - девочка, живущая в сети. (2:464/34.74)