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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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.

Текущая версия от 12:49, 23 марта 2011

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

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

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

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

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

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.