Klasa złożoności "Interactive Proofs"

Prowadzący: Igor Hańczaruk

Czyli jakie problemy można rozwiązać, gdy bogini namagiri zsyła wielomianowe dowody
Zadania kwalifikacyjne
Kategorie: matematyka informatyka

Zapisz się

Opis

Załóżmy, że masz czarodzieja, który rzekomo potrafi rozwiązać jakiś problem matematyczny, ale rozumowanie które przeprowadza jest zbyt skomplikowane, byś móogła je zrozumieć w czasie wielomianowym. Na zajęciach zastanowimy się, czy prawdomówność czarodzieja da się sprawdzić, jeśli wystarczy nam prawie pewność.

Wizualizacja klasy IP

Następujący przykład będzie książkowy: Czarodziej twierdzi, że masz na sobie dwie różne skarpetki, Ty niestety nie rozróżniasz kolorów. Żeby go sprawdzić możesz je zdjąć, schować za plecami, z prawdopodobieństwem 1/2 przełożyć z ręki do ręki, a potem spytać czarodzieja która z nich jest która. Jeśli skarpetki są różne, to rozróżniający kolory czarodziej będzie w stanie odpowiadać za każdym razem poprawnie. Jeśli są takie same, to może co najwyżej strzelać, więc po n takich rundkach, nie machnie się ani razu z prawdopodobieństwem (1/2)^n (niskim)

Podczas warsztatów:

  • Zajrzymy do świata klas złożoności, powiemy sobie co nieco (to znaczy że jeszcze nie wiem co)
  • Ad co nieco: NP i coNP - czym są i dlaczego (raczej) nie są tym samym
  • Popatrzymy sobie na klasę IP, czyli takie problemy, których rozwiązanie można komuś sprzedać w wielomianowym czasie z wysokim prawdopodobieństwem poprawności
  • Bardzo możliwe, że poznamy również klasę AM - artur-merlin, czyli to samo, ale dodatkowo czarodziej musi znać wyniki wszystkich losowań sprawdzaczki
  • Poznamy zaskakujący wynik o wysokim znaczeniu filozoficznym, który mówi, że IP = PSPACE (PSPACE to problemy rozwiązywalne w wielomianowej pamięci)

Wymagania

Zajęcia nie wymagają wcześniejszej znajomości teorii złożoności obliczeniowej. Preliminaria związane z tematem powinny zostać pokryte przez zadania kwalifikacyjne. Oczekiwane jest jakieś ogólne zaplecze matematyczne.

Przydatne rzeczy

Tu się jeszcze coś pojawi. Generalnie warsztaty będą bazowały na rozdziale ósmym książki

Arora, Barak Computational Complexity: A Modern Approach

Którą można bez problemu znaleźć w pdfie.

Kontakt

Można pisać maile na igor.hanczaruk@gmail.com