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

Материал из Викиконспекты
Версия от 18:18, 24 мая 2010; 192.168.0.2 (обсуждение)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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