Обсуждение:Класс NP

На мой взгляд, введение не согласуется с последующим изложением и может вводить читателя в заблуждение. Во-первых, класс NP является не множеством "алгоритмов", а множеством "языков". Во-вторых, неясен смысл словосочетания "сильно зависит от входных данных". В-третьих, я впервые сталкиваюсь с термином "свидетель решения". Как в отечественной, так и в зарубежной литературе более принят термин "сертификат". И вообще, введение лучше бы переработать, по возможности сохранив простоту и доступность, но без смысловых искажений.

"Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L."

По-моему, тут вместо "у нас есть слово, принадлежащее языку" следует написат "у нас есть слово". Так как если оно уже принадлежит языку, то незачем удостоверяться, что оно действительно принадлежит L. 80.91.179.2 19:22, 15 февраля 2009 (UTC)

Мне кажется, что нужно в самом начале статьи дать не пространные рассуждения об алгоритмах и "свидетелях решения", а оба точных определения.--ant_asm 15:01, 22 июня 2010 (UTC)

• Не нужно. Введение должно быть понятно и не специалисту и по возможности должно избегать технических терминов. Точные определения даны в разделе Определения. Maxal 19:14, 22 июня 2010 (UTC)

Что такое NP-трудная задача?

Сюда ведёт перенаправление со страницы NP-трудная задача, но что это такое, здесь не описано. Это задача класса NP? Это NP-полная задача? Неясно. -- 80.237.26.14 10:33, 12 марта 2012 (UTC)

Решения и их сертификаты

Задача: у Пети было 5 яблок. 2 он отдал Маше. Возможно ли ответить на вопрос, сколько яблок осталось у Пети?
Решение: да.
Сертификат решения: 3.

Это верно? Если нет - почему?
Если да - верно ли вообще (как это можно заключить из раздела "Примеры задач класса NP"), что "сертификат решения" - это конкретный пример (либо единственно возможный, либо один из многих), соответствующий ответу на вопрос общего характера, поставленный в задаче в качестве основного? Т.е., проще говоря, "сертификат решения" - это то, что можно подставить в условие для проверки решения (точнее, ответа) на нормальной машине за нормальное время?
Если нет - что ещё, кроме конкретного примера, может быть "сертификатом решения"?

Зачем вообще нужно понятие "сертификат решения", что оно добавляет в теорию?
Верно ли, что оно нужно для корректности определения класса NP? А именно - что это "проблемы разрешимости, решение которых возможно проверить на машине Тьюринга [нормальной, реальной, а не умозрительной "сверхудачливой"] за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения)"? Верно ли, что это "при наличии..." - ключевое условие принадлежности к NP?
Если да - верно ли, что NP-трудные задачи (кроме NP-полных) таковы, что их решения не могут быть проверены на детерминированной машине Тьюринга за полиномиальное время даже при наличии "сертификата"? Или, эквивалентно (?) - таковы, что не могут быть решены за полиномиальное время даже на недетерминированной машине Тьюринга?

В школе, вроде, у задач были условия, решения и ответы. А в статьях про классы разрешимости понятие "решение" применяется в значении "ответ". Что же, сам процесс отыскания ответа, собственно решение задачи как строгая цепочка связанных утверждений - не интересует в принципе, так что даже его термин переопределён? Если нет - зачем такая двузначность с одновременным выкидыванием привычного понятия?
213.24.126.123 07:31, 10 июля 2017 (UTC)MichaelMM

Какие задачи входят в класс NP?

en.wikipedia.org - decision problem (задачи решения)

И 3 ссылки в статье:

Гирш - задачи поиска

Кормен - задачи принятия решения

Хопкрофт - “да/нет”-версия проблемы, и на схеме 10.2 кривой перевод decision как разрешение

Каким образом это превратилось в задачи разрешимости (decidability)?!

Зачем и откуда это путаница с понятием разрешимости (decidability)?! Зачем писать термин, который нигде не используется?