Лаборатория алгоритмических методов

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

Дата:

Thursday, June 19, 2014 - 13:00

Аннотация:

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