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