1205
правок
NP-Полная задача: различия между версиями
Материал из WikiGrapp
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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> достаточно показать, что какая-то из | ||
| Строка 26: | Строка 26: | ||
(''[[Множество вершин, разрезающих контуры]]''). Имеет ли данный | (''[[Множество вершин, разрезающих контуры]]''). Имеет ли данный | ||
[[ориентированный граф]] <math>\,k</math>-элементное множество вершин, ''разрезающих'' все его контуры, т.е. содержащих хотя бы по одной вершине каждого из них? | [[ориентированный граф]] <math>\,k</math>-элементное множество вершин, ''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной вершине каждого из них? | ||
(''[[Множество дуг, разрезающих контуры]]''). Имеет ли данный | (''[[Множество дуг, разрезающих контуры]]''). Имеет ли данный | ||
ориентированный граф <math>\,k</math>-элементное множество дуг, | ориентированный граф <math>\,k</math>-элементное множество дуг, | ||
''разрезающих'' все его контуры, т.е. содержащих хотя бы по одной | ''разрезающих'' все его контуры, т. е. содержащих хотя бы по одной | ||
дуге каждого из них? | дуге каждого из них? | ||
| Строка 49: | Строка 49: | ||
[[степень вершины|степень]] не более <math>\,k</math>? | [[степень вершины|степень]] не более <math>\,k</math>? | ||
('' | (''Минимальный эквивалентный по достижимости ориентированный'' ''граф). Можно ли удалить из данного ориентированного графа'' | ||
часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | ||
не изменилось, но результирующий граф содержал бы не более | не изменилось, но результирующий граф содержал бы не более | ||
| Строка 103: | Строка 102: | ||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
* Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: ИПЦ НГУ, 2018. | |||
