Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2011/courses/sko11.pdf Дата изменения: Sun May 1 17:07:40 2011 Дата индексирования: Mon Feb 4 08:07:32 2013 Кодировка: Поисковые слова: п п п п п п п п п п п п п п п п п п п

. , ( ­ ) , , , .., , . : n- m- ? -- , , , . , 6 < 2m < 3n + 3 NP- (Matousek et al, http://arxiv.org/abs/math/0807.0336). , , . , NP- . `' (, , NP-) . `' : 3, , , . , . . . 1. K5 1, 2, 3, 4, 5, . , K5 . 2. , , K5 (12), , 1 2 345. 3. , , K5 (12) (13), , 1 2 345, 1 3 245. 4. , , K5 (12), (13) (14), , 1 2 345, 1 3 245. 1 4 235. 5. ... , .


( ) 1. . 1.1. 1- 2- (). 1.2. Rn . 1.3. . 1.4. . : . - Rn . 1.5. 2- . NP NP-. 1.6. (Matousek-Tancer-Wagner 2010). . 2. . 2.1. K5 . . 2.2. . . -. 2.3.* -. 3. . 3.1. R3 K5 . . 3.2.* 2- R3 3- (Jaco-Sedgwick 1998, Tonkonog 2010). 3.3. . . 3.4. --: Px1 x1 . 3.5. : Px1 x2 x1 , Px1 x2 x1 x2 . 3.6. 2- Pf , f . 3.7. Pf R3 : f ( ) = 0 . x x . 4. . 4.1. R4 6- . . 4.2. --. 4.3. R4 2- , . 4.4.* (Segal-Spiez-Skopenkov 1992, 1998).