Теорема Валианта-Вазирани (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.
Если язык USAT принадлежит классу P, то классы языков NP и RP совпадают.
Оригинальная статья 1986 года - Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions
Лекция Э.А.Гирша
