Równoważność z problemami funkcyjnymi Problem funkcyjny to dowolna częściowa funkcja f. Każda taka funkcja może być zamieniona na problem decyzyjny. Przykładowo dla każdej funkcji możemy zdefiniować jej graf (zbiór par (x,y), takich że f(x) = y) i rozważać go jako problem decyzyjny. Ta redukcja nie zachowuje jednak złożoności obliczeniowej – np. graf funkcji może być obliczalny w czasie wielomianowym, podczas gdy sama funkcja nie (licząc w stosunku do długości wejścia). Taką własność ma np. funkcja f(x) = 2x.
Każdy problem decyzyjny można również zamienić na funkcyjny, wyliczając funkcję charakterystyczną zbioru akceptowanych wejść. Ta redukcja zachowuje obliczalność, ale w praktyce stosuje się bardziej dokładne redukcje zachowujące również klasy złożoności. W tej redukcji przykładowo funkcje charakterystyczne klasy NP są tym samym, co funkcje charakterystyczne klasy Co-NP, mimo że odpowiadające im klasy problemów decyzyjnych są uważane za różne.
Zobacz też problem obliczeniowy
Kategoria:Teoria decyzji Kategoria:Teoria obliczeń