Теорема Валианта-Вазирани — различия между версиями
Ulyantsev (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | Теорема Валианта-Вазирани (Valiant–Vazirani theorem) является клевым результатом в теории сложности. | + | '''Теорема Валианта-Вазирани''' (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности. |
| + | ===Формулировка теоремы=== | ||
| + | |||
| + | Если язык '''[[USAT]]''' принадлежит классу '''[[P]]''', то классы языков '''[[NP]]''' и '''[[RP]]''' совпадают. | ||
| + | |||
| + | ===Доказательство теоремы=== | ||
