Złamanie niedeterminizmu problemów NP-zupełnych – przyszłość modelowania matematycznego i obliczeń równoległych

Pojęcie niedeterminizmu w algorytmice jest związane z powszechnie akceptowanym modelem obliczeń – maszyną Turinga. Potraktowanie problemów jako obiektów pozwoliło opisywać i analizować je metodami matematycznymi. Efektem takich badań, będących domeną teorii złożoności, jest szereg rezultatów udowodnionych, bądź będących hipotezami, ale także wiele pytań pozostających na dziś bez odpowiedzi. Do niewątpliwych osiągnięć teorii złożoności należy odkrycie klasyfikacji problemów wg kryterium trudności obliczeniowej. W uszeregowaniu tym istotną rolę odgrywa tytułowy niedeterminizm, będąc przy tym źródłem porażek teorii złożoności. Narracja walki odzwierciedla zmagania z fundamentalną kwestią P versus NP - pytaniem o charakter relacji między klasami problemów praktycznie rozwiązywalnych i problemów kwalifikowanych do trudnych.

Pozostające ciągle aktualnym pytanie o znaczenie obliczeń oraz naturę i ograniczenia algorytmów, prowokuje potrzebę refleksji nad statusem badań w tym zakresie. Przede wszystkim warto podjąć próbę określenia przyczyn niepowodzeń, a w kontekście kwestii P v NP, próbę określenia przyszłości informatyki w możliwej przecież erze post-niedeterministycznej.

Przedstawione w prezentacji, oparte o nowe modele, szkice koncepcji i rozwiązań kilku wybranych problemów, o spektakularnym znaczeniu dla przyszłości zastosowań informatyki – problemu spełnialności SAT, szczególnego przypadku problemu faktoryzacji mult(n), problemu nwd(a,b) i problemu pierwszości primes – mogą stanowić dobry przyczynek do takiej dyskusji, do której zaproszeniem jest tytuł prezentacji.

Szczegóły jednego z tematów prezentacji (fragmenty przygotowywanej książki):