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