|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 28 Jan 2003 12:02:07
To : Yuri Burger
Subject : Re: Урощение формул
--------------------------------------------------------------------------------
Tue Jan 28 2003 09:53, Yuri Burger wrote to Vitaly Lugovsky:
VL>>>> Задача эта - эмпирическая. И NP-полная.
??>>> Расскажи несчатному пеpвокуpснику, что значат эти опpеделения... Или
??>>> хотя бы где почитать можно.
VL>> NP-полная - решение расположено где-то на БЕСКОHЕЧHОМ дереве, и
VL>> требуется полный обход его. Однако, имея некоторые эмпирические
YB> Почему в бесконечном? NP - значит "не полиномиальная", время решения
YB> задачи растет неполиномиально по отношению к размеру задачи. Сама задача
YB> вполне может быть конечной (что в большенстве случаев и имеет место
YB> быть), но время перебора всех возможных решений слишком велико, а, как ты
YB> и сказал, для доказательства оптимальности решения, требуется этот самый
YB> полный перебор.
Давайте уж будем точны. NP - nondeterminity polinomial, т.е. для нее известно
полиномиальное решение, требующее не более чем полиномиального числа вызовов
некоего оракула, подсказывающего нам, на какую ветвь перейти. В частности,
если нам уже известно решение, оно и дает такой оракул, т.е. проверить
правильность можно за полиномиальное время. Можно также надеяться, что для
данной задачи вместо несуществующего оракула будет предложена вполне
алгоритмичная процедура, но пока такого не сделано. Покамест лишь показано,
что если для одной задачи из некоего класса такое возможно, то и для любой
задачи из этого класса тоже возможно (это, собственно, и есть класс NP-полных
задач).
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
