Классы P и NP: различия между версиями

'''Классы <math>\mathcal P</math> и <math>\mathcal NP</math>''' ([[P and NP classes|''<math>\mathcal P</math> and <math>\mathcal NP</math> classes]]'') - Через <math>{\mathcal P}</math> обозначается множество всех [[язык|языков]], допускаемых ''[[детерминированная машина Тьюринга|детерминированной машиной Тьюринга]]'' (''ДМТ'') с полиномиальной временной

сложностью, а через <math>{\mathcal NP}</math> --- множество всех языков, допускаемых ''недетерминированной машиной Тьюринга'' (<math>MT</math>) с полиномиальной [[временная сложность|временной сложностью]].

Имеется определенное соответствие между [[задача распознавания свойств|задачами распознавания]] и языками, которое осуществляется с помощью кодирования, обычно применяемого для представления задачи при ее решении на ЭВМ. Указанное соответствие позволяет отождествлять решение задачи распознавания свойств с распознаванием соответствующего языка: говорят, что задача принадлежит <math>{\mathcal P}</math> (или <math>{\mathcal NP}</math>), если соответствующий язык принадлежит <math>{\mathcal P}</math> (или <math>{\mathcal NP}</math>).

Класс <math>\mathcal P</math> --- это так называемые ''легко решаемые задачи''. Однако большинство из задач дискретной математики принадлежит <math>\mathcal NP</math>. Это так называемые переборные задачи. Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть разрешена алгоритмом полного перебора. Так, в задаче о выполнимости логических формул решение можно отыскать среди <math>2^n</math> булевых векторов длины <math>n</math>, где <math>n</math> --- число переменных формулы, и, перебрав это экспоненциальное множество векторов при вычислении значения формулы, мы обязательно решим задачу. Переборный алгоритм имеет экспоненциальную временную сложность и может хорошо работать на практике для небольших размеров задачи. Но с ростом размера задачи число вариантов быстро растет, и задача

экспоненциального числа вариантов, а аналогом разрешимости --- существование алгоритма решения задачи за полиномиальное время на детерминированном вычислительном устройстве.

При этом [[NP-Полная задача|<math>{\mathcal NP}</math>-полные задачи]] являются эталоном сложности класса переборных задач, они являются "самыми трудными" в классе <math>{\mathcal NP}</math>. На центральный вопрос,

можно ли исключить перебор при решении дискретных задач, можно ответить, либо построив полиномиальный алгоритм решения одной из <math>{\mathcal NP}</math>-полных задач, либо доказав невозможность построения эффективного алгоритма для этой задачи. До настоящего времени эта важная проблема дискретной математики остается открытой.

==См. также==

''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Задача легко разрешимая]], [[Метод локальной замены]], [[Метод построения компонент]], [[Задача распознавания свойств]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].''