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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Можно использовать любое эффективно вычислимое семейство 2-универсальных хеш-функций, а н…»)
 
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
Можно использовать любое эффективно вычислимое семейство 2-универсальных хеш-функций, а не только взятие по модулю. Кажется, что выделение такой абстракции будет сильно упрощать доказательство. Также можно будет заметить, что достаточно всего лишь O(n) формул.
+
Можно использовать любое эффективно вычислимое семейство 2-универсальных хеш-функций, а не только взятие по модулю. Кажется, что выделение такой абстракции будет сильно упрощать доказательство. Также можно будет заметить, что достаточно всего лишь O(n) формул. "Хорошее доказательство" можно найти [[http://www.cs.berkeley.edu/~luca/cs278-02/notes/lecture07b.ps|здесь]] или [[http://www.cs.princeton.edu/theory/complexity/countchap.pdf|здесь]]

Текущая версия на 18:18, 24 мая 2010

Можно использовать любое эффективно вычислимое семейство 2-универсальных хеш-функций, а не только взятие по модулю. Кажется, что выделение такой абстракции будет сильно упрощать доказательство. Также можно будет заметить, что достаточно всего лишь O(n) формул. "Хорошее доказательство" можно найти [[1]] или [[2]]