[Форум Rossia.org] [Ответы и комментарии] [Написать ответ]
Отправлено
Felix 18:05:41 14/03/1999
в ответ на:
Re: Ужасно..., отправлено
Тошик 16:21:15 13/03/1999
>> NP-сложная задача — задача не имеющая никаких способов решения более быстрых, чем последовательный перебор вариантов. По определению. >> Вы можете подразумевать что угодно, но у термина есть конкретное значение и Вы этот термин употребляете неправильно. > По определению, NP-задача (комбинаторная, т.е. представимая на графе) это задача, решение которой может быть найдено Недетерминированным автоматом за Полиномиальное число шагов (от характерного параметра сложности задачи, например, число вершин графа в задаче Гамильтона). > NP-полная задача — это задача, для которой не существует алгоритма ее решения полиномиальной сложности. Я наверное взялся бы доказать, что для представимой на графе задачи данное мною определение вполне корректно. Вечером скорее всего, напишу подробнее.
Ответы и комментарии: