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