11/ Какие задачи попадают в класс p? Какие задачи попадают в класс np? Как эти классы связаны между собой? (p-np – проблема).

Классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).

В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов.

Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса. Наиболее известными являются NP-полные задачи.

Полные задачи — хороший инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано.

В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.

Задачи, принадлежащие классу P

Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из n чисел, нахождение эйлерова цикл на графе из m рёбер, обнаружение в тексте длиной n некоторого слова, построение покрывающего дерево минимальной стоимости, линейное программирование и некоторые другие.

[править]

Задачи, принадлежность которых классу P неизвестна

Существует много задач, для которых не найдено полиномиального алгоритма, но не доказано, что его не существует. Соответственно, неизвестно, принадлежат ли такие задачи классу P. Вот некоторые из них:

Задача коммивояжёра (а также все остальные NP-полные задачи). Полиномиальное решение этой задачи равносильно установлению равенства классов P и NP.

Разложение числа на простые множители.

Дискретное логарифмирование в конечном поле.

Задача о скрытой подгруппе с n образующими.

Дискретное логарифмирование в аддитивной группе точек на эллиптической кривой.

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга.

Эквивалентно класс NP можно определить как содержащий задачи, которые можно «быстро» решить на недетерминированной машине Тьюринга.

Примеры задач класса NP

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:

Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор.

Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) заданного размера. Сертификат — номера вершин, образующих клику.

Определение наличия в графе гамильтонова цикла. Сертификат — последовательность вершин, образующих гамильтонов цикл.

Задача о коммивояжёре — расширенный и более приближенный к реальности вариант предыдущей задачи.

Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.

Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если удастся решить любую из них за полиномиальное время, то все задачи класса NP также можно будет решить за полиномиальное время.

Равенство классов P и NP

[править]

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск Задачи тысячелетия

Равенство классов P и NP

Гипотеза Ходжа

Гипотеза Пуанкаре

Гипотеза Римана

Квантовая теория

Янга — Миллса

Существование и гладкость

решений уравнений

Навье — Стокса

Гипотеза

Бёрча — Свиннертон-Дайера

В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

Формулировка

Диаграмма классов сложности при условии P ≠ NP.

Нестрого говоря, проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

Отношения между классами P и NP рассматриваются в теории вычислительной сложности (разделе теории вычислений), изучающей ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи).

Из чего состоит машина Тьюринга? Как она работает?

В каком случае мы говорим, что машина Тьюринга вычисляет числовую функцию f?

Какая задача называется алгоритмически неразрешимой?

Дать определение формальной грамматики. Приведите пример грамматики.

В чем заключается проблема остановки машины Тьюринга. Является ли она алгоритмически разрешимой?