Изменения
Нет описания правки
'''Теорема Валианта-Вазирани ''' (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.
===Формулировка теоремы===
Если язык '''[[USAT]]''' принадлежит классу '''[[P]]''', то классы языков '''[[NP]]''' и '''[[RP]]''' совпадают.
===Доказательство теоремы===
