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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Теорема Валианта-Вазирани (Valiant–Vazirani) является клевым результатом в теории вычислимости. …»)
 
Строка 1: Строка 1:
Теорема Валианта-Вазирани (Valiant–Vazirani) является клевым результатом в теории вычислимости.
+
Теорема Валианта-Вазирани (Valiant–Vazirani) является клевым результатом в теории сложности.
  
<ref>{{cite journal |last1=[[Leslie G. Valiant|Valiant, Leslie G.]]|last2=[[Vijay Vazirani|Vazirani, Vijay V.]]|year=1986 |title=NP is as easy as detecting unique solutions |journal=Theoretical Computer Science |publisher=North-Holland |volume=47 |issue= |pages=85–93 |url=http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf |doi=10.1016/0304-3975(86)90135-0 |first1=L }}</ref>
 
  
==References==
+
 
{{reflist}}
+
==Внешние ссылки==
 +
 
 +
[http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions]
 +
 
 +
[http://logic.pdmi.ras.ru/~hirsch/students/complexity1/lecture7.pdf Лекция Э.А.Гирша]

Версия 09:52, 3 мая 2010

Теорема Валианта-Вазирани (Valiant–Vazirani) является клевым результатом в теории сложности.


Внешние ссылки

Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions

Лекция Э.А.Гирша