| What: | Lecture |
| When: | Thursday, 17 October 2013, 18:30–19:50 |
| Where: | ПОМИ РАН |
Две формулировки PCP-теоремы: NP-трудность GAP-3SAT и NP=PCP(log n, 1). Трудность приближения MAX3SAT. Детерминированный и недетерминированный конечные автоматы, регулярные выражения.
