Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/~anromash/courses/cc-exercises-444.pdf Дата изменения: Fri Apr 26 11:52:18 2013 Дата индексирования: Fri Feb 28 00:08:57 2014 Кодировка: Поисковые слова: m 5

. , andrei.romashchenko@gmail.com 25 2013 . 444. 1. , EQ(a, b) = 1, a = b, 0, a = b

() n + 1 () n 2 log 2 + 1. = 1/10000 ( ). n ? n 100 ? 106 ? 2. a 1, . . . , 2n b . , ; , GT(a, b) = 1, a b, 0, a < b.

, n + 1 ( n + 1 , GT ). 3. A {1, . . . , n}, B {1, . . . , n}. , ; , DISJ(A, B ) = 1, A B = , 0, .

, n+1 : (A, B ), B = {1, . . . , n} \ A. , . 4. A {1, . . . , 2n }, B {1, . . . , n}. A B . () 2n.


() 3 n + c c, 2 n. () . ? 5. GT 2 O(log2 n), (a, b) 0,99. 6. , . "" : , ( ). . EQ(a, b) 1 8 (a, b) 1/100. : ! n. 7. () GT 2 O(log n · log log n), (a, b) 0,99. () O(log n). 8. . 4n n () , 2n+1 C2n 4n . n : (1 + 1)2n ; , C2n m C2n . (n+1)·(n+2)·...·(2n) n . () , C2n = 1·2·...·n () , p n + 1 2n ( n ) C2n . () , 1 k 4k . : (), () n = k , k , k , . . . 248 () , p 2n/3 n ( ( · ) (n+1)·1·n+2)n...·(2n) ( 2·...· n , C2n ). () , p 2n 2n/3 ( ( · ) (n+1)·1·n+2)n...·(2n) 1. : 2·...· , p ; . , p2 -


. () , p 1 2n ( · n C2n = (n+1)·1·n+2)n...·(2n) logp (2n). : , 2·...· p, p2 , p3 , .. , p . () , n + 1 2n . (-) (), 2 n C2n 4 3 n · (2n) 2n . , () n (, n > 10000). () , n p, n < p 2n. : () n 10000.

.
1. .
[1] . . " ". , 2012. [2] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press. 1998. [3] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press. 2009. ( , . http://www.cs.princeton.edu/theory/complexity/)

2. : .
[4] Michael Sipser. Introduction to the theory of computation. Course Technology, 2005. [5] . . , , 2006


3. : .
[6] . , . , . . : . 1- , , 2000. [7] Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms. 3rd edition. MIT Press, 2009. [8] . : . 2- , .: , 2004. ( , . http://www.mccme.ru/free-books/)

4. .
[9] . . . , 6, 1992. [10] . . . , 6, 1994. [11] . . . , 4, 1998. [12] . . . . .: , 2006.