|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 29 Jan 2003 06:24:53
To : Ivan Boldyrev
Subject : Re: Урощение формул
--------------------------------------------------------------------------------
Ivan Boldyrev <boldyrev@dataeast.ru> wrote:
>>> Скажи, а в задаче коммивояжёра -- "найти кратчайший цикл, проходящий
>>> через все вершины полносвязного взвешенного графа" -- тоже бесконечное
>>> дерево решений? С учётом того, что количество вообще всех циклов в
>>> любом конкретном конечном графе конечно?
>
> VL> Число путей от вершины к вершине - конечно. А вот число форм,
> VL> тождественных заданной - бесконечно. 1 = 2-1 = 3-2 = 10^2/100 =
> VL> ..., и всё такое.
>
> Вопрос был у Vladislavа Terehovа -- что такое NP-полнота. Ты
> определил понятие NP-полноты через бесконечное дерево. Я опроверг.
Торможу, стало быть. Мне показалось, что вопрос был - почему ЭТА задача
NP-полная.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
