Re: Урощение формул

From

Evgenij Masherov (2:5020/175.2)

To

Yuri Burger ()

Date

2003-01-28T11:02:07Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Jan 28 2003 09:53, Yuri Burger wrote to Vitaly Lugovsky:
 
VL>>>>  Задача эта - эмпирическая. И NP-полная.
 ??>>> Расскажи несчатному пеpвокуpснику, что значат эти опpеделения... Или
 ??>>> хотя бы где почитать можно.
 VL>>  NP-полная - решение расположено где-то на БЕСКОНЕЧНОМ дереве, и
 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)