1288
правок
NP-Полная задача: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 3: | Строка 3: | ||
рассматривается, то используется термин ''<math>\mathcal NP</math>-трудная'' задача. | рассматривается, то используется термин ''<math>\mathcal NP</math>-трудная'' задача. | ||
Найдется немного научных терминов, так быстро завоевавших широкую известность, как понятие "<math>{\mathcal NP}</math>-полная задача". За короткий промежуток времени с момента введения этого понятия С.Куком в начале 70-х годов оно стало символом тех трудностей, которые встречаются на пути создания достаточно общих и эффективных методов решения задач дискретной математики. | Найдется немного научных терминов, так быстро завоевавших широкую известность, как понятие "<math>{\mathcal NP}</math>-полная задача". За короткий промежуток времени с момента введения этого понятия С. Куком в начале 70-х годов оно стало символом тех трудностей, которые встречаются на пути создания достаточно общих и эффективных методов решения задач дискретной математики. | ||
<math>{\mathcal NP}</math>-полные задачи являются "самыми трудными" в классе <math>{\mathcal NP}.</math> | <math>{\mathcal NP}</math>-полные задачи являются "самыми трудными" в классе <math>{\mathcal NP}.</math> | ||
Если какая-нибудь <math>{\mathcal NP}</math>-полная задача может быть решена за полиномиальное время, то и любая задача из <math>{\mathcal NP}</math> полиномиально разрешима, а если какая-то задача из <math>{\mathcal NP}</math> труднорешаема, то и любая <math>{\mathcal NP}</math>-полная задача является труднорешаемой. При этом, для того чтобы доказать <math>{\mathcal NP}</math>-полноту некоторой задачи из <math>{\mathcal NP},</math> достаточно показать, что какая-то из | Если какая-нибудь <math>{\mathcal NP}</math>-полная задача может быть решена за полиномиальное время, то и любая задача из <math>{\mathcal NP}</math> полиномиально разрешима, а если какая-то задача из <math>{\mathcal NP}</math> труднорешаема, то и любая <math>{\mathcal NP}</math>-полная задача является труднорешаемой. При этом, для того чтобы доказать <math>{\mathcal NP}</math>-полноту некоторой задачи из <math>{\mathcal NP},</math> достаточно показать, что какая-то из | ||
| Строка 10: | Строка 10: | ||
Вопрос о взаимоотношении классов <math>{\mathcal P}</math> и <math>{\mathcal NP}</math> имеет | Вопрос о взаимоотношении классов <math>{\mathcal P}</math> и <math>{\mathcal NP}</math> имеет | ||
фундаментальное значение, но все еще открыт. Известно, что | фундаментальное значение, но все еще открыт. Известно, что | ||
<math>{\mathcal P}\subseteq {\mathcal NP}</math> и если <math>L\in {\mathcal NP},</math> то существует такой полином <math>\,p(n)</math> и ''ДМТ'' <math>\,M,</math> что <math>\,L</math> допускается на <math>\,M</math> с [[временная сложность|временной сложностью]] <math>\,O(2^{p(n)}).</math> Однако до сих пор не доказано, содержит класс <math>{\mathcal NP}</math> труднорешаемые задачи или нет, т.е. <math>{\mathcal NP\setminus P}\neq \emptyset</math> или <math>{\mathcal NP=P}.</math> Вместе с тем известно, что в предположении <math>{\mathcal P}\neq {\mathcal NP}</math> класс <math>{\mathcal NP}</math> не просто содержит два непересекающихся подкласса: класс <math>{\mathcal P}</math> и класс <math>{\mathcal NP}</math>-полных задач, а также должен включать задачи, не принадлежащие ни одному из этих подклассов (т.е. при <math>{\mathcal P}\neq | <math>{\mathcal P}\subseteq {\mathcal NP}</math> и если <math>L\in {\mathcal NP},</math> то существует такой полином <math>\,p(n)</math> и ''ДМТ'' <math>\,M,</math> что <math>\,L</math> допускается на <math>\,M</math> с [[временная сложность|временной сложностью]] <math>\,O(2^{p(n)}).</math> Однако до сих пор не доказано, содержит класс <math>{\mathcal NP}</math> труднорешаемые задачи или нет, т. е. <math>{\mathcal NP\setminus P}\neq \emptyset</math> или <math>{\mathcal NP=P}.</math> Вместе с тем известно, что в предположении <math>{\mathcal P}\neq {\mathcal NP}</math> класс <math>{\mathcal NP}</math> не просто содержит два непересекающихся подкласса: класс <math>{\mathcal P}</math> и класс <math>{\mathcal NP}</math>-полных задач, а также должен включать задачи, не принадлежащие ни одному из этих подклассов (т.е. при <math>{\mathcal P}\neq | ||
{\mathcal NP}</math> должны существовать задачи из <math>{\mathcal NP},</math> которые | {\mathcal NP}</math> должны существовать задачи из <math>{\mathcal NP},</math> которые | ||
неразрешимы за полиномиальное время и не являются <math>{\mathcal NP}</math>-полными). | неразрешимы за полиномиальное время и не являются <math>{\mathcal NP}</math>-полными). | ||
| Строка 26: | Строка 26: | ||
(''[[Множество вершин, разрезающих контуры]]''). Имеет ли данный | (''[[Множество вершин, разрезающих контуры]]''). Имеет ли данный | ||
[[ориентированный граф]] <math>\,k</math>-элементное множество вершин, ''разрезающих'' все его контуры, т.е. содержащих хотя бы по одной вершине каждого из них? | [[ориентированный граф]] <math>\,k</math>-элементное множество вершин, ''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной вершине каждого из них? | ||
(''[[Множество дуг, разрезающих контуры]]''). Имеет ли данный | (''[[Множество дуг, разрезающих контуры]]''). Имеет ли данный | ||
ориентированный граф <math>\,k</math>-элементное множество дуг, | ориентированный граф <math>\,k</math>-элементное множество дуг, | ||
''разрезающих'' все его контуры, т.е. содержащих хотя бы по одной | ''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной | ||
дуге каждого из них? | дуге каждого из них? | ||
| Строка 49: | Строка 49: | ||
[[степень вершины|степень]] не более <math>\,k</math>? | [[степень вершины|степень]] не более <math>\,k</math>? | ||
('' | (''Минимальный эквивалентный по достижимости ориентированный'' ''граф).'' Можно ли удалить из данного ориентированного графа часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | ||
часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | |||
не изменилось, но результирующий граф содержал бы не более | не изменилось, но результирующий граф содержал бы не более | ||
<math>\,k</math> дуг. | <math>\,k</math> дуг. | ||
| Строка 103: | Строка 101: | ||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИПЦ НГУ, 2018. | |||
