|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 28 Jan 2003 10:53:10
To : Vitaly Lugovsky
Subject : Re: Урощение формул
--------------------------------------------------------------------------------
Hello, Vitaly!
You wrote to Vladislav Terehov on Tue, 28 Jan 2003 02:42:50 +0300:
VL>>> Задача эта - эмпирическая. И NP-полная.
??>> Расскажи несчатному пеpвокуpснику, что значат эти опpеделения... Или
??>> хотя бы где почитать можно.
VL> NP-полная - решение расположено где-то на БЕСКОHЕЧHОМ дереве, и
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
