Теорема Валианта-Вазирани

Теорема Валианта-Вазирани (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.

Формулировка теоремы

Если язык USAT принадлежит классу P, то классы языков NP и RP совпадают.

Доказательство теоремы

Внешние ссылки

Оригинальная статья 1986 года - Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions

Лекция Э.А.Гирша