Теория сложности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сложность по памяти, классы PS, L, NL, coNL)
м (Интерактивные протоколы)
Строка 54: Строка 54:
 
*[[Теорема Шамира]]
 
*[[Теорема Шамира]]
 
*[[Семейство универсальных попарно независимых хеш-функций]]
 
*[[Семейство универсальных попарно независимых хеш-функций]]
*[[Протокол Голдвассера-Сипсера для оценки размера множества]]
+
*[[Протокол Голдвассер-Сипсера для оценки размера множества]]
  
 
=== Probabilistically checkable proofs ===
 
=== Probabilistically checkable proofs ===

Версия 13:12, 19 июня 2013

Эта статья находится в разработке!

Детерминированные и недетерминированные вычисления, сложность по времени и по памяти

Классы P и NP, NP-полнота

Сложность по памяти, классы PS, L, NL, coNL

Полиномиальная иерархия

Схемная сложность

Вероятностные сложностные классы

Интерактивные протоколы

Probabilistically checkable proofs



Вот сюда можно подсматривать, но злоупотреблять не рекомендуется.