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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Классы <math>\cal P</math> и <math>\cal NP</math>''' (''<math>cal P</math> and <math>\cal NP</math> classes'') - Через <ma...)
 
Нет описания правки
Строка 1: Строка 1:
'''Классы <math>\cal P</math> и <math>\cal NP</math>''' (''<math>cal P</math> and <math>\cal 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>{\cal P}</math> обозначается множество всех языков, допускаемых ''детерминированной машиной Тьюринга'' (''ДМТ'') с полиномиальной временной
сложностью, а через <math>{\mathcal NP}</math> --- множество всех языков, допускаемых ''недетерминированной машиной Тьюринга'' (<math>MT</math>) с полиномиальной [[временная сложность|временной сложностью]].
сложностью, а через <math>{\cal NP}</math>~--- множество всех языков, допускаемых ''недетерминированной машиной Тьюринга'' (<math>MT</math>)
с полиномиальной временной сложностью.


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


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


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


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


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


[Касьянов/95]
[Касьянов/95]

Версия от 11:49, 29 октября 2009

Классы [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]-полных задач, либо доказав невозможность построения эффективного алгоритма для этой задачи. До настоящего времени эта важная проблема дискретной математики остается открытой.

См. также

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

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]