[дискретные экстремальные задачи] Классы P и NP

Marina32

объяните, пожалуйста, в двух словах, чем отличаются эти классы.
определение каждого из них уже по несколько раз перечитал, но логической разницы не могу понять до конца.

Marina32

Класс Р составляют такие задачи поставленные в форме распознавания, для кот. существуют алгоритмы, решающие эти задачи с полиномиальной оценкой времени их работы от размера входа.
Класс NP составляют дискретные задачи распознавания, для которых имеется алгоритм проверки обоснования ответа "да" с полиномиальной оценкой времени.
Это определения из учебника. Я понял, чего я не улавливаю. Что означает слово "решающие" в первом определении? Решить задачу - не значит обосновать ответ "да" для задачи распознавания?

natunchik

Это определения из учебника. Я понял, чего я не улавливаю. Что означает слово "решающие" в первом определении? Решить задачу - не значит обосновать ответ "да" для задачи распознавания?
Найти корень уравнения довольно сложно. Проверить, что некоторое данное число является корнем, гораздо проще. Собственно, задача нахождения корня булевской функции - нп-полная, если мне ничего не изменяет.

natunchik

Но формулировки у тя в учебнике чудофищные =) Если как следует напрячься, то можно придумать, как сказанное в нём можно подогнать под правильное определение =)
Типа, "задача распознавания" - это ответить, принадлежит ли данное слово некоему языку. Ответ "да" подразумевает наличие вычисленного номера слова в языке (то есть процедуры, которая позволяет его, слово, построить (за полиномиальное время для NP задач.

Mike3

да ладно, нормальные вроде формулировки. я по крайней мере примерно так и осилил
а вот твой второй абзац чото пока не могу

Mike3

а, все. догнал.

Mike3

кстати, может кто-нибудь еще до 10 утра напишет на пальцах, что такое "градиентный алгоритм поиска приближенного решения задачи на покрытие" или где про это почитать в сети.
ну и заодно: где прочитать вкратце про поиск кратчайшего и надежного путей в графе.

Marina32

ага, спасибо большое

888julia888

определение P и NP через машину Тьюринга надо?
или разобралсо?

Marina32

кстати, напиши, мне интересно
Оставить комментарий
Имя или ник:
Комментарий: