Was ist ein "natürliches" NP-vollständiges Problem?

Question

Ich denke, ich habe ein ziemlich gutes Verständnis von NP-Complete, NP-Hard usw. im Allgemeinen, aber plötzlich stolperte ich über etwas Literatur, ich fand jemanden, der ein "natürliches" NP-vollständiges Problem ausdrückte mit diesen Zitaten. Ich verstand nicht, was sie meinten, also versuchte ich es zu googeln - es tauchte mehrmals auf, aber niemand machte sich jemals die Mühe, zu erklären, was sie mit "natürlich" meinten.

Kann mir jemand erklären, was der Kontext dafür ist, Zitate um "natürlich" zu setzen - was meint man, wenn sie ein "natürliches" NP-vollständiges Problem sagen?

Answer 1

Im Kontext der CS-Theorie sieht man oft, dass jemand Probleme mit bestimmten Eigenschaften beweist, indem er hochgradig konstruierte Probleme definiert, auf die niemand in der Praxis wahrscheinlich stoßen würde. Zum Beispiel zeigt Ladner's theorem dass wenn P ≠ NP, dann gibt es ein Problem in NP ist, die nicht in P ist aber auch nicht NP -komplette, aber das spezifische Problem erdacht ist hoch erfunden und wurde im Wesentlichen zu dem einzigen Zweck konstruiert, das angegebene Eigentum zu haben. Diese Probleme werden subjektiv als "unnatürliche" Probleme bezeichnet, weil das Problem erfunden wurde, um eine Eigenschaft zu haben.

Ein "natürliches" Problem ist ein Problem, das subjektiv selbst interessant ist - normalerweise etwas, das vorher studiert wurde -, von dem später gezeigt wird, dass es eine interessante theoretische Eigenschaft besitzt. In diesem Zusammenhang wäre ein "natürliches" vollständiges Problem, das tatsächlich in der Praxis auftritt, etwa die 3-Färbbarkeit, das Hamilton-Zyklus-Problem oder das boolesche Erfüllbarkeits-Problem.