Что такое естественная NP-полная задача?

Я думаю, что у меня довольно приличное понимание NP-Complete, NP-Hard и т. д. в целом, но внезапно, наткнувшись на какую-то литературу, я обнаружил, что кто-то говорит о «естественной» NP-полной задаче — явно с этими цитаты. Я не понял, что они имели в виду, поэтому попытался поискать в гугле — он появлялся еще несколько раз, но никто так и не удосужился объяснить, что они имели в виду под «естественным».

Может ли кто-нибудь объяснить мне, каков контекст для помещения кавычек вокруг «естественной» — что имеется в виду, когда они говорят «естественная» NP-полная проблема?


np
person vawd_gandi    schedule 11.05.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В контексте теории CS вы часто видите, как кто-то доказывает, что существуют проблемы с определенными свойствами, определяя весьма надуманные проблемы, с которыми на практике вряд ли кто-то столкнется. Например, теорема Ладнера показывает, что если P < strong>NP, то в NP есть проблема, которой нет в P, но она также не является NP-полной , но придуманная конкретная задача сильно надумана и, по существу, строилась с единственной целью — иметь указанное свойство. Эти проблемы субъективно называются «неестественными» проблемами, потому что проблема была придумана, чтобы иметь какое-то свойство.

«Естественная» проблема — это проблема, которая субъективно интересна сама по себе — обычно это то, что было изучено ранее, — позже было показано, что у нее есть какое-то интересное теоретическое свойство. В этом контексте «естественной» NP-полной проблемой будет NP-полная проблема, которая действительно возникает на практике — скажем, что-то вроде 3-раскрашиваемости, гамильтонова цикла проблема или логическая выполнимость.

person templatetypedef    schedule 22.05.2016