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

From

Yuri Burger ()

To

Vitaly Lugovsky ()

Date

2003-01-28T09:53:10Z

Area

RU.ALGORITHMS

From: "Yuri Burger" <kruger@selena.net.ua>

Hello, Vitaly!
You wrote to Vladislav Terehov on Tue, 28 Jan 2003 02:42:50 +0300:

 VL>>>  Задача эта - эмпирическая. И NP-полная.
 ??>> Расскажи несчатному пеpвокуpснику, что значат эти опpеделения... Или
 ??>> хотя бы где почитать можно.
 VL>  NP-полная - решение расположено где-то на БЕСКОНЕЧНОМ дереве, и
 VL> требуется полный обход его. Однако, имея некоторые эмпирические

    Почему в бесконечном? NP - значит "не полиномиальная", время решения задачи
растет неполиномиально по отношению к размеру задачи. Сама задача вполне может
быть конечной (что в большенстве случаев и имеет место быть), но время перебора
всех возможных решений слишком велико, а, как ты и сказал, для доказательства
оптимальности решения, требуется этот самый полный перебор.

With best regards, Yuri Burger aka J.O. Kruger.  E-mail: jo_kruger@mail.ru


--- ifmail v.2.15dev5
 * Origin: Unknown (2:5020/400)