Kwestia decyzji

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

W teorii obliczalności i teorii złożoności obliczeniowej problem decyzyjny to problem obliczeniowy, który można postawić jako pytanie tak-nie dotyczące wartości wejściowych. Przykładem problemu decyzyjnego jest rozstrzygnięcie za pomocą algorytmu, czy dana liczba naturalna jest liczbą pierwszą . Innym jest problem „biorąc pod uwagę dwie liczby x i y , czy x równo dzieli 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 decyzyjna dla problemu decyzyjnego „czy biorąc pod uwagę dwie liczby x i y , x równo dzieli y ?” dałoby kroki do ustalenia, czy x równo dzieli y . Jednym z takich algorytmów jest długi podział . 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 zwykle pojawiają się w matematycznych kwestiach rozstrzygalności , 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 w matematyce są nierozstrzygalne .

Dziedzina złożoności obliczeniowej kategoryzuje rozstrzygalne problemy decyzyjne według stopnia trudności ich rozwiązania. „Trudne” w tym sensie jest opisywane w kategoriach zasobów obliczeniowych potrzebnych najbardziej wydajnemu algorytmowi do rozwiązania określonego problemu. Tymczasem dziedzina teorii rekurencji kategoryzuje nierozstrzygalne problemy decyzyjne według stopnia Turinga , który jest miarą nieobliczalności nieodłącznie związanej z każdym rozwiązaniem.

Definicja

Problem decyzyjny to pytanie typu „tak” lub „nie” dotyczące nieskończonego zestawu danych wejściowych. Tradycyjnie definiuje się problem decyzyjny jako zbiór możliwych danych wejściowych wraz ze zbiorem danych wejściowych, dla których odpowiedź brzmi „ tak” .

Te dane wejściowe mogą być liczbami naturalnymi, ale mogą też być wartościami innego rodzaju, na przykład łańcuchami binarnymi lub ciągami nad jakimś innym alfabetem . Podzbiór łańcuchów, dla których problem zwraca „tak”, jest językiem formalnym i często problemy decyzyjne są definiowane jako języki formalne.

Korzystając z kodowania, takiego jak numeracja Gödla , dowolny ciąg znaków można zakodować jako liczbę naturalną, za pomocą której można zdefiniować problem decyzyjny 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 rozstrzygnąć, czy dana liczba naturalna jest liczbą pierwszą, sprawdzając każdy możliwy nietrywialny czynnik. Chociaż znane są znacznie wydajniejsze metody testowania pierwszości , istnienie jakiejkolwiek skutecznej metody wystarczy do ustalenia rozstrzygalności.

rozstrzygalność

Problem decyzyjny jest rozstrzygalny lub skutecznie rozwiązywalny , jeśli zbiór danych wejściowych (lub liczb naturalnych), dla którego odpowiedź brzmi tak, jest zbiorem rekurencyjnym . Problem jest częściowo rozstrzygalny , półrozstrzygalny , rozwiązywalny lub możliwy do udowodnienia , jeśli zbiór danych wejściowych (lub liczb naturalnych), dla których odpowiedź brzmi tak, jest zbiorem rekurencyjnie przeliczalnym . Problemy, które nie są rozstrzygalne, są nierozstrzygalne . Dla nich nie jest możliwe stworzenie algorytmu, wydajnego lub innego, który je rozwiązuje.

Problem zatrzymania jest ważnym nierozstrzygalnym problemem decyzyjnym; więcej przykładów można znaleźć na liście problemów nierozstrzygalnych .

Kompletne problemy

Problemy decyzyjne można uporządkować według redukowalności do wielu jeden i odnieść do możliwych redukcji, takich jak redukcje w czasie wielomianowym . Mówimy , że problem decyzyjny P jest zupełny dla zbioru problemów decyzyjnych S , jeśli P należy do zbioru S i każdy problem w S można sprowadzić do P . Kompletne problemy decyzyjne są wykorzystywane w teorii złożoności obliczeniowej do charakteryzowania klas złożoności problemów decyzyjnych. Na przykład problem spełnialności Boole'a jest kompletny dla klasy NP problemów decyzyjnych w warunkach redukowalności w czasie wielomianowym.

Problemy z funkcjami

Problemy decyzyjne są ściśle związane z problemami funkcyjnymi , które mogą mieć odpowiedzi bardziej złożone niż proste „tak” lub „nie”. Odpowiedni problem funkcyjny to „biorąc pod uwagę dwie liczby x i y , ile wynosi x podzielone przez y ?”.

Problem funkcyjny składa się z częściowej funkcji f ; nieformalny „problem” polega na obliczeniu wartości f na wejściach, dla których jest zdefiniowany.

Każdy problem funkcyjny można przekształcić w problem decyzyjny; problem decyzyjny jest po prostu wykresem powiązanej funkcji. (Wykres funkcji f jest zbiorem par ( x , y ) takich, że f ( x ) = y .) Gdyby ten problem decyzyjny był skutecznie rozwiązywalny, problem funkcji również byłby rozwiązany. Ta redukcja nie uwzględnia jednak złożoności obliczeniowej. Na przykład wykres funkcji może być rozstrzygalny w czasie wielomianowym (w takim przypadku czas działania jest obliczany jako funkcja pary ( x , y ) ) , gdy funkcja nie jest obliczalna w czasie wielomianowym (w którym czas trwania sprawy 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 problem funkcyjny obliczania funkcji charakterystycznej zbioru związanego z problemem decyzyjnym. Jeśli ta funkcja jest obliczalna, to związany z nią problem decyzyjny jest rozstrzygalny. Jednak ta redukcja jest bardziej liberalna niż standardowa redukcja stosowana w złożoności obliczeniowej (czasami nazywana redukcją wielomianową w czasie wielomianowym); na przykład złożoność funkcji charakterystycznych problemu NP-zupełnego i jego ko-NP-zupełnego dopełnienia jest dokładnie taka sama, mimo że podstawowe 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 dla określonego wejścia. Problemy optymalizacyjne 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 problemie komiwojażera problem optymalizacji polega na stworzeniu wycieczki o minimalnej wadze. Związany z tym problem decyzyjny to: dla każdego N zdecydować, czy wykres ma trasę o wadze mniejszej niż N . Wielokrotnie odpowiadając na problem decyzyjny, można znaleźć minimalną wagę wycieczki.

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

Zobacz też

WSZYSTKIE (złożoność)
Problem obliczeniowy
Rozstrzygalność (logika) – dla problemu rozstrzygnięcia, czy formuła jest konsekwencją teorii logicznej .
Problem z wyszukiwaniem
Problem z liczeniem (złożoność)
Zadanie tekstowe (matematyka)

Kozen, DC (2012). Automaty i obliczalność . Skoczek. ISBN 9781461218449 .
Hartley, Rogers, Jr (1987). Teoria funkcji rekurencyjnych i efektywna obliczalność . MIT Press. ISBN 9780262680523 .
Sipser, M. (2020). Wprowadzenie do teorii obliczeń . Nauka Cengage'a. ISBN 9780357670583 .
Soare, Robert I. (1987). Rekurencyjnie przeliczalne zbiory i stopnie . Skoczek. ISBN 0-387-15299-7 .
Kroening, Daniel ; Strichman, Ofer (23 maja 2008). Procedury decyzyjne . Skoczek. ISBN 978-3-540-74104-6 .
Bradley, Aaron; Manna, Zohar (3 września 2007). Rachunek obliczeniowy . Skoczek. ISBN 978-3-540-74112-1 .