Простыми словами
Самые известные задачи, входящие в класс NP, следующие:
читать дальше1. Задача выполнимости булевых формул. Булева формула — это (в двух словах) некоторое выражение, которое может принимать значение "истина" или "ложь" в зависимости от значений переменных, в нее входящих. (Переменные тоже могут принимать значения "истина" либо "ложь") "Выполнимость" означает, что при каком-то наборе значений входных переменных формула стала равна единице (истине).
Свидетель — сам набор значений переменных.
2. Задача, известная под названием Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера.
Кликой (clique) в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики — число вершин, содержащихся в ней.
На рисунке красным выделена клика размера четыре.
Есть разные варианты формулировки задачи о клике.
Первый, "облегченный" вариант ее таков: существует ли в заданном графе G клика размера k?
"Настоящая" же задача о клике формулируется следующим образом: в заданном графе G найти клику максимального размера.
Свидетелем здесь являются номера вершин, образующих клику.
На рисунке это номера 2, 3, 6, 7. (Клика размера 4 и будет здесь максимальной)
А вот, например, вершины 2, 3, 6 или 3, 6, 7 — тоже образуют клики размера 3, но они уже не удовлетворяют критерию максимальности.
3. Проблема существования гамильтонова цикла в графе.
Гамильтонов цикл — это совсем просто. Нам нужно выйти из какой-то вершины и вернуться в нее таким образом, чтобы ни в какой промежуточной вершине не побывать дважды.
Вот, например:
вершины 8, 4, 5, 6, 9 образуют Гамильтонов цикл. И он здесь далеко не один.
Свидетель — последовательность вершин, образующих гамильтонов цикл.
4. Задача о коммивояжёре — о, это очень распространенная задача оптимизации! До сих пор на эту тему пишутся и защищаются диссертации. Потому что каждый раз бедному коммивояжеру нужно находить всё новые и новые пути: критериев оптимальности очень много.
Звучит эта задача следующим образом: у нас есть коммивояжер, то есть мы сами и есть тот коммивояжер, которому надо посетить указанный список городов. Нам нужно отыскать самый выгодный маршрут, проходящий через указанные города хотя бы по одному разу. (А если мы нечисты на руку, и не хотим потом встречаться со своими покупателями, то ровно по одному разу — улавливаете требование гамильтонова цикла?)
В условие задачи входят различные критерии выгодности маршрута: как короче, как дешевле, как быстрее по времени, и т.д. и т.п.
Свидетель здесь — просто решение задачи.
5. Существование целочисленного решения системы линейных неравенств.
Свидетель — тоже решение.
Почему я так подробно всё это описываю?
Определение класса NP было бы неполным, если бы я не упомянула вот о каком аспекте. Логически он вытекает из того, что уже было сказано, но всё-таки лучше рассказать о нём в явном виде.
Пусть у нас есть задача из класса NP. Возьмем любую из перечисленных. Например, задачу о гамильтоновом цикле. Если у нас есть свидетель, то остается только проверить, действительно ли указанные вершины можно обойти по разу и вернуться в начальную. Это задача, которую можно решить быстро, то есть задача класса Р. Если проверка дала положительный результат, то есть мы не обманули нашу машину Тьюринга, дав ей "хорошего" свидетеля, она должна выдать ответ "ДА". Если же мы дали неверный совет, неверно нашли свидетеля, машина должна сказать нам "НЕТ". Давайте посмотрим на картинку с гамильтоновым циклом еще раз.
Предположим, я говорю машине: "Свидетель — вершины: 1, 0, 4, 5". Машина отвечает: "НЕТ". Вроде бы, здесь всё понятно, непонятно только, зачем я так подробно об этом пишу. А вот зачем!
Гамильтонов цикл-то на самом деле здесь ЕСТЬ! И даже не один! Так что машина, отвечая "НЕТ" на самом деле отвечает не на вопрос о существовании или несуществовании гамильтонова цикла, а об истинности или ложности нашей подсказки. (Но сама-то машина об этом не знает)
То есть, с точки зрения вопроса о существовании цикла машина ошиблась.
Так вот, такие "ошибки" допустимы.
Зато ошибки в другую сторону недопустимы ни при каких обстоятельствах. Если мы дали машине правильного свидетеля, она ни при каких обстоятельствах не может сказать, что он не подходит!
Кроме того, должна выполняться еще одна вещь! Я пишу об этом как о самоочевидном, но на самом-то деле это надо оговорить отдельно! У нас должна быть построена такая машина Тьюринга, которая была бы способна понять и проверить нашу подсказку! Проверить, правильный ли наш свидетель! Причем, не для единичного случая, а для каждого из возможных.
Итак, подытожить это можно следующим образом.
Задача входит в класс NP, если существует машина Тьюринга, которая по представленному нами свидетелю сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой; причем, каждый данный нами "правильный" свидетель должен "соответствовать" этой машине Тьюринга, то есть она должна его "понимать".
читать дальше1. Задача выполнимости булевых формул. Булева формула — это (в двух словах) некоторое выражение, которое может принимать значение "истина" или "ложь" в зависимости от значений переменных, в нее входящих. (Переменные тоже могут принимать значения "истина" либо "ложь") "Выполнимость" означает, что при каком-то наборе значений входных переменных формула стала равна единице (истине).
Свидетель — сам набор значений переменных.
2. Задача, известная под названием Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера.
Кликой (clique) в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики — число вершин, содержащихся в ней.
На рисунке красным выделена клика размера четыре.
Есть разные варианты формулировки задачи о клике.
Первый, "облегченный" вариант ее таков: существует ли в заданном графе G клика размера k?
"Настоящая" же задача о клике формулируется следующим образом: в заданном графе G найти клику максимального размера.
Свидетелем здесь являются номера вершин, образующих клику.
На рисунке это номера 2, 3, 6, 7. (Клика размера 4 и будет здесь максимальной)
А вот, например, вершины 2, 3, 6 или 3, 6, 7 — тоже образуют клики размера 3, но они уже не удовлетворяют критерию максимальности.
3. Проблема существования гамильтонова цикла в графе.
Гамильтонов цикл — это совсем просто. Нам нужно выйти из какой-то вершины и вернуться в нее таким образом, чтобы ни в какой промежуточной вершине не побывать дважды.
Вот, например:
вершины 8, 4, 5, 6, 9 образуют Гамильтонов цикл. И он здесь далеко не один.
Свидетель — последовательность вершин, образующих гамильтонов цикл.
4. Задача о коммивояжёре — о, это очень распространенная задача оптимизации! До сих пор на эту тему пишутся и защищаются диссертации. Потому что каждый раз бедному коммивояжеру нужно находить всё новые и новые пути: критериев оптимальности очень много.
Звучит эта задача следующим образом: у нас есть коммивояжер, то есть мы сами и есть тот коммивояжер, которому надо посетить указанный список городов. Нам нужно отыскать самый выгодный маршрут, проходящий через указанные города хотя бы по одному разу. (А если мы нечисты на руку, и не хотим потом встречаться со своими покупателями, то ровно по одному разу — улавливаете требование гамильтонова цикла?)
В условие задачи входят различные критерии выгодности маршрута: как короче, как дешевле, как быстрее по времени, и т.д. и т.п.
Свидетель здесь — просто решение задачи.
5. Существование целочисленного решения системы линейных неравенств.
Свидетель — тоже решение.
Почему я так подробно всё это описываю?
Определение класса NP было бы неполным, если бы я не упомянула вот о каком аспекте. Логически он вытекает из того, что уже было сказано, но всё-таки лучше рассказать о нём в явном виде.
Пусть у нас есть задача из класса NP. Возьмем любую из перечисленных. Например, задачу о гамильтоновом цикле. Если у нас есть свидетель, то остается только проверить, действительно ли указанные вершины можно обойти по разу и вернуться в начальную. Это задача, которую можно решить быстро, то есть задача класса Р. Если проверка дала положительный результат, то есть мы не обманули нашу машину Тьюринга, дав ей "хорошего" свидетеля, она должна выдать ответ "ДА". Если же мы дали неверный совет, неверно нашли свидетеля, машина должна сказать нам "НЕТ". Давайте посмотрим на картинку с гамильтоновым циклом еще раз.
Предположим, я говорю машине: "Свидетель — вершины: 1, 0, 4, 5". Машина отвечает: "НЕТ". Вроде бы, здесь всё понятно, непонятно только, зачем я так подробно об этом пишу. А вот зачем!
Гамильтонов цикл-то на самом деле здесь ЕСТЬ! И даже не один! Так что машина, отвечая "НЕТ" на самом деле отвечает не на вопрос о существовании или несуществовании гамильтонова цикла, а об истинности или ложности нашей подсказки. (Но сама-то машина об этом не знает)
То есть, с точки зрения вопроса о существовании цикла машина ошиблась.
Так вот, такие "ошибки" допустимы.
Зато ошибки в другую сторону недопустимы ни при каких обстоятельствах. Если мы дали машине правильного свидетеля, она ни при каких обстоятельствах не может сказать, что он не подходит!
Кроме того, должна выполняться еще одна вещь! Я пишу об этом как о самоочевидном, но на самом-то деле это надо оговорить отдельно! У нас должна быть построена такая машина Тьюринга, которая была бы способна понять и проверить нашу подсказку! Проверить, правильный ли наш свидетель! Причем, не для единичного случая, а для каждого из возможных.
Итак, подытожить это можно следующим образом.
Задача входит в класс NP, если существует машина Тьюринга, которая по представленному нами свидетелю сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой; причем, каждый данный нами "правильный" свидетель должен "соответствовать" этой машине Тьюринга, то есть она должна его "понимать".
@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato
-
-
10.07.2008 в 20:04-
-
10.07.2008 в 21:33Именно так.
Только его обычно не столь конкретно называют английским математиком )))))
-
-
10.07.2008 в 21:35просто я его узнал вначале как отца Этель Лилиан Буль, по мужу Войнич=) а в биографии ее, написанной Е.Таратутой как раз было указанно что Дж.Буль - ирландец=)
-
-
10.07.2008 в 21:42понятно)
как всегда война "физиков"-"лириков" )))
Думаю, ни одни математик в твердой памяти не скажет, что Буль — ирландец)))
Зато литературовед — с дорогой душой)))
Тем более, что родился Буль в Линкольне)
А вот Этель Лилиан — в Корке ))))
-
-
10.07.2008 в 21:44а Линкольн это где??? Не Ирландия?
И У.Р.Гамильтона ирландцем называть нельзя, к вопросу о математиках??
-
-
10.07.2008 в 21:48Линкольн — Англия.
Да нет, Гамильтон как раз ирландец
-
-
10.07.2008 в 21:51ну как говорил кажись, Йёйтс, "ирландство - оно в душе!"=)
это ж Гамильтон, кажется, вырезал формулу на перилах моста?
-
-
10.07.2008 в 22:00да, он))) кажется, с кватернионами бился...
-
-
10.07.2008 в 22:01ага, с этими самыми звирями=)
я читал Кляйна - он почему-то не признает кватернионистов.
-
-
10.07.2008 в 22:26А кто такие кватернионисты? )))
Это те, кто занимается кватернионами?
А чего их не признавать?
Всё это дела прошлые... Сейчас, по-моему, тут копья уже никто не ломает.
-
-
10.07.2008 в 22:28www.diary.ru/~Organon/?query=%EA%E2%E0%F2%E5%F0...
-
-
10.07.2008 в 22:31это школа Гамильтона, да=)
книга Кляйна же в 1909 году выходила, вот и полемика тех лет видать...
за ссылко спасибо, почитаю=))))
-
-
30.08.2009 в 14:13-
-
31.08.2009 в 16:51Комментарии меня там сразили)
А вообще, я этот жж мало читала, но всё, что читала, очень нравилось!