О сложности задачи выполнимости схемы

Speaker: 
Иван Михайлин
Date: 
Thursday, June 19, 2014 - 13:00
Place: 
ПОМИ, ауд. 203
Abstract: 

В докладе будет доказано, что из разумных предположений на схемную сложность NP-полных задач следует, что любой полиномиальный алгоритм с односторонней ошибкой для Circuit-SAT будет давать очень маленькую вероятность успеха.