Na szczęście wiele ważnych problemów obliczeniowych umiemy rozwiązywać w czasie wielomianowym. Jednak w praktyce wielomian wielomianowi nierówny – jest przecież istotne, czy dany problem umiemy rozwiązać w czasie  czy też w czasie  Okazuje się, że także w przypadku problemów rozwiązywalnych w czasie wielomianowym (tzw. klasa problemów P) znane są pewne narzędzia pozwalające stwierdzić, że danego problemu zapewne nie da się rozwiązać w czasie szybszym niż taki a taki, a jeśli nawet się da, to jest to bardzo trudne.

W tym artykule skupimy naszą uwagę na następującym problemie:

Wszystkie omawiane w tym artykule problemy mają charakter decyzyjny, tzn. odpowiedzią w każdym z nich jest pojedyncza wartość logiczna. Na potrzeby naszego artykułu przyjmiemy następującą definicję redukcji problemu:

Będziemy wówczas pisali, że  co oznacza tyle, że problem  jest co najmniej tak trudny jak problem  gdyż jeśli umiemy w czasie  rozwiązać problem  to umiemy w takim samym czasie rozwiązać problem  Jeśli  oraz  to będziemy pisali, że

Problemem, który będziemy redukować do innych zagadnień, jest wspomniany już problem . Przez wiele lat znany był algorytm rozwiązujący ten problem w czasie (patrz zadanie 1 na marginesie) i uważano, że nie da się go rozwiązać w złożoności mniejszej niż  Wprowadzono też klasę problemów -trudnych, czyli problemów, do których można zredukować problem w czasie  Od 2005 roku wiadomo jednak, że problem można rozwiązać troszeczkę szybciej, a mianowicie w czasie

Mimo tego usprawnienia wciąż nie widać nadziei na znalezienie algorytmu rozwiązującego ten problem w czasie istotnie lepszym niż

Będziemy także używać następującego bliźniaczego problemu , który jest równoważny z problemem (tj. ):

Problemy, które będziemy rozważać w dalszej części tekstu, mają charakter geometryczny. Jako pierwszy rozpatrzymy problem nazywany – podstawowy problem -trudny w geometrii, służący jako narzędzie do dowodzenia -trudności innych problemów. Jest on określony następująco:

Rys. 1 Instancja problemu otrzymana z instancji  problemu . Wynikiem jest

Po chwili namysłu nietrudno dostrzec tu podobieństwo do problemu . Nie jest to przypadek; zachodzi bowiem . Przeprowadzimy tylko redukcję , redukcja w drugą stronę jest właściwie taka sama. Wystarczy mianowicie dla każdej liczby  wybrać punkt  na prostej  dla każdej liczby – punkt  a dla każdej liczby – punkt  patrz rysunek 1. Punkty  i   są współliniowe, gdy

czyli dokładnie gdy  Stąd odpowiedź dla otrzymanej instancji problemu  jest pozytywna wtedy i tylko wtedy, gdy pozytywna jest odpowiedź dla odpowiadającej jej instancji problemu , a to jest dokładnie to, co chcieliśmy uzyskać.

Problem , jakkolwiek użyteczny, nie jest sam w sobie nadmiernie interesujący. Dużo ciekawszy jest podobny do niego następujący problem:

Ten problem także jest -trudny; tym razem redukcję przeprowadzimy wprost z problemu . Niech  będzie instancją problemu . Dla każdej liczby  rysujemy na płaszczyźnie punkt  Zbadajmy, kiedy trzy różne tak otrzymane punkty  i   są współliniowe:

Okazuje się zatem, że punkty  i   są współliniowe wtedy i tylko wtedy, gdy liczby  stanowią rozwiązanie problemu . W ten sposób otrzymujemy żądaną redukcję problemu do problemu , pod warunkiem, że w tym pierwszym problemie interesują nas tylko trójki różnych liczb. To jednak możemy zapewnić (patrz zad. 2).

Wytrawny znawca geometrii natychmiast zauważy, że -trudność problemu implikuje bezpośrednio -trudność dualnego problemu:

Wróćmy teraz do problemu . Skoro reklamowaliśmy go jako przydatne narzędzie w geometrii, to najwyższy czas, aby podać kilka jego zastosowań. Wykazaliśmy już, że jest to problem -trudny. Jeśli zatem pokażemy redukcję z tego problemu do jakiegoś innego problemu geometrycznego działającą w czasie  to w ten sposób wykażemy, że ów drugi problem również jest -trudny. Pierwszym problemem z tej serii, który weźmiemy pod lupę, jest:

Rys. 2 Redukcja instancji problemu z rysunku 1 do instancji problemu .

Sprowadzimy problem do problemu . Tym razem redukcja będzie działać w czasie  gdyż wymagać będzie sortowania. Posortujemy punkty na każdej z prostych poziomych i połączymy pary kolejnych punktów odcinkami w taki sposób, żeby między każdymi dwoma kolejnymi odcinkami występował bardzo mały odstęp, o długości równej  Widzimy już, że przy tej konstrukcji prosta rozdzielająca zbiór odcinków, przechodząca przez trzy odstępy, odpowiada trójce punktów współliniowych należących do różnych prostych poziomych. Należy jeszcze zadbać o wyeliminowanie poziomych prostych rozdzielających. Wystarczy w tym celu umieścić dwa pionowe odcinki po bokach konstrukcji i ustawić je „na zakładkę” z odcinkami poziomymi, tak aby z kolei wyeliminować trywialne proste rozdzielające pionowe (Rys. 2). W ten sposób wykazaliśmy, że .

Kolejny przykład. Okazuje się, że problem możemy zredukować do następującego, całkiem naturalnego i mającego liczne zastosowania praktyczne problemu:

Redukcja jest tutaj podobna jak poprzednio. Przeszkodami będą odcinki poziome z wcześniejszej redukcji. Robota umieścimy poniżej całej konstrukcji, a jego celem będzie przedostanie się powyżej konstrukcji. Sam robot będzie na tyle długi, żeby nie mógł przedostać się na drugą stronę inaczej niż tylko przez trzy odstępy naraz. Należy jeszcze zadbać, aby robot nie mógł ominąć całej konstrukcji bokiem. W tym celu trzeba poniżej i powyżej konstrukcji zbudować „klatki” uniemożliwiające ucieczkę robota do „nieskończoności”. W ten sposób otrzymujemy wniosek, że .

To, co przedstawiliśmy do tej pory, to tylko niewielka grupa znanych problemów -trudnych. Dla Niestrudzonych Czytelników mamy w zanadrzu jeszcze kilka innych takich problemów – tym razem już dowody pominiemy. Zacznijmy od jeszcze jednego pomocniczego problemu -trudnego:

Problem ten można zredukować do każdego z następujących zagadnień typu :