This shows you the differences between two versions of the page.
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2020/07/05 18:17] aoblizanov [Вопросы и ответы про NP, P и т.д.] |
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2022/12/10 09:08] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== [В работе] NP класс и NP-полные задачи ====== | ||
- | ===== Вопросы и ответы про $NP, P$ и т.д. ===== | ||
- | ==== Что такое класс $P$? ==== | ||
- | |||
- | $P$ -- класс задач, //решаемых// за **полиномиальное** (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. | ||
- | |||
- | ==== Что такое полиномиальное время? ==== | ||
- | Говорят, что алгоритм работает за полиномиальное время, если время работы //ограничено сверху// многочленом от размера входа алгоритма, то есть $T(n)=O(n^k)$ для некоторой константы $k$. | ||
- | |||
- | (Примерами задач являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из $n$ чисел, нахождение эйлерова цикла на графе из $m$ рёбер, обнаружение в тексте длиной $n$ некоторого слова, построение покрывающего дерева минимальной стоимости) | ||
- | ==== Что такое класс $NP$? ==== | ||
- | $NP$ -- класс задач, //верифицируемых// (проверяемых) за **полиномиальное** время. Альтернативное определение: класс задач, решаемых за полиномиальное время на //недетерминированной машине Тьюринга//. Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д. | ||
- | ==== Как доказать, что задача принадлежит классу $NP$? ==== | ||
- | Существует два варианта: | ||
- | - Привести алгоритм решения задачи, работающий полиномиальное время на недетерминированной машине Тьюринга. | ||
- | - Описать сертификат и привести алгоритм верификации, работающий полиномиальное время на детерминированной машине Тьюринга. | ||
- | |||
- | **Сертификат** -- дополнительная информация, позволяющая быстро решить задачу. Важно помнить, что размер сертификата должен быть полиномиален относительно размера самой задачи. | ||
- | |||
- | **Алгоритм верификации** -- принимает на вход //экземпляр// задачи и сертификат к нему, а возвращает ответ к задаче, 0 или 1. | ||
- | |||
- | <note>Грубо говоря, к классу $NP$ относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи, которые можно быстро решить. Далее рассмотрим подробнее задачи, связанные с классом $NP$.</note> | ||
- | |||
- | <note tip>В тексте есть слова, выделенные //курсивом//. Убедитесь, что хорошо понимаете их значение, порой оно связано со смежными науками.</note> | ||
- | |||
- | ---- | ||
- | ==== Какие задачи называются $NP$-трудными? ==== | ||
- | Это задачи, к которым //сводимы// все задачи из класса $NP$ за полиномиальное время. При этом не требуется, чтобы сама задача принадлежала классу $NP$, она может быть более сложной. | ||
- | ==== Что значит, что одна задача водима к другой за полиноминальное время? ==== | ||
- | Это значит, что существует полиномиальная функция, которая //отображает// экземпляр первой задачи в экземпляр второй задачи. Если входная задача соответствует положительному решению, то и выходная задача соответствует положительному решению. Если входная задача соответствует отрицательному решению, то и решение выходной задачи отрицательно. | ||
- | ==== Какие подходы к решению $NP$-трудных задач? ==== | ||
- | * Полный перебор (Brute force) | ||
- | * Приближенное решение (с оценкой точности и с вероятностью ошибки) | ||
- | * Стремление к полиномиальному решению в среднем (в худшем случае задача остается нерешаемой за полиномиальное время) | ||
- | ==== Какие задачи называются $NP$-полными? ==== | ||
- | $NP$-трудные задачи, принадлежащие классу $NP$. | ||
- | |||
- | **Примеры:** 3Sat, задача о вершинном покрытии (множество вершин, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из него) и т.д. | ||
- | ==== Как доказать, что задача является $NP$-трудной? ==== | ||
- | Существует два варианта: | ||
- | - (Практически никогда не используется) Доказать, что все задачи из класса $NP$ сводится к данной. Таким способом была определена первая $NP$-трудная (и -полная) задача -- Sat. | ||
- | - (Основной) Доказать, что к данной задаче сводится (за полиномиальное время) какая-нибудь $NP$-трудная задача. Отсюда следует, что все задачи можно свести к данной, так как любую задачу из $NP$ можно свести к $NP$-трудной задаче, а ее в свою очередь к данной. | ||
- | ==== Как доказать, что задача является $NP$-полной? ==== | ||
- | * Доказать, что она $NP$-трудная. | ||
- | * Доказать, что она принадлежит $NP$. | ||
- | |||
- | ===== Общая схема и проблема $NP=P$ ===== | ||
- | |||
- | ==== Гипотеза $NP=P$ ==== | ||
- | Существует гипотеза $P=NP$ (одна из центральных проблем теории алгоритмов). Гипотеза гласит, что **если решение задачи можно быстро проверить, то саму задачу можно быстро решить**. Гипотезу не могут ни опровергнуть, ни доказать уже более 30 лет. | ||
- | |||
- | <note>Данная проблема является одной из задач тысячелетия. За ее решение Математический институт Клэя назначил премию в миллион долларов США.</note> | ||
- | |||
- | ==== Общая схема классов ==== | ||
- | |||
- | {{:courses:algorithms_building_and_analysis:materials:np-class.png?720|}} | ||
- | |||
- | Обратим внимание на знаки **==?** на рисунке. Если хотя бы одна **$NP$-полная** (иначе говоря NPC) задача будет принадлежать классу $P$, то все остальные задачи из класса $NP$ также будут принадлежать классу $P$. Говоря на "языке рисунка": //из синей стрелки следуют синие пунктирные стрелки//. Именно так должно доказываться равенство $NP=P$. | ||
- | |||
- | Но тем не менее, ни одной $NP$-полной задачи, которая принадлежала бы классу $P$, не было найдено. | ||
- | |||
- | |||
- | --- //[[kirvant31580@gmail.com|Облизанов Александр]]// |