Granice algorytmów, czyli czego komputer nigdy nie zrobi

Czy istnieją problemy, których żaden komputer nigdy nie rozwiąże? A może są zadania, które, mimo że da się rozwiązać, to zawsze będą wymagały dużo czasu?

Podczas wykładu uczestnicy poznają dwa z najbardziej zaskakujących odkryć współczesnej informatyki teoretycznej. Najpierw zobaczymy, że istnieją pytania, na które nie potrafi odpowiedzieć żaden program, niezależnie od mocy komputera czy sprytu programisty. Następnie przejdziemy do problemów, które możemy rozwiązywać, ale prawdopodobnie zawsze będą wymagały ogromnych obliczeń. W ten sposób dotrzemy do słynnego problemu P vs NP, jednego z siedmiu Problemów Milenijnych.