NP-сложность


[Форум Rossia.org] [Ответы и комментарии] [Написать ответ]


Отправлено Felix 18:05:41 14/03/1999
в ответ на: Re: Ужасно..., отправлено Тошик 16:21:15 13/03/1999

>> NP-сложная задача — задача не имеющая никаких способов решения более быстрых, чем последовательный перебор вариантов. По определению. 
>> Вы можете подразумевать что угодно, но у термина есть конкретное значение и Вы этот термин употребляете неправильно. 
> По определению, NP-задача (комбинаторная, т.е. представимая на графе) это задача, решение которой может быть найдено Недетерминированным автоматом за Полиномиальное число шагов (от характерного параметра сложности задачи, например, число вершин графа в задаче Гамильтона). 
> NP-полная задача — это задача, для которой не существует алгоритма ее решения полиномиальной сложности. 
 
 
Я наверное взялся бы доказать, что для представимой на графе задачи данное мною определение вполне  корректно. 
Вечером скорее всего, напишу подробнее.


Ответы и комментарии:


[Форум Rossia.org] [Начало] [Написать ответ]