Приближенное решение задач комбинаторной оптимизации: алгоритмы и трудность, осень 2016: Гипотеза Хота (UGC)

  • Published on
    26-Jan-2017

  • View
    55

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p> :</p><p> 10: (Unique Games Conjecture)</p><p>. </p><p>. ..</p><p>-, Computer Science Club, 2016</p><p>. ( ) 10: , CSclub, 2016 1 / 31</p></li><li><p>NP- </p><p>MAX-LCk(1, ) MAX-3LIN, MAX-3SAT</p><p>MAX-ULCk MAX-CUT, MAX-2SAT, MIN-VC</p><p> MAX-ULCk </p><p> ( , ),</p><p> :</p><p> , </p><p> .</p><p>. ( ) 10: , CSclub, 2016 2 / 31</p></li><li><p>NP- </p><p>MAX-LCk(1, ) MAX-3LIN, MAX-3SAT</p><p>MAX-ULCk MAX-CUT, MAX-2SAT, MIN-VC</p><p> MAX-ULCk </p><p> ( , ),</p><p> :</p><p> , </p><p> .</p><p>. ( ) 10: , CSclub, 2016 2 / 31</p></li><li><p>NP- </p><p>MAX-LCk(1, ) MAX-3LIN, MAX-3SAT</p><p>MAX-ULCk MAX-CUT, MAX-2SAT, MIN-VC</p><p> MAX-ULCk </p><p> ( , ),</p><p> :</p><p> , </p><p> .</p><p>. ( ) 10: , CSclub, 2016 2 / 31</p></li><li><p>NP- </p><p>MAX-LCk(1, ) MAX-3LIN, MAX-3SAT</p><p>MAX-ULCk MAX-CUT, MAX-2SAT, MIN-VC</p><p> MAX-ULCk </p><p> ( , ),</p><p> :</p><p> , </p><p> .</p><p>. ( ) 10: , CSclub, 2016 2 / 31</p></li><li><p> MAX-ULCk: ; V1 </p><p> ; , </p><p> e = (v1v2) e : , , e((v1)) = (v2). k .</p><p>: , </p><p>.</p><p> , UGC</p><p> &gt; 0 k , MAX-ULCk(1 , ) NP-.</p><p>. ( ) 10: , CSclub, 2016 3 / 31</p></li><li><p> MAX-ULCk: ; V1 </p><p> ; , </p><p> e = (v1v2) e : , , e((v1)) = (v2). k .</p><p>: , </p><p>.</p><p> , UGC</p><p> &gt; 0 k , MAX-ULCk(1 , ) NP-.</p><p>. ( ) 10: , CSclub, 2016 3 / 31</p></li><li><p>1 MAX-LC7(1, 1 ) NP-.2 k MAX-ULCk(1, 1 ) P.</p><p> : </p><p> , </p><p> , </p><p>.</p><p>- .</p><p>. ( ) 10: , CSclub, 2016 4 / 31</p></li><li><p>1 MAX-LC7(1, 1 ) NP-.2 k MAX-ULCk(1, 1 ) P.</p><p> : </p><p> , </p><p> , </p><p>.</p><p>- .</p><p>. ( ) 10: , CSclub, 2016 4 / 31</p></li><li><p>1 MAX-LC7(1, 1 ) NP-.2 k MAX-ULCk(1, 1 ) P.</p><p> : </p><p> , </p><p> , </p><p>.</p><p>- .</p><p>(u) = 1 (v) =? (u) = 1 uv (1) = 2, (v) = 2.</p><p>. ( ) 10: , CSclub, 2016 4 / 31</p></li><li><p>UGC- </p><p> UGC , , /2 &lt; &lt; &gt; 0 MAX-CUT((1 cos)/2 , / + ) NP-.</p><p>GW = min0</p></li><li><p>UGC- </p><p> UGC , , /2 &lt; &lt; &gt; 0 MAX-CUT((1 cos)/2 , / + ) NP-.</p><p>GW = min0</p></li><li><p> : PCP </p><p>MAX-ULCm(1 , ). : </p><p> fw .(, .)</p><p> 2 </p><p> . (, </p><p> .)</p><p> MAX-CUT.</p><p> :</p><p> . </p><p>, </p><p> .</p><p>. ( ) 10: , CSclub, 2016 6 / 31</p></li><li><p> : PCP </p><p>MAX-ULCm(1 , ). : </p><p> fw .(, .)</p><p> 2 </p><p> . (, </p><p> .)</p><p> MAX-CUT.</p><p> :</p><p> . </p><p>, </p><p> .</p><p>. ( ) 10: , CSclub, 2016 6 / 31</p></li><li><p> : PCP </p><p>MAX-ULCm(1 , ). : </p><p> fw .(, .)</p><p> 2 </p><p> . (, </p><p> .)</p><p> MAX-CUT.</p><p> :</p><p> . </p><p>, </p><p> .</p><p>. ( ) 10: , CSclub, 2016 6 / 31</p></li><li><p> : PCP </p><p>MAX-ULCm(1 , ). : </p><p> fw .(, .)</p><p> 2 </p><p> . (, </p><p> .)</p><p> MAX-CUT.</p><p> :</p><p> . </p><p>, </p><p> .</p><p>. ( ) 10: , CSclub, 2016 6 / 31</p></li><li><p> , </p><p> .</p><p>. ( ) 10: , CSclub, 2016 7 / 31</p></li><li><p> , </p><p> .</p><p>v</p><p>w</p><p>w</p><p>V W </p><p>fw ( x) = fv (x) = fw ( x).</p><p>(fw (x) )</p><p> , , - (v ,w), (v ,w ) :</p><p>((w)) = (v); ((w )) = (v),</p><p>. ( ) 10: , CSclub, 2016 7 / 31</p></li><li><p> , </p><p> .</p><p>v</p><p>w</p><p>w</p><p>V W </p><p>fw ( x) = fv (x) = fw ( x).</p><p>(fw (x) )</p><p> . </p><p> ( x).</p><p>. ( ) 10: , CSclub, 2016 7 / 31</p></li><li><p> PCP </p><p> , = cos, 1 &lt; &lt; 0.1 x {0, 1}m, x </p><p> N(x) ( (1 )/2).</p><p>2 v V .</p><p>3 w , w v( ).</p><p>4 fw ( x) fw ( x ) ,</p><p>fw ( x) 6= fw ( x ).</p><p> , - (v ,w), (v ,w ).</p><p>. ( ) 10: , CSclub, 2016 8 / 31</p></li><li><p> PCP </p><p> , = cos, 1 &lt; &lt; 0.1 x {0, 1}m, x </p><p> N(x) ( (1 )/2).</p><p>2 v V .</p><p>3 w , w v( ).</p><p>4 fw ( x) fw ( x ) ,</p><p>fw ( x) 6= fw ( x ).</p><p> , - (v ,w), (v ,w ).</p><p>. ( ) 10: , CSclub, 2016 8 / 31</p></li><li><p> PCP </p><p> , = cos, 1 &lt; &lt; 0.1 x {0, 1}m, x </p><p> N(x) ( (1 )/2).</p><p>2 v V .</p><p>3 w , w v( ).</p><p>4 fw ( x) fw ( x ) ,</p><p>fw ( x) 6= fw ( x ).</p><p> , - (v ,w), (v ,w ).</p><p>. ( ) 10: , CSclub, 2016 8 / 31</p></li><li><p> PCP </p><p> , = cos, 1 &lt; &lt; 0.1 x {0, 1}m, x </p><p> N(x) ( (1 )/2).</p><p>2 v V .</p><p>3 w , w v( ).</p><p>4 fw ( x) fw ( x ) ,</p><p>fw ( x) 6= fw ( x ).</p><p> , - (v ,w), (v ,w ).</p><p>. ( ) 10: , CSclub, 2016 8 / 31</p></li><li><p> PCP </p><p> , = cos, 1 &lt; &lt; 0.1 x {0, 1}m, x </p><p> N(x) ( (1 )/2).</p><p>2 v V .</p><p>3 w , w v( ).</p><p>4 fw ( x) fw ( x ) ,</p><p>fw ( x) 6= fw ( x ).</p><p> , - (v ,w), (v ,w ).</p><p>. ( ) 10: , CSclub, 2016 8 / 31</p></li><li><p> &gt; 2. , 1 , , </p><p>1 2 .</p><p> C , , , = </p><p>2</p><p>8C 62:</p><p> , </p><p>arccos </p><p>+ .</p><p>. ( ) 10: , CSclub, 2016 9 / 31</p></li><li><p> &gt; 2. , 1 , , </p><p>1 2 .</p><p> C , , , = </p><p>2</p><p>8C 62:</p><p> , </p><p>arccos </p><p>+ .</p><p>. ( ) 10: , CSclub, 2016 9 / 31</p></li><li><p> UGC , , /2 &lt; &lt; &gt; 0 MAX-CUT((1 cos)/2 , / + ) NP-.</p><p> =2</p><p>8C</p><p>( , C ) m , NP- MAX-ULCm(1 , ). ( , m .) </p><p>MAX-ULCm(1 , ) 6p MAX-CUT((1 )/2 , arccos / + )</p><p>. ( ) 10: , CSclub, 2016 10 / 31</p></li><li><p> UGC , , /2 &lt; &lt; &gt; 0 MAX-CUT((1 cos)/2 , / + ) NP-.</p><p> =2</p><p>8C</p><p>( , C ) m , NP- MAX-ULCm(1 , ). ( , m .) </p><p>MAX-ULCm(1 , ) 6p MAX-CUT((1 )/2 , arccos / + )</p><p>. ( ) 10: , CSclub, 2016 10 / 31</p></li><li><p> UGC , , /2 &lt; &lt; &gt; 0 MAX-CUT((1 cos)/2 , / + ) NP-.</p><p> =2</p><p>8C</p><p>( , C ) m , NP- MAX-ULCm(1 , ). ( , m .) </p><p>MAX-ULCm(1 , ) 6p MAX-CUT((1 )/2 , arccos / + )</p><p>. ( ) 10: , CSclub, 2016 10 / 31</p></li><li><p> G (V ,W , ) 7 H MAX-CUT.</p><p> H: (w , y), w W , y {0, 1}m. H: ((w , y), (w , y )), V G v w , w . (w , y), (w , y ) . , y = x , y = x , , (v ,w), (v ,w ) G .</p><p> H w G fw , , (w , x). : fw H.</p><p>. ( ) 10: , CSclub, 2016 11 / 31</p></li><li><p> G (V ,W , ) 7 H MAX-CUT.</p><p> H: (w , y), w W , y {0, 1}m. H: ((w , y), (w , y )), V G v w , w . (w , y), (w , y ) . , y = x , y = x , , (v ,w), (v ,w ) G .</p><p> H w G fw , , (w , x). : fw H.</p><p>. ( ) 10: , CSclub, 2016 11 / 31</p></li><li><p> G (V ,W , ) 7 H MAX-CUT.</p><p> H: (w , y), w W , y {0, 1}m. H: ((w , y), (w , y )), V G v w , w . (w , y), (w , y ) . , y = x , y = x , , (v ,w), (v ,w ) G .</p><p> H w G fw , , (w , x). : fw H.</p><p>. ( ) 10: , CSclub, 2016 11 / 31</p></li><li><p> G , 1 , , (1 )/2 . , , </p><p> .</p><p> G , , </p><p> ( H) ( ) arccos / + .</p><p>. ( ) 10: , CSclub, 2016 12 / 31</p></li><li><p> G , 1 , , (1 )/2 . , , </p><p> .</p><p> G , , </p><p> ( H) ( ) arccos / + .</p><p>. ( ) 10: , CSclub, 2016 12 / 31</p></li><li><p> : (V W ) [m] (1 ) . : fw (w). , </p><p> .</p><p> 1 2 (v ,w), (v ,w ). , ((w)) = (v) = ((w )).</p><p> : x((w)) = fw ( x) 6= fw ( x ) = (x )((w )): x(v) 6= (x )(v)</p><p>: Prx N(x)</p><p>[x(v) 6= (x )(v)] =1</p><p>2(1 ).</p><p>(1 2) 1 2</p><p>=1 2 2 1 </p><p>2&gt;</p><p>1 2 , ( &gt; 2).</p><p>. ( ) 10: , CSclub, 2016 13 / 31</p></li><li><p> : (V W ) [m] (1 ) . : fw (w). , </p><p> .</p><p> 1 2 (v ,w), (v ,w ). , ((w)) = (v) = ((w )).</p><p> : x((w)) = fw ( x) 6= fw ( x ) = (x )((w )): x(v) 6= (x )(v)</p><p>: Prx N(x)</p><p>[x(v) 6= (x )(v)] =1</p><p>2(1 ).</p><p>(1 2) 1 2</p><p>=1 2 2 1 </p><p>2&gt;</p><p>1 2 , ( &gt; 2).</p><p>. ( ) 10: , CSclub, 2016 13 / 31</p></li><li><p> : (V W ) [m] (1 ) . : fw (w). , </p><p> .</p><p> 1 2 (v ,w), (v ,w ). , ((w)) = (v) = ((w )).</p><p> : x((w)) = fw ( x) 6= fw ( x ) = (x )((w )): x(v) 6= (x )(v)</p><p>: Prx N(x)</p><p>[x(v) 6= (x )(v)] =1</p><p>2(1 ).</p><p>(1 2) 1 2</p><p>=1 2 2 1 </p><p>2&gt;</p><p>1 2 , ( &gt; 2).</p><p>. ( ) 10: , CSclub, 2016 13 / 31</p></li><li><p> : (V W ) [m] (1 ) . : fw (w). , </p><p> .</p><p> 1 2 (v ,w), (v ,w ). , ((w)) = (v) = ((w )).</p><p> : x((w)) = fw ( x) 6= fw ( x ) = (x )((w )): x(v) 6= (x )(v)</p><p>: Prx N(x)</p><p>[x(v) 6= (x )(v)] =1</p><p>2(1 ).</p><p>(1 2) 1 2</p><p>=1 2 2 1 </p><p>2&gt;</p><p>1 2 , ( &gt; 2).</p><p>. ( ) 10: , CSclub, 2016 13 / 31</p></li><li><p> ( )</p><p> . , </p><p> . ,</p><p> .</p><p> , .</p><p> , </p><p> .</p><p> ,</p><p> fw , gv .</p><p>. ( ) 10: , CSclub, 2016 14 / 31</p></li><li><p> ( )</p><p> . , </p><p> . ,</p><p> .</p><p> , .</p><p> , </p><p> .</p><p> ,</p><p> fw , gv .</p><p>. ( ) 10: , CSclub, 2016 14 / 31</p></li><li><p> ( )</p><p> . , </p><p> . ,</p><p> .</p><p> , .</p><p> , </p><p> .</p><p> ,</p><p> fw , gv .</p><p>. ( ) 10: , CSclub, 2016 14 / 31</p></li><li><p> : S(f ) = ExU</p><p>yN(x)</p><p>[f (x) f (y)], f : {+1,1}n R.</p><p> f : {+1,1}n {+1,1}</p><p>S(f ) = 1 2 PrxU</p><p>yN(x)</p><p>[f (x) 6= f (y)].</p><p>. ( ) 10: , CSclub, 2016 15 / 31</p></li><li><p> : S(f ) = ExU</p><p>yN(x)</p><p>[f (x) f (y)], f : {+1,1}n R.</p><p> f : {+1,1}n {+1,1}</p><p>S(f ) = 1 2 PrxU</p><p>yN(x)</p><p>[f (x) 6= f (y)].</p><p>. ( ) 10: , CSclub, 2016 15 / 31</p></li><li><p>S(f ) = f ,Tf =S[n]</p><p>f (S)2 |S |(Tf (x) = E</p><p>yN(x)[f (y)]</p><p>).</p><p> Tf (S) = |S |f (S) .</p><p> :</p><p>S(f ) = ExU</p><p>yN(x)</p><p>[f (x) f (y)] = ExU</p><p>f (x) EyN(x)</p><p>[f (y)] =</p><p>= ExU</p><p>f (x)Tf (x) = f ,Tf .</p><p> : </p><p> , </p><p> - |S|.</p><p>. ( ) 10: , CSclub, 2016 16 / 31</p></li><li><p>S(f ) = f ,Tf =S[n]</p><p>f (S)2 |S |(Tf (x) = E</p><p>yN(x)[f (y)]</p><p>).</p><p> Tf (S) = |S |f (S) .</p><p> :</p><p>S(f ) = ExU</p><p>yN(x)</p><p>[f (x) f (y)] = ExU</p><p>f (x) EyN(x)</p><p>[f (y)] =</p><p>= ExU</p><p>f (x)Tf (x) = f ,Tf .</p><p> : </p><p> , </p><p> - |S|.</p><p>. ( ) 10: , CSclub, 2016 16 / 31</p></li><li><p>S(f ) = f ,Tf =S[n]</p><p>f (S)2 |S |(Tf (x) = E</p><p>yN(x)[f (y)]</p><p>).</p><p> Tf (S) = |S |f (S) .</p><p> :</p><p>S(f ) = ExU</p><p>yN(x)</p><p>[f (x) f (y)] = ExU</p><p>f (x) EyN(x)</p><p>[f (y)] =</p><p>= ExU</p><p>f (x)Tf (x) = f ,Tf .</p><p> : </p><p> , </p><p> - |S|.</p><p>. ( ) 10: , CSclub, 2016 16 / 31</p></li><li><p>Majn(x1, . . . , xn) =</p><p>{1, 1,+1, .</p><p>limn</p><p>S(Majn) = 12 arccos </p><p>.</p><p> z1, z2 </p><p>E[z1z2] = . </p><p>Pr[z1 6 0, z2 6 0] =1</p><p>2 1</p><p>2 arccos </p><p>.</p><p>. ( ) 10: , CSclub, 2016 17 / 31</p></li><li><p>Majn(x1, . . . , xn) =</p><p>{1, 1,+1, .</p><p>limn</p><p>S(Majn) = 12 arccos </p><p>.</p><p> z1, z2 </p><p>E[z1z2] = . </p><p>Pr[z1 6 0, z2 6 0] =1</p><p>2 1</p><p>2 arccos </p><p>.</p><p>. ( ) 10: , CSclub, 2016 17 / 31</p><p> :</p><p>Majn(x1, . . . , xn) = sign( 1</p><p>n</p><p>i</p><p>xi</p><p>).</p></li><li><p> (inuence)</p><p>Inf i (f ) = PrxU [ f xi ]</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>Inf6Ci (f ) =</p><p>|S |6CS3i</p><p>f (S)2</p><p>. ( ) 10: , CSclub, 2016 18 / 31</p></li><li><p> (inuence)</p><p>Inf i (f ) = PrxU [ f xi ]</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>Inf6Ci (f ) =</p><p>|S |6CS3i</p><p>f (S)2</p><p>. ( ) 10: , CSclub, 2016 18 / 31</p></li><li><p> (inuence)</p><p>Inf i (f ) = PrxU [ f xi ]</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>Inf6Ci (f ) =</p><p>|S |6CS3i</p><p>f (S)2</p><p>. ( ) 10: , CSclub, 2016 18 / 31</p></li><li><p>Di f (x) =f(xxi :=1</p><p>) f(xxi :=+1</p><p>)2</p><p> {1, 0,+1}</p><p>Inf i (f ) = PrxU</p><p>[|Di f (x)| = 1</p><p>],</p><p>Inf i (f ) = ExU</p><p>[Di f (x)2] = Di f (x),Di f (x),</p><p>Di f (x) =S3i</p><p>f (S)S\{i}(x)</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>. ( ) 10: , CSclub, 2016 19 / 31</p></li><li><p>Di f (x) =f(xxi :=1</p><p>) f(xxi :=+1</p><p>)2</p><p> {1, 0,+1}</p><p>Inf i (f ) = PrxU</p><p>[|Di f (x)| = 1</p><p>],</p><p>Inf i (f ) = ExU</p><p>[Di f (x)2] = Di f (x),Di f (x),</p><p>Di f (x) =S3i</p><p>f (S)S\{i}(x)</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>. ( ) 10: , CSclub, 2016 19 / 31</p></li><li><p>Di f (x) =f(xxi :=1</p><p>) f(xxi :=+1</p><p>)2</p><p> {1, 0,+1}</p><p>Inf i (f ) = PrxU</p><p>[|Di f (x)| = 1</p><p>],</p><p>Inf i (f ) = ExU</p><p>[Di f (x)2] = Di f (x),Di f (x),</p><p>Di f (x) =S3i</p><p>f (S)S\{i}(x)</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>. ( ) 10: , CSclub, 2016 19 / 31</p></li><li><p>Di f (x) =f(xxi :=1</p><p>) f(xxi :=+1</p><p>)2</p><p> {1, 0,+1}</p><p>Inf i (f ) = PrxU</p><p>[|Di f (x)| = 1</p><p>],</p><p>Inf i (f ) = ExU</p><p>[Di f (x)2] = Di f (x),Di f (x),</p><p>Di f (x) =S3i</p><p>f (S)S\{i}(x)</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>. ( ) 10: , CSclub, 2016 19 / 31</p></li><li><p>Di f (x) =f(xxi :=1</p><p>) f(xxi :=+1</p><p>)2</p><p> {1, 0,+1}</p><p>Inf i (f ) = PrxU</p><p>[|Di f (x)| = 1</p><p>],</p><p>Inf i (f ) = ExU</p><p>[Di f (x)2] = Di f (x),Di f (x),</p><p>Di f (x) =S3i</p><p>f (S)S\{i}(x)</p><p>Inf i (f ) =S3i</p><p>f (S)2.</p><p>. ( ) 10: , CSclub, 2016 19 / 31</p></li><li><p> (Majority is the stablest, MIS)</p><p> 0 &lt; &lt; 1, &gt; 0 , f : {1}n [1; 1] E[f ] = 0 Inf i (f ) 6 1 6 i 6 n, </p><p>S(f ) 6 12</p><p>arccos + .</p><p> , : ,</p><p> ..</p><p>. ( ) 10: , CSclub, 2016 20 / 31</p></li><li><p> (Majority is the stablest, MIS)</p><p> 0 &lt; &lt; 1, &gt; 0 , f : {1}n [1; 1] E[f ] = 0 Inf i (f ) 6 1 6 i 6 n, </p><p>S(f ) 6 12</p><p>arccos + .</p><p> , : ,</p><p> ..</p><p>. ( ) 10: , CSclub, 2016 20 / 31</p></li><li><p> 2</p><p> 0 &lt; &lt; 1, &gt; 0 , C f : {1}n [1; 1] E[f ] = 0 Inf</p><p>6Ci (f ) 6 1 6 i 6 n, </p><p>S(f ) 6 12</p><p>arccos + .</p><p> MIS .</p><p>: f , g = Tf .</p><p>. ( ) 10: , CSclub, 2016 21 / 31</p></li><li><p> 2</p><p> 0 &lt; &lt; 1, &gt; 0 , C f : {1}n [1; 1] E[f ] = 0 Inf</p><p>6Ci (f ) 6 1 6 i 6 n, </p><p>S(f ) 6 12</p><p>arccos + .</p><p> MIS .</p><p>: f , g = Tf .</p><p>. ( ) 10: , CSclub, 2016 21 / 31</p></li><li><p> ( &lt; 0)</p><p> 3: </p><p> 1 &lt; &lt; 0, &gt; 0 , C f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n, </p><p>S(f ) &gt; 12</p><p>arccos .</p><p>1 .</p><p>2 </p><p>1</p><p>2 1</p><p>2S(f ) 6</p><p>arccos </p><p>+</p><p>2.</p><p>. ( ) 10: , CSclub, 2016 22 / 31</p></li><li><p> ( &lt; 0)</p><p> 3: </p><p> 1 &lt; &lt; 0, &gt; 0 , C f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n, </p><p>S(f ) &gt; 12</p><p>arccos .</p><p>1 .</p><p>2 </p><p>1</p><p>2 1</p><p>2S(f ) 6</p><p>arccos </p><p>+</p><p>2.</p><p>. ( ) 10: , CSclub, 2016 22 / 31</p></li><li><p> ( &lt; 0)</p><p> 3: </p><p> 1 &lt; &lt; 0, &gt; 0 , C f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n, </p><p>S(f ) &gt; 12</p><p>arccos .</p><p>1 .</p><p>2 </p><p>1</p><p>2 1</p><p>2S(f ) 6</p><p>arccos </p><p>+</p><p>2.</p><p>. ( ) 10: , CSclub, 2016 22 / 31</p></li><li><p> 3 2</p><p> 1 &lt; &lt; 0 f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n. </p><p>g(x) =1</p><p>2</p><p>(f (x) f (x)</p><p>)=</p><p>|S | </p><p>f (S)S(x).</p><p> E[g ] = 0 </p><p>Inf6Ci (g) =</p><p>|S| |S |6C</p><p>f (S)2 6|S|6C</p><p>f (S)2 = Inf6Ci (f ) 6 .</p><p> g 2 :</p><p>S(g) = S(g) 6 12</p><p>arccos() + .</p><p> S(f ) &gt; S(g) &gt; 1 +2</p><p>arccos() = 1 2</p><p>arccos .</p><p>. ( ) 10: , CSclub, 2016 23 / 31</p></li><li><p> 3 2</p><p> 1 &lt; &lt; 0 f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n. </p><p>g(x) =1</p><p>2</p><p>(f (x) f (x)</p><p>)=</p><p>|S | </p><p>f (S)S(x).</p><p> E[g ] = 0 </p><p>Inf6Ci (g) =</p><p>|S| |S |6C</p><p>f (S)2 6|S|6C</p><p>f (S)2 = Inf6Ci (f ) 6 .</p><p> g 2 :</p><p>S(g) = S(g) 6 12</p><p>arccos() + .</p><p> S(f ) &gt; S(g) &gt; 1 +2</p><p>arccos() = 1 2</p><p>arccos .</p><p>. ( ) 10: , CSclub, 2016 23 / 31</p></li><li><p> 3 2</p><p> 1 &lt; &lt; 0 f : {1}n [1; 1] Inf6Ci (f ) 6 1 6 i 6 n. </p><p>g(x) =1</p><p>2</p><p>(f (x) f (x)</p><p>)=</p><p>|S | </p><p>f (S)S(x).</p><p> E[g ] = 0 </p><p>Inf6Ci (g) =</p><p>|S| |S |6C</p><p>f (S)2 6|S|6C</p><p>f (S)2 = Inf6Ci (f ) 6 .</p><p> g 2 :</p><p>S(g) = S(g) 6 12</p><p>arccos() + .</p><p> S(f ) &gt; S(g) &gt; 1 +2</p><p>arccos() = 1 2</p><p>arccos .</p><p>. ( ) 10: , CSclub, 2016 23 / 31</p></li><li><p> : 1</p><p> :</p><p> {fw} arccos / + , : (V W ) [m], &gt; .</p><p> ( )</p><p> &gt; /2 V arccos / + /2.</p><p>2 1 +</p><p>(1 </p><p>2</p><p>)(arccos </p><p>+</p><p>2</p><p>) arccos / + /2</p><p>. ( ) 10: , CSclub, 2016 24 / 31</p></li><li><p> : 1</p><p> :</p><p> {fw} arccos / + , : (V W ) [m], &gt; .</p><p> ( )</p><p> &gt; /2 V arccos / + /2.</p><p>2 1 +</p><p>(1 </p><p>2</p><p>)(arccos </p><p>+</p><p>2</p><p>) arccos / + /2</p><p>. ( ) 10: , CSclub, 2016 24 / 31</p></li><li><p> : 1</p><p> :</p><p> {fw} arccos / + , : (V W ) [m], &gt; .</p><p> ( )</p><p> &gt; /2 V arccos / + /2.</p><p>2 1 +</p><p>(1 </p><p>2</p><p>)(arccos </p><p>+</p><p>2</p><p>) arccos / + /2</p><p>. ( ) 10: , CSclub, 2016 24 / 31</p></li><li><p> : 1</p><p> :</p><p> {fw} arccos / + , : (V W ) [m], &gt; .</p><p> ( )</p><p> &gt; /2 V arccos / + /2.</p><p>2 1 +</p><p>(1 </p><p>2</p><p>)(arccos </p><p>+</p><p>2</p><p>) arccos / + /2</p><p>. ( ) 10: , CSclub, 2016 24 / 31</p></li><li><p> : 2</p><p> Uv v . </p><p>gv (x) = EwUv</p><p>[fw (v ,w x)].</p><p> , v , fw (w), gv (v):</p><p>EwUv</p><p>[xv,w ((w))] = EwUv</p><p>[x(v)] = x(v).</p><p> - </p><p> v .</p><p>. ( ) 10: , CSclub, 2016 25 / 31</p></li><li><p> : 2</p><p> Uv v . </p><p>gv (x) = EwUv</p><p>[fw (v ,w x)].</p><p> , v , fw (w), gv (v):</p><p>EwUv</p><p>[xv,w ((w))] = EwUv</p><p>[x(v)] = x(v).</p><p> - </p><p> v .</p><p>. ( ) 10: , CSclub, 2016 25 / 31</p></li><li><p> : 2</p><p> Uv v . </p><p>gv (x) = EwUv</p><p>[fw (v ,w x)].</p><p> , v , fw (w), gv (v):</p><p>EwUv</p><p>[xv,w ((w))] = EwUv</p><p>[x(v)] = x(v).</p><p> - </p><p> v .</p><p>. ( ) 10: , CSclub, 2016 25 / 31</p></li><li><p> : 3</p><p> v V :</p><p>Pr[ ] = Prx ,x ,w ,w </p><p>[fw ( x)fw ( x ) = 1] =</p><p>=1</p><p>2 1</p><p>2Ex ,x </p><p>Ew ,w </p><p>[fw ( x)fw ( x )] =</p><p>=1</p><p>2 1</p><p>2Ex ,x </p><p>[gv (x)gv (x)] =</p><p>1</p><p>2 1</p><p>2S(gv )</p><p> 12 1</p><p>2S(gv ) &gt;</p><p>arccos +</p><p>2 </p><p> 12 1</p><p>2S(gv ) 6</p><p>arccos +</p><p>2.</p><p>, gv . jv , Inf</p><p>6Cjv</p><p>[gv ] &gt; . gv (x) = xj j ( 0).</p><p>. ( ) 10: , CSclub, 2016 26 / 31</p></li><li><p> : 3</p><p> v V :</p><p>Pr[ ] = Prx ,x ,w ,w </p><p>[fw ( x)fw ( x ) = 1] =</p><p>=1</p><p>2 1</p><p>2Ex ,x </p><p>Ew ,w </p><p>[fw ( x)fw ( x