Zacząłem się pewnego razu zastanawiać, czy między nauką, a religią nie ma silnych powiązań, a konkretniej - czy można wyprowadzić pewne izomorfizmy między problemami z teizmu, a problemami z matematyki.

Ten post jest raczej satyryczny i filozoficzny niż merytoryczny. Zachęcam do czytania z przymrużeniem oka.

Czy Bóg istnieje? Czy P = NP?

Te dwa pytanie są z goła bardzo odmienne. Przede wszystkim dotyczą różnych tematów. Jednak można znaleźć między nimi pewne analogie.

Ponieważ część czytelników może nie wiedzieć czym są P i NP albo kim jest Bóg, to w pierwszej sekcji przedstawię ich nieformalne definicje. Następnie w drugiej sekcji określę podobieństwa tych dwóch problemów, a w sekcji trzeciej będę spekulował co się stanie, gdy znajdziemy odpowiedź na te pytania.

Od razu zaznaczę, że z odpowiedzi na jedno z tych pytań nie dostaniemy odpowiedzi na drugie, a dowód tego lematu zostawię czytelnikowi jako ćwiczenie.

Definicje

Zacznę od definicji problemu P = NP jako że jest to bardziej ścisła definicja.

Literą P oznaczamy zbiór problemów, na które możemy odpowiedzieć uruchamiając pewien algorytm, który działa w czasie wielomianowym. Z pojęciem wielomianu czytelnik mógł się spotkać w liceum. Chodzi o to, że istnieje jakiś wielomian W(n) dla algorytmu, taki, że jeśli dane do problemu mają długość n, to program będzie działał około W(n) czasu.

Np. Niech W(n) = n² i mamy algorytm nieefektywnego sortowania listy. Dla listy długości 5, dostaniemy odpowiedź po 25 jednostkach czasu, a dla listy o 20 elementach, po 400 jednostkach czasu.

Natomiast NP to zbiór takich problemów, które można rozwiązać algorytmem działającym w czasie wielomianowym, jeśli dodatkowo mamy dostępną wyrocznię, która nam podpowiada jak ten algorytm na działać i zawsze podpowiada dobrze. Jest to trochę bajkowe, ale ścisła definicja jest znacznie bardziej skomplikowana i niekoniecznie potrzebna do zrozumienia problemu.

Problem brzmi: wiemy, że każdy problem, który jest w P jest również w NP, ale nie wiemy czy wszystkie problemy w NP są w P i tylko nie umiemy wymyślić lepszych algorytmów. Czy P = NP?

Przejdę teraz do definicji Boga. W wielu kulturach wykształciły się wierzenia w istotę, która ma pełną władzę nad naszym światem, w szczególności go stworzyła, a jednocześnie jest niematerialna i ma bezkresny zasięg swojej mocy.

Bogom (różnych religii) oddaje się cześć, modli się o przychylność, a także stara się być dobrym człowiekiem, aby uniknąć kary bożej (tu są pewne wariancje).

Ciężko jest potwierdzić istnienie Boga, jako że jego obecność jest nie wykrywalna przy pomocy eksperymentów naukowych (niematerialność). Jednakże ludzie obserwowali niewyjaśnione zjawiska (cuda), które przypisywane są właśnie zasłudze Boga. Brak dowodu za, nie jest dowodem przeciw, może nie umiemy znaleźć właściwego eksperymentu.

Podobieństwa problemów

Oba problemy opierają się na zjawisku posiadania zbyt małej wiedzy, aby za pomocą logiki zaprezentować mniej lub bardziej formalny dowód.

Biorąc problem NP-zupełny nie wiemy czy istnieje dla niego algorytm w P. Każdy kto dotychczas próbował ten problem rozwiązać, nie był w stanie wymyślić rozwiązania w P. Co nie znaczy że go nie ma.

I tak samo jest z Bogiem. To że ktoś zaobserwował cud, nie znaczy że nie ma fizycznego wytłumaczenia takiego zjawiska, być może w oparciu o wiedzę, której nie posiadamy.

Można by się posunąć do stwierdzenia, że wyjaśnialne przez naukę zjawiska można porównać do zbioru P, a wszystkie możliwe zjawiska do zbioru NP.

Istnieje możliwość, że P = NP, a zarazem istnieje możliwość, że wszystkie zjawiska na świecie mają wytłumaczenie w nauce. A to by oznaczało, że Bóg również jest bytem mającym podłoże w fizyce.

Co jeśli znajdziemy odpowiedź?

Jeśli P != NP to w zasadzie nic się nie dzieje. I tak większość informatyków się skłania ku temu.

Jeśli P = NP to mamy lekki problem. Nasza obecna kryptografia opiera się właśnie na NP-zupełnych problemach i nagle okaże się, że każdy szyfr można złamać w czasie wielomianowym.

Z Bogiem będzie trochę trudniej. Załóżmy, że Bóg istnieje. Czy któraś religia dobrze go opisała? Czy ludzie zaakceptują oblicze Boga jakie zostanie zaobserwowane? Czy będziemy się w stanie komunikować z Bogiem? Jest więcej nowych pytań, niż odpowiedzi.

Albo okaże się, że Bóg nie istnieje, albo że jego istnienie jest warunkowane w nauce, więc nie jest w stanie robić cudów ponad możliwości fizycznego świata. Czy ludzie którzy dotychczas byli religijni zaakceptują naukowe dowody?

Podsumowanie

Jak widać otwarte problemy są dość skomplikowane. W przypadku problemu P = NP skutki znalezienia rozwiązania są znacznie bardziej określone, niż w przypadku problemu Boga. Myślę, że problem Boga będzie długo jeszcze pozostawał bez odpowiedzi, po tym jak ktoś pokaże czy P = NP. W szczególności, pojawienie się komputerów kwantowych wróży nam zmianę podejścia do algorytmiki, a wiele problemów, które były obliczeniowo trudne, zostanie rozwiązanych.