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