W pracy Stephena Cooka na temat problemu P vs NP [1] stwierdza, że [2]:
Teza wykonalności: Naturalny problem ma wykonalny algorytm, jeśli ma algorytm czasu wielomianowego.
Moje pytanie brzmi: co dokładnie on (lub ogólnie tak naprawdę, co to znaczy) przez „ naturalny problem”? Mówienie o naturalnych problemach wydaje się dość powszechne, ale nie znalazłem jeszcze definicji. Wydaje mi się, że czegoś mi brakuje. Oto kilka możliwych odpowiedzi, o których myślę:
Pierwsza możliwa odpowiedź
Cook mówi w swoim artykule, że „naturalne” musi zostać wyjaśnione. Mówi: „generalnie nie uważamy, że klasa z parametrem jest tak naturalna, jak zbiór grafów, które można osadzić na powierzchni rodzaju k , k > 1.” [3] Po pierwsze, wydaje się, że to mówi „ „naturalne” nie jest raczej tym, czym jest; ale jeśli każdy problem jest albo naturalny, albo nie, a to w pełni opisuje wszystkie problemy, które nie są naturalne, wystarczyłoby, aby zdefiniować naturalny. (Ale kwalifikator „ogólnie” sugeruje, że nie jest to wystarczający i konieczny opis problemów, które nie są naturalne).
Wydaje mi się, że „klasy z parametrami” odnoszą się do ciągliwości parametrów o stałych parametrach, przez co rozumiemy problemy, które mają ograniczone możliwości wprowadzania danych, tak że wymuszona jest wykonalność. Możemy więc rozwiązać problem plecaka [4] za pomocą algorytmu czasu wielomianowego, jeśli naprawimy ciężar, który może unieść plecak (ale ogólnie nie ma rozwiązania w czasie wielomianowym). Biorąc to pod uwagę, uważam, że bycie „naturalnym” oznacza, że problem nie jest ograniczony („sztucznie” ograniczony?) W sposób, który wymusza algorytm wielomianowy z problemu, którego nie można rozwiązać w czasie wielomianowym.
Powodem, dla którego nie jestem pewien, czy jest to właściwy sposób zrozumienia pojęcia Cooka o „naturalnym”, jest to, że nie jestem absolutnie pewien, co kwalifikują się tutaj „naturalne” kwalifikacje. Jeśli upuścisz „naturalny”, wtedy „problem ma wykonalny algorytm, jeśli ma algorytm wielomianowy”. Ale wydaje się to całkowicie uzasadnione: problem plecaka nie ma wykonalnego algorytmu, ponieważ nie ma algorytmu czasu wielomianowego; zdolność plecakowa z ustaloną paramaterą ma wykonalny algorytm, ponieważ ma algorytm czasu wielomianowego. Oba konta wydają się zgodne z pojęciem problemu z wykonalnym algorytmem.
Rozumiem, że może to być najlepszy przewodnik do zrozumienia, co znaczy Cook, ponieważ Cook faktycznie się odwraca i definiuje. Rozumiem również, że to pojęcie natury jest ujęte w tym pytaniu StackExchange. [5}
Ale jest inny.
Druga możliwa odpowiedź
William Gasarch w swoim artykule „Klasyfikowanie problemów w klasy złożoności” [6] mówi, że przeprowadzi „dosłowną dyskusję na temat naturalnego problemu” [7]. Na zakończenie pracy [8] odbywa się wymiana w formie dialogu, w której jeden z mówców mówi:
„Co sprawia, że problem jest naturalny? Z jednej strony nie skonstruowałem problemu wyłącznie w celu nieobecności w P. Więc to nie jest głupi problem z dupą. Czy następnie podnosi się do poziomu bycia naturalnym?”
Wydaje mi się więc, że Gasarch mówi, że jeśli mamy problem, który nie jest celowo skonstruowany, abyśmy mogli powiedzieć, że nie ma go w P, to jest to naturalne. Tak więc przy odrobinie twórczej interpretacji wydaje się, że Gasarch mówi coś co najmniej spójnego z Cookiem: z jednej strony Gasarch mówi, że nie bycie skonstruowanym z jedynym celem nie będącym w P sprawia, że problem nie jest naturalny; z drugiej strony Cook twierdzi, że problem jest naturalny, jeśli nie ma parametrów. Ale sama spójność nie daje definicji.
Trzecia możliwa odpowiedź
W artykule w Wikipedii dotyczącym „dobrze postawionego problemu” [9] przedstawiono definicję dobrze postawionego problemu przez Jacquesa Hadamarda, a następnie stwierdzono, że dobrze postawiony problem można uznać za „naturalny” problem w tym, że istnieją fizyczne procesy modelowane przez te problemy ”. Problem jest więc naturalny, czy tylko wtedy, gdy modeluje proces fizyczny?
Kwalifikacje Hadamarda, według Wikipedii, są następujące: (i) istnieje rozwiązanie, (ii) rozwiązanie jest unikalne, oraz (iii) zachowanie rozwiązania zmienia się w sposób ciągły wraz z warunkami początkowymi. Wydaje się, że różni się to od pozostałych dwóch definicji. Wydaje mi się, że „naturalne” nie jest używane dokładnie w ten sam sposób (zwłaszcza jeśli zgadzamy się z interpretacją, że problem jest naturalny tylko wtedy, gdy modeluje proces fizyczny), ale chciałem go uwzględnić, ponieważ wpadłem na w moich badaniach nad tym pytaniem, i są punkty kontaktowe.
Więc moje pytanie brzmi: co jest naturalnym problemem? Czy którakolwiek z tych odpowiedzi lub jakakolwiek ich kombinacja jest poprawna? Czy brakuje mi innej odpowiedzi? Dziękuję Ci.
- „The Statement of the Problem”, 2006, opublikowane online w Clay Mathematics; tytuł: „The P vs. NP Problem”, http://www.claymath.org/sites/default/files/pvsnp.pdf
- p. 3)
- p. 4
- https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
- Najtrudniejszy znany problem naturalny w P Uważam, że naturalny problem wynika z tego opisu, ale nie ogranicza k do bycia największym.
- https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
- p. 2)
- p. 47–8, sekcja 25
- https://en.wikipedia.org/wiki/Well-posed_problem