Co bylo na wykladzie ?

WPROWADZENIE
Trudnosc obliczeniowa -- od rozumienia empirycznego do modelu matematycznego.
Powszechnosc problemow trudnych obliczeniowo "w przyrodzie".
W miare przyspieszania dzialania komputerow znaczenie szybkich algorytmow rosnie -- nie maleje.
Paradokslana natura pojecia zlozonosci: nadmiar struktury (skomplikowanie) lub przeciwnie -- jej brak (losowosc).
Podstatowe pojecia: problemy decyzyjne, zlozonosc czasowa i pamieciowa maszyny Turinga, zlozonosc problemu decyzyjnego.
Twierdzenie Sipsera o tym, ze maszyne Turinga dzialajaca w pamieci ograniczonej przez funkcje liczbowa S(n) mozna
symulowac maszyna dzialajaca w tej samej pamieci, ktora ponadto zatrzymuje sie dla kazdych danych.

MASZYNA UNIWERSALNA I KONSTRUKCJE PRZEKATNIOWE
Przypomnienie: uniwersalna maszyna Turinga, nierozstrzygalnosc jezyka przekatniowego i w konsekwencji problemu stopu.
Twierdzenie o hierarchii pamieciowej: jesli S_2 jest funkcja pamieciowo konstruowalna niemniejsza od log n
i lim sup S_2 (n) / S_1 (n) jest nieskonczonosc, to istnieje jezyk akceptowany w pamieci S_2 (n), ale nie w pamieci S_1 (n).
Analogiczne twierdzenie zachodzi dla zlozonosci czasowej.

CZAS I PRZESTRZEN JAKO MIARY ZLOZONOSCI
Zaleznosc pomiedzy pamieciowa i czasowa zlozonoscia problemu, hipotezy otwarte.
``Czy z faktu, ze w ogolnosci algorytm uzywa wykladniczo wiecej czasu niz pamieci, wynika, ze
zlozonosc pamieciowa problemu jest zawsze logartymicznie mniejsza od czasowej ?'' (Nie wiemy.)
Podstawowe klasy deterministycznej zlozonosci obliczeniowej: L, P, PSPACE, EXPTIME.

OBLICZENIE JAKO GRA -- ALTERNACJA
Obliczenie jako gra, w ktorej "protagonista" chce wykazac, ze w chwili t, w komorce o numerze i
znajduje sie symbol A (byc moze stan).
Pojecie alternujacej maszyny Turinga, alternujace klasy zlozonosci.

Twierdzenie (Chandra-Kozen-Stockmeyer)

Dla funkcji f co najmniej liniowej i konstruowalnej,

ATIME (f(n)) zawarte w DSPACE (f(n)) zawarte w ATIME (f(n)^2 )

DTIME (f(n)) = ASPACE (log f(n)).

Pierwsza czesc dowodu: "alternowanie".
Druga czesc dowodu: determinizowanie maszyn alternujacych poprzez przeszukiwanie grafu konfiguracji, dwie metody - ``trade off'' oszczednosci czasu lub pamieci.

OBWODY LOGICZNE
Obwody logiczne - niejednorodny model obliczen (dla kazdego n, obwod C_n rozwiazuje problem
ograniczony do wejsc dlugosci n).
Uwaga: prosty rachunek pokazuje, ze wiekszosc funkcji wymaga obwodow o wykladniczym rozmiarze, ale
nie sa znane *przyklady* takich funkcji.
Ograniczamy rozwazania do sytuacji, gdy rozmiar C_n jest wielomianowy wzgledem n: klasa P/poly.
Charakteryzacja: problem decyzyjny jest rozwiazywalny w czasie wielomianowym (tzn. jest w P)
wtedy i tylko wtedy, gdy jest rozpozanwany przez ciag obwodow C_n rozmiaru wielomianowego,
ktory to ciag mozna wygenerowac w pamieci logarytmicznej.
Definiowanie jezyka L poprzez relacje R(x,y), "y jest swiadkiem dla x"
--- prawdziwym gdy R(x,y) <==> L(x),
--- "obrony" gdy R(x,y), "oskarzenia", gdy nie R(x,y).
Klasy zlozonosci definiowalne przez relacje: NP (swiadkowie "obrony" tylko prawdziwi),
BPP (co najmniej 3/4 prawdziwych swiadkow ktoregokolwiek rodzaju).
Twierdzenie o sile obwodow logicznych:

BPP zawiera sie w P/poly

(a wiec, derandomizacja, ale niejednorodna). W dowodzie - Lemat "o demokracji".

REDUKCJE POMIEDZY PROBLEMAMI -- ZUPELNOSC
Jeszcze o rozwiazywaniu problemow zadanych przez relacje, przyklady.
Algorytm wielomianowy odrozniajacy liczby pierwsze od zlozonych *nie* implikuje algorytmu
znajdujacego dzielnik, natomiast jakikolwiek algorytm rozstrzygajacy egzystencjalnie
problem SAT mozna poprawic do algorytmu znajdujacego wartosciowanie.
Redukcje funkcyjne - w sensie Karpa (obliczalne w pamieci logarytmicznej)
i w sensie Levina (transformujace rowniez swiadkow - w obie strony).
Maszyny z wyroczniami i redukcje w sensie Turinga.
Problemy zupelne. NP-zupelnosc (w sensie Levina) problemu spelnialnosci obwodow logicznych.
Dalsze redukcje: NP-zupelnosc (w sensie Levina) problemu spelnialnosci formul rachunku zdan,
formul w postaci CNF (koniunkcja alternatyw) i 3-CNF, czyli Twierdzenie Cooka.
Redukcja w sensie Turinga problemu funkcyjnego Search (R) do problemu
egzystencjalnego L(R), o ile tylko relacja R jest wielomianowa, a L(R) jest
problemem zupelnym w sensie Karpa.

Problem Levina: gdyby P=NP mialo dowod niekonstruktywny --
konstrukcja semi-algorytmu, ktory rozwiazuje w czasie wielomianowym
problem SAT (w przypadkach pozytywnych), o ile tylko istnieje jakis
(byc moze nieznany) algorytm o tej wlasnosci.

OGRANICZENIA DOLNE DLA OBWODOW MONOTONICZNYCH
Hipoteza, ze istnieja jezyki NP, ktorych nie mozna rozpoznawac ciagami obwodow
wielomianowego rozmiaru jest silniejsza niz P=/=NP.
Twierdzenie Razborowa . Jezyka CLIQUE nie mozna rozpoznawac zadnym
ciagiem wielomianowych obwodow monotonicznych.
Notatki (napisal Rafal Wojtczuk).

OGRANICZENIA DOLNE DLA OBWODOW LOGICZNYCH
Twierdzenie (Furst, Saxe, Sipser) . Jezyka (regularnego) PARITY, zlozonego ze slow 0-1,
gdzie 1 wystepuje parzysta liczbe razy, nie mozna rozpoznac przy pomocy ciagu obwodow
logicznych o wielomianowym rozmiarze i stalej glebokosci.

Twierdzenie to jest jednym z najsilniejszych dolnych ograniczen,
jakie pokazano do tej pory w teorii zlozonosci.

Dowod przez indukcje na (hipotetyczna) glebokosc obwodu.
Dla glebokosci 2 jest to latwe cwiczenie. Trudnym krokiem dowodu
jest lemat kombinatoryczny, ang. Switching Lemma , stwierdzajacy, ze
glebokosc obwodu mozna zmniejszyc dokonujac podstawienia wartosci
logicznych na niektore zmienne, a nastepnie "przestawiajac" dwa dolne poziomy,
przy czym wzrost liczby bramek jest asymptotycznie tylko wielomianowy.

Ciag dalszy nastapi.