130
правок
Изменения
→Связь P и NP: Заменил ссылки на примечания
== Связь P и NP ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым. Были осуществлены различные подходы к разрешению этой задачи: попытка найти [[Теорема_Махэни|редкий <tex>\mathrm{NP}</tex>-полный язык]]; было доказано, что [[Теорема_Бейкера_—_Гилла_—_Соловэя|доказательство должно быть нерелятивизующимся]]; различные попытки найти полиномиальные решения для задач из <tex>\mathrm{NPC}</tex>:
*«решение» 3SAT за полиномиальное время]<ref>[http://arxiv.org/abs/1011.3944 «решение» 3SAT за полиномиальное времяNon-Orthodox Combinatorial Models Based on Discordant Structures];</ref>*задача о коммивояжёре<ref>[http://www.cse.yorku.ca/~aaw/Zambito/TSP_Survey.pdf задача о коммивояжереThe Traveling Salesman Problem: A Comprehensive Survey]</ref>.
Некоторые задачи из <tex>\mathrm{P}</tex> очень похожи на задачи из <tex>\mathrm{NP}</tex>, при этом различие между задачами кажется совершенно незначительным:
|}
== Примечания ==
<references/>
== См. также ==
* [[Недетерминированные вычисления]]
