Problemy trudnorozwiązywalne 2

Niepełne rozwiązania problemów NP — zupełnych:

Dla takich problemów zwykle szukamy algorytmów aproksymacyjnych — tzn. dostarczających rozwiązań bliskich dokładnym, ale to ma znaczenie tylko w problemach decyzyjnych.

Problemy jeszcze trudniejsze:

₉n

Są problemy gdzie dolne ograniczenia są podwójnie wykładnicze; np. dowodzenie prawdy wtzw. arytmetyce Presheraera jest klasy 0(2 ). Ponadto można pokazać, że dla tego problemu dolna granica pamięciowa jest złożoności O (2N). Dla algorytmu o takim dolnym ograniczeniu pamięciowym można pokazać, że istnieją dla niego dane wejściowe o rozsądnym rozmiarze (<150), które wymagają takiej pamięci dla danych pomocniczych, że nawet jeśli 1 bit pamięci miałby wielkość protonu, to cały Wszechświat nie wystarczyłby do ich zapamiętania.

Nieobliczalność i nierozstrzygalność:

Choć trudno w to uwierzyć są problemy jeszcze trudniejsze: są t problemy nieobliczalne, dla których nie ma żadnych algorytmów. (Dla problemów decyzyjnych sąto problemy nierozstrzygalne! Tzn., że dla niektórych problemów możemy wykazać, że są nieobliczalne (nierozstrzygalne).

Czyli jest podział:

/

nieobliczalne

(nierozstrzygalne)

wcale nie ma algorytmu

trudno

rozwiązywalne

nie ma algorytmu wielomianowego

łatwo

rozwiązywalne

<

są algorytmy wielomianowe

Problemem, który może być nierozstrzygalny jest problem domina. Ale jest tu pewna subtelność. Jeśli rozpatrzymy problem "węża domino" (jak w popularnej grze), to jest on rozstrzygalny, jeśli płaszczyzna, na której układamy jest skończona (bo istnieje skończona liczba węży, która da się ulokować na skończonej płaszczyźnie). Jest też rozstrzygalny na płaszczyźnie nie nieograniczonej. Ale jeśli weźmiemy dwie połowy nieograniczonej płaszczyzny, to na każdej takiej połowie problem jest nierozstrzygalny.

Inny problem nierozstrzygalny jest ważny z punktu budowy kompilatorów: nie istnieje algorytm, który po wczytaniu jako danych dwóch zbiorów reguł składniowych byłby w stanie stwierdzić w skończonym czasie czy definiuje ten sam język.