Я просмотрел все ссылки по этой теме, но все еще не понимаю, почему мы считаем NP Complete NP. Только ли мы можем проверить это за полиномиальное время, когда мы говорим, что NP-полные проблемы являются NP, но у нас есть некоторые NP-проблемы, которые также могут быть решены за полиномиальное время, но NP-полные проблемы не могут быть решены за полиномиальное время, поэтому тогда не противоречит ли это свойству называть NP полные проблемы NP?
Почему мы говорим, что полные проблемы NP - это NP?
Ответы (1)
Существует множество P задач принятия решений, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время.
Затем существует набор NP задач принятия решений, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время, то есть те, решение которых может быть проверено за полиномиальное время при некоторой свидетельской строке.
Детерминированная машина Тьюринга может моделировать недетерминированную машину, поэтому мы знаем, что существует алгоритм экспоненциального времени для решения NP-задач. Однако мы не знаем, действительно ли у нас P = NP.
NP-полная проблема - это NP-проблема, которая по крайней мере так же сложна, как и любая другая NP-проблема. Например, SAT является NP-полным, потому что он может эффективно кодировать недетерминированную машину Тьюринга, а решение SAT означает моделирование этой машины. Вы можете показать NP-полноту проблемы решения проблемы A, продемонстрировав, что ранее известная как NP-полная проблема B может быть уменьшена до A за полиномиальное время. Это означает, что если A можно решить за полиномиальное время, то B можно решить и за полиномиальное время, таким образом, в некотором смысле A по крайней мере так же сложно, как B.
но у нас есть некоторые проблемы NP, которые также могут быть решены за полиномиальное время
Именно потому, что P является подмножеством NP.
Полные задачи NP не могут быть решены за полиномиальное время
Мы этого точно не знаем.
не противоречит ли это свойству называть NP полными проблемами NP
Нисколько. Да, в NP есть проблемы, которые, как мы знаем, есть и в P. Это не значит, что в NP нет проблем, которых нет в P. Но, конечно, мы не знаем последнего. Может быть даже так, что каждая NP-полная проблема находится в P, в случае P = NP.
person
Niklas B.
schedule
14.07.2015
Это (1) не отвечает на вопрос
Why do we say that NP complete problems are NP?. (2) Введение в заблуждение: You can show NP-completeness of a problem A by demonstrating that a previously known to be NP-complete problem B can be reduced to A in polynomial time. Нет, это покажет, что проблема (A) является NP-сложной.
- person amit; 14.07.2015
@amit Ну, конечно, я имел в виду проблему с решением А здесь, спасибо
- person Niklas B.; 14.07.2015
@amit И также мне кажется, что мой ответ в значительной степени проясняет все, и последнее предложение является явным ответом на вопрос, хотя чтение остальной части текста в любом случае должно прояснить любую путаницу
- person Niklas B.; 14.07.2015
Ответ на вопрос, почему проблемы с NPC возникают в NP, краток и отсутствует в ответе. По определению.
- person amit; 14.07.2015
@amit Хорошо, но иногда приходится читать между строк. В вопросе OP есть много неправильных представлений, которые мой ответ пытается всесторонне прояснить. Мне кажется, что ваш ответ TL; DR дает нулевое значение в этом контексте, хотя это, конечно, неоспоримо верно
- person Niklas B.; 14.07.2015
Вот почему я не публиковал его в качестве ответа, но, отвечая на вопрос, на который есть однозначный ответ, без его упоминания, не хватает сути. Вы можете прояснять все сколько хотите, но это не объясняет того, почему NPC находится в NP? Это объясняет, почему это могло быть, или почему это не противоречит, но все же не объясняет, почему это ЕСТЬ.
- person amit; 14.07.2015
NPпросто означает, что ответ можно проверить за полиномиальное время.NP-Completeозначает, что его можно проверить за полиномиальное время, но решение не может быть найдено за полиномиальное время. Это контрастирует сP, который можно решить и проверить за полиномиальное время. ЕслиP=NPхотя (и это такое же большое если, как они появляются), это означает, чтоNP-Complete- пустой набор. (Или, если быть более точным, это означало бы, чтоNP-Completeсовпадает с наборомP.) - person biziclop schedule 14.07.2015NPвообще не должно быть серьезных проблем. Это хорошее представление из них всех. - person biziclop schedule 14.07.2015....that means NP-Complete is an empty set. (Or to be more precise it would mean that NP-Complete is the same set as P.)это противоречит самому себе :( [Чем позже будет правильнее, это будет означатьNPC=NP=CO-NP=P != {}] - person amit schedule 14.07.2015NP-полная проблема должна содержаться вNP. - person Codor schedule 14.07.2015