courses:algorithms_building_and_analysis:materials:np_full_tasks_notes

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2020/07/03 20:53]
aoblizanov [Что такое полиномиальное время?]
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.  
- 
-**Пример:​** задача о клике. Сертификат -- множество вершин,​ образующих клику. Алгоритм верификации:​ проверить,​ что все вершины,​ приведенные в сертификате,​ связаны между собой (сложность - $O(n^2)$ ​ 
- 
-<​note>​Грубо говоря,​ к классу $NP$ относятся те задачи,​ правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи,​ которые можно быстро решить. Далее рассмотрим подробнее задачи,​ связанные с классом $NP$.</​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 лет. 
- 
- --- //​[[kirvant31580@gmail.com|Облизанов Александр]] 2020/07/03 20:51// 
courses/algorithms_building_and_analysis/materials/np_full_tasks_notes.txt · Last modified: 2022/12/10 09:08 (external edit)