courses:algorithms_building_and_analysis:materials:np_full_tasks_notes
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2020/07/05 15:00] aoblizanov added np=p |
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2020/07/20 20:23] aoblizanov [[В работе] NP класс и NP-полные задачи] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== [В работе] NP класс и NP-полные задачи ====== | + | ====== NP класс и NP-полные задачи ====== |
| - | ===== Вопросы и ответы про NP, P и т.д. ===== | + | ===== Вопросы и ответы про $NP, P$ и т.д. ===== |
| ==== Что такое класс $P$? ==== | ==== Что такое класс $P$? ==== | ||
| - | $P$ -- класс задач, решаемых за **полиномиальное** (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. | + | $P$ -- класс задач, //решаемых// за **полиномиальное** (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. |
| ==== Что такое полиномиальное время? ==== | ==== Что такое полиномиальное время? ==== | ||
| - | Говорят, что алгоритм работает за полиномиальное время, если время работы ограничено сверху многочленом от размера входа алгоритма, то есть $T(n)=O(n^k)$ для некоторой константы $k$. | + | Говорят, что алгоритм работает за полиномиальное время, если время работы //ограничено сверху// многочленом от размера входа алгоритма, то есть $T(n)=O(n^k)$ для некоторой константы $k$. |
| - | (Примерами задач являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из n чисел, нахождение эйлерова цикла на графе из m рёбер, обнаружение в тексте длиной n некоторого слова, построение покрывающего дерева минимальной стоимости) | + | (Примерами задач являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из $n$ чисел, нахождение эйлерова цикла на графе из $m$ рёбер, обнаружение в тексте длиной $n$ некоторого слова, построение покрывающего дерева минимальной стоимости) |
| ==== Что такое класс $NP$? ==== | ==== Что такое класс $NP$? ==== | ||
| - | $NP$ -- класс задач, верифицируемых (проверяемых) за **полиномиальное** время. Альтернативное определение: класс задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга. Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д. | + | $NP$ -- класс задач, //верифицируемых// (проверяемых) за **полиномиальное** время. Альтернативное определение: класс задач, решаемых за полиномиальное время на //недетерминированной машине Тьюринга//. Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д. |
| ==== Как доказать, что задача принадлежит классу $NP$? ==== | ==== Как доказать, что задача принадлежит классу $NP$? ==== | ||
| Существует два варианта: | Существует два варианта: | ||
| Line 19: | Line 19: | ||
| **Сертификат** -- дополнительная информация, позволяющая быстро решить задачу. Важно помнить, что размер сертификата должен быть полиномиален относительно размера самой задачи. | **Сертификат** -- дополнительная информация, позволяющая быстро решить задачу. Важно помнить, что размер сертификата должен быть полиномиален относительно размера самой задачи. | ||
| - | **Алгоритм верификации** -- принимает на вход экземпляр задачи и сертификат к нему, а возвращает ответ к задаче, 0 или 1. | + | **Алгоритм верификации** -- принимает на вход //экземпляр// задачи и сертификат к нему, а возвращает ответ к задаче, 0 или 1. |
| - | + | ||
| - | **Пример:** задача о клике. Сертификат -- множество вершин, образующих клику. Алгоритм верификации: проверить, что все вершины, приведенные в сертификате, связаны между собой (сложность - $O(n^2)$ | + | |
| <note>Грубо говоря, к классу $NP$ относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи, которые можно быстро решить. Далее рассмотрим подробнее задачи, связанные с классом $NP$.</note> | <note>Грубо говоря, к классу $NP$ относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи, которые можно быстро решить. Далее рассмотрим подробнее задачи, связанные с классом $NP$.</note> | ||
| + | |||
| + | <note tip>В тексте есть слова, выделенные //курсивом//. Убедитесь, что хорошо понимаете их значение, порой оно связано со смежными науками.</note> | ||
| + | |||
| ---- | ---- | ||
| ==== Какие задачи называются $NP$-трудными? ==== | ==== Какие задачи называются $NP$-трудными? ==== | ||
| - | Это задачи, к которым сводимы все задачи из класса $NP$ за полиномиальное время. При этом не требуется, чтобы сама задача принадлежала классу $NP$, она может быть более сложной. | + | Это задачи, к которым //сводимы// все задачи из класса $NP$ за полиномиальное время. При этом не требуется, чтобы сама задача принадлежала классу $NP$, она может быть более сложной. |
| ==== Что значит, что одна задача водима к другой за полиноминальное время? ==== | ==== Что значит, что одна задача водима к другой за полиноминальное время? ==== | ||
| - | Это значит, что существует полиномиальная функция, которая отображает экземпляр первой задачи в экземпляр второй задачи. Если входная задача соответствует положительному решению, то и выходная задача соответствует положительному решению. Если входная задача соответствует отрицательному решению, то и решение выходной задачи отрицательно. | + | Это значит, что существует полиномиальная функция, которая //отображает// экземпляр первой задачи в экземпляр второй задачи. Если входная задача соответствует положительному решению, то и выходная задача соответствует положительному решению. Если входная задача соответствует отрицательному решению, то и решение выходной задачи отрицательно. |
| ==== Какие подходы к решению $NP$-трудных задач? ==== | ==== Какие подходы к решению $NP$-трудных задач? ==== | ||
| * Полный перебор (Brute force) | * Полный перебор (Brute force) | ||
| Line 48: | Line 49: | ||
| ==== Гипотеза $NP=P$ ==== | ==== Гипотеза $NP=P$ ==== | ||
| - | Существует гипотеза $P=NP$ (одна из центральных проблем теории алгоритмов). Гипотеза гласит, что если решение задачи можно быстро проверить, то саму задачу можно быстро решить. Гипотезу не могут ни опровергнуть, ни доказать уже более 30 лет. | + | Существует гипотеза $P=NP$ (одна из центральных проблем теории алгоритмов). Гипотеза гласит, что **если решение задачи можно быстро проверить, то саму задачу можно быстро решить**. Гипотезу не могут ни опровергнуть, ни доказать уже более 30 лет. |
| + | |||
| + | <note>Данная проблема является одной из задач тысячелетия. За ее решение Математический институт Клэя назначил премию в миллион долларов США.</note> | ||
| ==== Общая схема классов ==== | ==== Общая схема классов ==== | ||
| Line 54: | Line 57: | ||
| {{:courses:algorithms_building_and_analysis:materials:np-class.png?720|}} | {{:courses:algorithms_building_and_analysis:materials:np-class.png?720|}} | ||
| - | Обратим внимание на знаки **==?** на рисунке. Если хотя бы одна **$NP$-полная** (иначе говоря NPC) задача будет принадлежать классу $P$, то все остальные задачи из класса $NP$ также будут принадлежать классу $P$. Говоря на "языке рисунка": //из синей стрелки следуют синие пунктирные стрелки//. | + | Обратим внимание на знаки **==?** на рисунке. Если хотя бы одна **$NP$-полная** (иначе говоря NPC) задача будет принадлежать классу $P$, то все остальные задачи из класса $NP$ также будут принадлежать классу $P$. Говоря на "языке рисунка": //из синей стрелки следуют синие пунктирные стрелки//. Именно так должно доказываться равенство $NP=P$. |
| - | Но тем не менее, ни одной $NP$-полной задачи, которая принажлежала бы классу $P$, не было найдено. | + | Но тем не менее, ни одной $NP$-полной задачи, которая принадлежала бы классу $P$, не было найдено. |
| --- //[[kirvant31580@gmail.com|Облизанов Александр]]// | --- //[[kirvant31580@gmail.com|Облизанов Александр]]// | ||
courses/algorithms_building_and_analysis/materials/np_full_tasks_notes.txt · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
