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

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

Date:

Thursday, June 19, 2014 - 13:00

Abstract:

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