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 18:04] aoblizanov |
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2022/12/10 09:08] (current) |
||
---|---|---|---|
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) |