Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Классы <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 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 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>{\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> --- число переменных формулы, и, перебрав это экспоненциальное множество векторов при вычислении значения формулы, мы обязательно решим задачу. Переборный алгоритм имеет экспоненциальную временную сложность и может хорошо работать на практике для небольших размеров задачи. Но с ростом размера задачи число вариантов быстро растет, и задача
Класс <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>. На центральный вопрос,
При этом [[NP-Полная задача|<math>{\mathcal NP}</math>-полные задачи]] являются эталоном сложности класса переборных задач, они являются "самыми трудными" в классе <math>{\mathcal NP}</math>. На центральный вопрос,
Строка 14: Строка 14:


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


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.