Точная связь между классами сложности и сложностями алгоритма [дублирует

Question

Этот вопрос уже имеет ответ здесь:

• Каково определение P, NP, NP-Complete и NP-Hard? 7 ответов

Все ли алгоритмы, которые имеют многочленную сложность времени, принадлежат классу P? И у класса P нет алгоритма, который не имеет многочленной сложности?

Все ли алгоритмы, которые имеют не полиномиальную сложность, принадлежат NP или NP-Hard или обоим?

Я просто пытаюсь понять основные отношения.

Answer 1

$ P $ определяется как класс (решения) задач, которые имеют алгоритм, который решает их во время полинома (в ТМ или полиномиально-эквивалентной модели). Таким образом, $ p $ содержит именно эти проблемы, не больше и не меньше.

Что касается $ np $- ситуация более деликатная. Проблема заключается в $ np $, если у нее есть недерминированный алгоритм, который работает в многочленное время. Эквивалентное, более удобное определение-это то, что, учитывая решение проблемы, вы можете проверить его правильность во времени полиномиальной в размере проблемы. Например, учитывая график и путь, который претендует на звание гамильтониана, вы можете проверить в полиномиальное время, что это действительно гамильтонианский путь. Таким образом, проблема принятия решения о том, имеет ли график гамильтонианский путь в $ np $.

Разъяснение: $ np $ - это класс проблемы, не из алгоритмы. Анкет Алгоритм не принадлежит $ np $.

Теперь, как известно, некоторые проблемы не имеют алгоритма полиномиального времени. Это не значит, что они находятся в $ np $. На самом деле, известно, что некоторые проблемы не будут в $ np $. Например, любая проблема $ nexp $-Hard.

Что касается проблем $ np $ -hard-поскольку мы не знаем, является ли $ p = np $ или нет, мы не знаем, является ли каждая проблема за пределами $ p $ $ $ $-Hard. Если $ np = p $, то каждая проблема-$ np $ -hard (кроме $ sigma^*$ и $ yellyset $).

Этот ответ (который безусловно неполный) охватывает около 3 недель материала в основном курсе сложности. Возможно, рассмотрите тщательное чтение учебника, такого как «Теория вычислений» Сипсера.

Answer 2

Все алгоритмы, которые решают некоторую проблему решения в полиномиальное время, показывают, что их проблемы находятся в $ P $. Но, безусловно, есть алгоритмы, которые не требуют многочленного времени для проблем в $ p $. Вы можете сортировать, генерируя все перестановки ввода $ n! $, И проверить каждый, если он отсортирован. Этот алгоритм занимает более чем экспоненциальное время, но проблема имеет решение в полиномиальном времени.