Problem NP-zupełny

Z Nonsensopedii, polskiej encyklopedii humoru

Problem NP-zupełny (Problem niezwykle-pracogenno-zupełny) – rodzinka wyjątkowo złośliwych, męczących i upierdliwych w rozwiązaniu problemów. Aktor grający zbira w trzecim odcinku Kojaka udowodnił, że jeżeli uda się rozwiązać jeden problem NP-zupełny w ludzkim czasie, to można też rozwiązać w tym czasie inne problemy z tej rodzinki.

Przykłady[edytuj • edytuj kod]

  • Problem odkurzenia wszechświata – należy odkurzyć cały wszechświat, co z uwagi na zanieczyszczenia i oceany bywa kłopotliwe, a następnie zawartość worka wyrzucić na zewnątrz.
  • Problem czasu reklamowego – należy obliczyć średni czas trwania bloku reklamowego na Polsacie w danym miesiącu.
  • Problem sznurka do snopowiązałki w PRL-u – sznurek ten, pomimo dużej produkcji i braku eksportu, nie istniał w praktyce, a jego brak wymagał zastosowania domowych środków zaradczych.

Algorytm rozwiązujący problemy w czasie znośnym[edytuj • edytuj kod]

Wynaleziony pod koniec 2007 roku algorytm rozwiązujący problemy NP-zupełne w czasie znośnym, tj. na przykład przed wybudowaniem planowanych w Polsce autostrad.

Opis algorytmu[edytuj • edytuj kod]

Algorytm ten jest bardzo prosty, i opiera się na podstawowych własnościach matematycznych.

Aby wykonać algorytm rozwiązujący problemy NP należy działać według niżej wymienionych punktów a wynik będzie poprawny/optymalny.

  1. Wprowadź dane instancji problemu do niedeterministycznej maszyny Turinga.
  2. Nie zapomnij wybrać z opcji zaawansowanych tryb „TURBO EXPERT”.
  3. Poczekaj pińćdziesiąt jednostek czasu, wykorzystując je pożytecznie, na przykład zmywając naczynia lub grając w CSa.
  4. Odczytaj wynik rozwiązanego problemu i odbierz milion dolarów za rozwiązanie milenijnego problemu.
  5. Ciesz się i żyj w dobrobycie.

Dowód poprawności algorytmu jest banalny i jest modyfikacją dowodu na nieskończoność liczb pierwszych. Nie rozumiesz? Nie przejmuj się, do Biedronki wszystkich przyjmują.