### Wymagania (prerequisites)
* Jezyki formalne i zlozonosc obliczeniowa (konieczne)
* Algorytmy aproksymacyjne (zalecane)
* Zlozonosc obliczeniowa (moze troche pomoc)
### Opis (description)
O niektorych problemach od dawna wiadomo, ze sa NP-trudne, natomiast calkiem
niedawno pokazano iz rownie trudno jest znalezc ich przyblizone rozwiazania.
Dobrym przykladem jest 3-SAT, a dokladniej jego wersja optymalizacyjna
MAX-3-Sat, ktora pyta o wartosciowanie spelniajace mozliwie najwieksza liczbe
klauzul. Podczas gdy losowe wartosciowanie spelnia mniej wiecej 7/8 sposrod
nich, okazuje sie, ze rozroznienie pomiedzy formulami spelnialnymi oraz takimi
gdzie spelnic mozna jedynie 7/8 sposrod klauzul jest NP-trudne. To odkrycie ma
rowniez ciekawe konsekwencje wykraczajace poza teorie aproksymacji.
Omawiane wyniki z pewnoscia nie beda latwe i oczywiste, ale postaramy sie
powoli i systematycznie omowic najwazniejsze zagadnienia w tym temacie.
### Program (program)
Lagodne wprowadzenie:
* weak vs. strong NP-hardness
* APX-hardness
A potem juz bardzo konkretnie:
* the PCP theorem and consequences
* Unique Games Conjecture and consequences
