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

From

Stanislav Shwartsman (2:400/520)

To

Alexander Shmidt

Date

2002-07-26T09:22:26Z

Area

RU.ALGORITHMS

Hello Alexander!

25 Jul 02 09:16, you wrote to me:

 AS> Именно _зачач_ - да, сколько угодно придумать можно, но именно типов,
 AS> АФАИК - 7 (по крайней мере так пишут на всех сайтах всевозможных ВУЗов
 AS> в разделах планов учебы).

 Что значит типов ?

 Те ЗАДАЧИ, с которых все началось (3-SAT, VERTEX COVER и т.д) и которые
 по причине их относительной простоты изучают в ВУЗах никак не являются
 ТИПАМИ NP-полных задач. Вообще не слышал ни слова о какой-либо
 классификации в этой области.

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

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

 Это я еще скромный сайтик выбрал. Есть списки длинной в тысячу проблем
 и более.

 AS>>> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
 SS>>  Это самостоятельный первоапрельский прикол.
 AS> В каком смысле?

 В том самом смысле, что статья, в которой "сапер" называется сабжем
 была написана к 1 апреля. Между прочим в этой эхе этот вопрос уже
 несколько раз обсуждался.

 AS> Вот, хоть убей, переписку в мыле не помню :)

 Тогда извини, наверно это был не ты :)

 SS>>  Между прочим я русским языком тебе в нетмыле объяснял, что
 SS>> "сапер" в общем виде задача не разрешимая. Существует несколько
 SS>> раскладов, при которых просто невозможно определить где мина из
 SS>> известных данных. Остается только наугад, а значит задача решения не
 SS>> имеет.

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

 И так далее, пока не придем к положению, с которого не знаем куда
 продолжать. Сейчас опять начнется спор, а где-то через месяц найдется
 кто-то, кому не лень сесть и построить пример, не имеющий решения.
 То есть как ни анализируй ТОЧНО опеределить местонахождение мины не
 удастьсь. Например известно, что осталась только одна мина и есть 2
 клетки кандидата на ее местонахождение. Что будешь делать ?

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

 А IMHO если можно, то уже даавно свели. Посмотри в списках.

    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)