1303
правки
NP-Полная задача: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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>-полными). | ||
| Строка 49: | Строка 49: | ||
[[степень вершины|степень]] не более <math>\,k</math>? | [[степень вершины|степень]] не более <math>\,k</math>? | ||
(''Минимальный эквивалентный по достижимости ориентированный'' ''граф). Можно ли удалить из данного ориентированного графа | (''Минимальный эквивалентный по достижимости ориентированный'' ''граф).'' Можно ли удалить из данного ориентированного графа часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | ||
часть [[дуга|дуг]] так, чтобы отношение [[достижимая вершина|достижимости]] между вершинами | |||
не изменилось, но результирующий граф содержал бы не более | не изменилось, но результирующий граф содержал бы не более | ||
<math>\,k</math> дуг. | <math>\,k</math> дуг. | ||