Problem decyzyjny - Decision problem

Problem decyzyjny ma tylko dwa możliwe wyjścia ( yes lub nie ) na każdym wejściu.

W teorii obliczalności i teorii złożoności obliczeniowej , problem decyzyjny to problem, który można postawić jako pytanie tak - nie w odniesieniu do wartości wejściowych. Przykładem problemu decyzyjnego jest rozstrzygnięcie, czy dana liczba naturalna jest liczbą pierwszą . Innym przykładem jest problem „podano dwie wartości x i y , czy x równomiernie podzielić y ?”. Odpowiedź brzmi „tak” lub „nie” w zależności od wartości x i y . Metodę rozwiązania problemu decyzyjnego, podaną w postaci algorytmu , nazywamy procedurą decyzyjną dla tego problemu. Procedura decyzja dla danego problemu decyzyjnego „dwie liczby x i y , czy x równomiernie podzielić y ?” dałby kroki do ustalenia, czy x równo dzieli y . Jednym z takich algorytmów jest dzielenie długie . Jeśli reszta wynosi zero, odpowiedź brzmi „tak”, w przeciwnym razie „nie”. Problem decyzyjny, który można rozwiązać za pomocą algorytmu, nazywa się rozstrzygalnym .

Problemy decyzyjne pojawiają się zwykle w matematycznych pytaniach o rozstrzygalność , to znaczy w kwestii istnienia skutecznej metody określania istnienia jakiegoś obiektu lub jego przynależności do zbioru; niektóre z najważniejszych problemów matematycznych są nierozstrzygalne .

Dziedzina złożoności obliczeniowej kategoryzuje możliwe do rozstrzygnięcia problemy decyzyjne według tego, jak trudne są one do rozwiązania. W tym sensie „trudny” jest opisywany w kategoriach zasobów obliczeniowych potrzebnych najbardziej wydajnemu algorytmowi do rozwiązania określonego problemu. W międzyczasie dziedzina teorii rekursji kategoryzuje nierozstrzygalne problemy decyzyjne według stopnia Turinga , który jest miarą niepoliczalności nieodłącznie związanej z każdym rozwiązaniem.

Definicja

Problem decyzyjny jest tak lub nie pytanie na nieskończony zbiór wejść. Tradycyjnie problem decyzyjny definiuje się jako zbiór możliwych wejść wraz ze zbiorem wejść, dla których odpowiedź brzmi tak .

Te dane wejściowe mogą być liczbami naturalnymi, ale mogą też być wartościami innego rodzaju, takimi jak ciągi binarne lub ciągi znaków z innego alfabetu . Podzbiór ciągów, dla których problem zwraca „tak”, jest językiem formalnym , a często problemy decyzyjne są definiowane jako języki formalne.

Za pomocą kodowania, takiego jak numeracja Gödla , dowolny ciąg można zakodować jako liczbę naturalną, za pomocą której problem decyzyjny można zdefiniować jako podzbiór liczb naturalnych. Dlatego algorytm problemu decyzyjnego polega na obliczeniu funkcji charakterystycznej podzbioru liczb naturalnych.

Przykłady

Klasycznym przykładem rozstrzygalnego problemu decyzyjnego jest zbiór liczb pierwszych. Można skutecznie zdecydować, czy dana liczba naturalna jest liczbą pierwszą, testując każdy możliwy nietrywialny czynnik. Chociaż znane są znacznie skuteczniejsze metody badania pierwszości , do ustalenia rozstrzygalności wystarczy istnienie jakiejkolwiek skutecznej metody.

Rozstrzygalność

Problem decyzyjny jest rozstrzygalny lub skutecznie rozwiązany, jeśli zbiór danych wejściowych (lub liczb naturalnych), dla których odpowiedź brzmi tak, jest zbiorem rekurencyjnym . Problemem jest częściowo rozstrzygalne , semidecidable , rozwiązywalne , albo udowodnić , czy zestaw wejść (lub liczb naturalnych), dla których odpowiedź jest twierdząca rekurencyjnie przeliczalny zbiór . Problemy, których nie można rozstrzygnąć, są nierozstrzygalne . Dla nich nie jest możliwe stworzenie algorytmu, wydajnego lub innego, który by je rozwiązał.

Zatrzymanie problemem jest ważnym problemem nierozstrzygalny decyzji; więcej przykładów znajduje się na liście nierozstrzygalnych problemów .

Kompletne problemy

Problemy decyzyjne można uporządkować według redukowalności wielu jeden i powiązać z wykonalnymi redukcjami, takimi jak redukcje wielomianowe w czasie . Problem decyzja P mówi się, że kompletna dla zestawu problemów decyzyjnych S jeśli P jest członkiem S i każdy problem w S może być zmniejszona do P . Pełne problemy decyzyjne są wykorzystywane w obliczeniowej teorii złożoności do charakteryzowania klas złożoności problemów decyzyjnych. Na przykład, logiczny problem spełnialności jest kompletny dla klasy NP problemów decyzyjnych w warunkach redukowalności w czasie wielomianu.

Problemy funkcjonalne

Problemy decyzyjne są ściśle związane z problemami funkcjonalnymi , w przypadku których odpowiedzi mogą być bardziej złożone niż proste „tak” lub „nie”. Odpowiedni problem funkcji brzmi: „mając dwie liczby x i y , co jest podzielone przez x przez y ?”.

Problemem funkcja składa się z częściowej funkcji f ; nieformalnym „problemem” jest obliczenie wartości f na wejściach, dla których jest ona zdefiniowana.

Każdy problem funkcjonalny można przekształcić w problem decyzyjny; problem decyzyjny to tylko wykres powiązanej funkcji. (Wykres funkcji f jest zbiorem par ( x , y ) takim, że f ( x ) = y .) Gdyby ten problem decyzyjny był efektywnie rozwiązany, to byłby również problem funkcji. Ta redukcja nie uwzględnia jednak złożoności obliczeniowej. Na przykład możliwe jest, aby wykres funkcji był rozstrzygalny w czasie wielomianu (w którym to przypadku czas działania jest obliczany jako funkcja pary ( x , y )), gdy funkcja nie jest obliczalna w czasie wielomianu (w którym czas działania przypadku jest obliczany jako funkcja samego x ). Funkcja f ( x ) = 2 x ma tę właściwość.

Każdy problem decyzyjny można przekształcić w zadanie funkcyjne obliczania funkcji charakterystycznej zbioru związanego z problemem decyzyjnym. Jeśli ta funkcja jest obliczalna, wówczas związany z nią problem decyzyjny jest rozstrzygalny. Jednak ta redukcja jest bardziej liberalna niż standardowa redukcja stosowana w przypadku złożoności obliczeniowej (czasami nazywana redukcją wielomianową wielokrotną); na przykład złożoność charakterystycznych funkcji problemu NP-zupełnego i jego uzupełnienia co-NP-pełnego jest dokładnie taka sama, chociaż leżące u jego podstaw problemy decyzyjne mogą nie być uważane za równoważne w niektórych typowych modelach obliczeniowych.

Problemy z optymalizacją

W przeciwieństwie do problemów decyzyjnych, dla których istnieje tylko jedna poprawna odpowiedź dla każdego wejścia, problemy optymalizacyjne dotyczą znalezienia najlepszej odpowiedzi na dane wejście. Problemy z optymalizacją pojawiają się naturalnie w wielu zastosowaniach, takich jak problem komiwojażera i wiele pytań w programowaniu liniowym .

Istnieją standardowe techniki przekształcania problemów funkcji i optymalizacji w problemy decyzyjne. Na przykład w przypadku komiwojażera problemem optymalizacji jest stworzenie wycieczki o minimalnej wadze. Związane jest problem decyzyjny: dla każdego N , aby zdecydować, czy wykres ma żadnej trasy o masie mniejszej niż N . Wielokrotnie odpowiadając na problem decyzyjny, można określić minimalną wagę wycieczki.

Ponieważ teoria problemów decyzyjnych jest bardzo dobrze rozwinięta, badania nad teorią złożoności zwykle skupiały się na problemach decyzyjnych. Same problemy optymalizacyjne są nadal przedmiotem zainteresowania w teorii obliczalności, a także w takich dziedzinach, jak badania operacyjne .

Zobacz też

Bibliografia

  • Kozen, DC (2012), Automata and Computability , Springer.
  • Hartley Rogers, Jr. , The Theory of Recursive Functions and Effective Computability , MIT Press, ISBN   0-262-68052-1 (miękka oprawa ), ISBN   0-07-053522-1
  • Sipser, M. (1996), Wprowadzenie do teorii obliczeń , PWS Publishing Co.
  • Robert I. Soare (1987), Recursively Enumerable Sets and Degrees , Springer-Verlag, ISBN   0-387-15299-7
  • Daniel Kroening & Ofer Strichman, Procedury decyzyjne , Springer, ISBN   978-3-540-74104-6
  • Aaron Bradley & Zohar Manna , rachunek obliczeniowy , Springer, ISBN   978-3-540-74112-1