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

  • Published on
    21-Feb-2017

  • View
    51

  • Download
    2

Embed Size (px)

Transcript

<ul><li><p> :</p><p> 9: </p><p>. </p><p> . ..</p><p>-, Computer Science Club, 2016</p><p>. ( ) 9: , CSclub, 2016 1 / 26</p></li><li><p> : </p><p> MAX-3LIN: F2, </p><p> .: , </p><p> .</p><p> 0 1/2. MAX-3LIN 1/2.</p><p> &gt; 0 MAX-3LIN(1 , 1/2 + ) NP-.</p><p>. ( ) 9: , CSclub, 2016 2 / 26</p></li><li><p> : </p><p> MAX-3LIN: F2, </p><p> .: , </p><p> .</p><p> 0 1/2. MAX-3LIN 1/2.</p><p> &gt; 0 MAX-3LIN(1 , 1/2 + ) NP-.</p><p>. ( ) 9: , CSclub, 2016 2 / 26</p></li><li><p> : </p><p> MAX-3LIN: F2, </p><p> .: , </p><p> .</p><p> 0 1/2. MAX-3LIN 1/2.</p><p> &gt; 0 MAX-3LIN(1 , 1/2 + ) NP-.</p><p>. ( ) 9: , CSclub, 2016 2 / 26</p></li><li><p> : </p><p> MAX-3LIN: F2, </p><p> .: , </p><p> .</p><p> 0 1/2. MAX-3LIN 1/2.</p><p> &gt; 0 MAX-3LIN(1 , 1/2 + ) NP-.</p><p>. ( ) 9: , CSclub, 2016 2 / 26</p><p>MAX-3LIN(1, ) P.</p></li><li><p>: </p><p> : 3 1 x , y Fn2 .2 z N(y), = 1 2.3 f x , y , x + z .4 , f (x) + f (y) = f (x + z). </p><p> .</p><p> . MAX-LCk(1, ) 6p MAX-3LIN(1 , 1/2 + ).</p><p>. ( ) 9: , CSclub, 2016 3 / 26</p></li><li><p>: </p><p> : 3 1 x , y Fn2 .2 z N(y), = 1 2.3 f x , y , x + z .4 , f (x) + f (y) = f (x + z). </p><p> .</p><p> . MAX-LCk(1, ) 6p MAX-3LIN(1 , 1/2 + ).</p><p>. ( ) 9: , CSclub, 2016 3 / 26</p></li><li><p>PCP MAX-LCk(1, ): </p><p> G (V ,E , [k], f ) . (v) [k] . Xi : (x1, . . . , xk) 7 xi :</p><p>Xi (x1, . . . , xk) = Xi (x1, . . . ,xk).</p><p> , . :</p><p>1 + Xi (x1, . . . , xk) = Xi (1 + x1, . . . , 1 + xk)</p><p> 2.</p><p> PCP Tv : {0, 1} {0, 1}, v V .</p><p>. ( ) 9: , CSclub, 2016 4 / 26</p></li><li><p>PCP A MAX-LCk(1, )</p><p> 1 (u, v) E (G ).2 Tu Tv .3 .</p><p> f ((u)) = (v), </p><p>Tv (x) = Tu(f (x)), f (x)j = xf (j), j [k].</p><p>Tu(x) + Tv (y) = Tu(x + z), x , y U; z N(f (y))</p><p>( , , ).</p><p>. ( ) 9: , CSclub, 2016 5 / 26</p></li><li><p>PCP A MAX-LCk(1, )</p><p> 1 (u, v) E (G ).2 Tu Tv .3 .</p><p> f ((u)) = (v), </p><p>Tv (x) = Tu(f (x)), f (x)j = xf (j), j [k].</p><p>Tu(x) + Tv (y) = Tu(x + z), x , y U; z N(f (y))</p><p>( , , ).</p><p>. ( ) 9: , CSclub, 2016 5 / 26</p></li><li><p>PCP A MAX-LCk(1, )</p><p> 1 (u, v) E (G ).2 Tu Tv .3 .</p><p> f ((u)) = (v), </p><p>Tv (x) = Tu(f (x)), f (x)j = xf (j), j [k].</p><p>Tu(x) + Tv (y) = Tu(x + z), x , y U; z N(f (y))</p><p>( , , ).</p><p>. ( ) 9: , CSclub, 2016 5 / 26</p></li><li><p> unsatG = 0, , A 1 .</p><p> . : V , . </p><p>Tu(x) = x(u), (v) = f ((u)) (uv) E .</p><p>Tu(x) = x(u), Tv (y) = y(v), (v) = f ((u)).</p><p>x(u) + yf ((u)) = x(u) + z(u) yf ((u)) = z(u),</p><p> 12(1 + ) = 1 .. ( ) 9: , CSclub, 2016 6 / 26</p></li><li><p> unsatG = 0, , A 1 .</p><p> . : V , . </p><p>Tu(x) = x(u), (v) = f ((u)) (uv) E .</p><p>Tu(x) = x(u), Tv (y) = y(v), (v) = f ((u)).</p><p>x(u) + yf ((u)) = x(u) + z(u) yf ((u)) = z(u),</p><p> 12(1 + ) = 1 .. ( ) 9: , CSclub, 2016 6 / 26</p></li><li><p> unsatG = 0, , A 1 .</p><p> . : V , . </p><p>Tu(x) = x(u), (v) = f ((u)) (uv) E .</p><p>Tu(x) = x(u), Tv (y) = y(v), (v) = f ((u)).</p><p>x(u) + yf ((u)) = x(u) + z(u) yf ((u)) = z(u),</p><p> 12(1 + ) = 1 .. ( ) 9: , CSclub, 2016 6 / 26</p></li><li><p> unsatG = 0, , A 1 .</p><p> . : V , . </p><p>Tu(x) = x(u), (v) = f ((u)) (uv) E .</p><p>Tu(x) = x(u), Tv (y) = y(v), (v) = f ((u)).</p><p>x(u) + yf ((u)) = x(u) + z(u) yf ((u)) = z(u),</p><p> 12(1 + ) = 1 .. ( ) 9: , CSclub, 2016 6 / 26</p></li><li><p> unsatG = 0, , A 1 .</p><p> . : V , . </p><p>Tu(x) = x(u), (v) = f ((u)) (uv) E .</p><p>Tu(x) = x(u), Tv (y) = y(v), (v) = f ((u)).</p><p>x(u) + yf ((u)) = x(u) + z(u) yf ((u)) = z(u),</p><p> 12(1 + ) = 1 .. ( ) 9: , CSclub, 2016 6 / 26</p></li><li><p> A &lt; 1/2 1/2 + - . , 2 .</p><p> 1 S </p><p>Tv (S)2</p><p>( ; ,Tv () = 0);</p><p>2 j S ;3 (v) = j .</p><p>. ( ) 9: , CSclub, 2016 7 / 26</p></li><li><p> A &lt; 1/2 1/2 + - . , 2 .</p><p> 1 S </p><p>Tv (S)2</p><p>( ; ,Tv () = 0);</p><p>2 j S ;3 (v) = j .</p><p>. ( ) 9: , CSclub, 2016 7 / 26</p></li><li><p> A &lt; 1/2 1/2 + - . , 2 .</p><p> 1 S </p><p>Tv (S)2</p><p>( ; ,Tv () = 0);</p><p>2 j S ;3 (v) = j .</p><p>. ( ) 9: , CSclub, 2016 7 / 26</p></li><li><p> A &lt; 1/2 1/2 + - . , 2 .</p><p> 1 S </p><p>Tv (S)2</p><p>( ; ,Tv () = 0);</p><p>2 j S ;3 (v) = j .</p><p>. ( ) 9: , CSclub, 2016 7 / 26</p></li><li><p> A &lt; 1/2 1/2 + - . , 2 .</p><p> 1 S </p><p>Tv (S)2</p><p>( ; ,Tv () = 0);</p><p>2 j S ;3 (v) = j .</p><p>. ( ) 9: , CSclub, 2016 7 / 26</p></li><li><p> A A = Tu, B = Tv 1/2 + uv . f 2uv .</p><p> .</p><p> , </p><p>E(uv)E</p><p>[2uv ] &gt; </p><p>(E</p><p>(uv)E[uv ]</p><p>)2= 2.</p><p>. ( ) 9: , CSclub, 2016 8 / 26</p></li><li><p> A A = Tu, B = Tv 1/2 + uv . f 2uv .</p><p> .</p><p> , </p><p>E(uv)E</p><p>[2uv ] &gt; </p><p>(E</p><p>(uv)E[uv ]</p><p>)2= 2.</p><p>. ( ) 9: , CSclub, 2016 8 / 26</p></li><li><p>S</p><p>f</p><p>i fodd(S)</p><p>fodd(S)</p><p>f odd(S) ={i :f 1(i) S },</p><p>S .</p><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>( A = Tu, B = Tv .)</p><p>. ( ) 9: , CSclub, 2016 9 / 26</p></li><li><p>S</p><p>f</p><p>i fodd(S)</p><p>fodd(S)</p><p>f odd(S) ={i :f 1(i) S },</p><p>S .</p><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>( A = Tu, B = Tv .)</p><p>. ( ) 9: , CSclub, 2016 9 / 26</p></li><li><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>1 S A(S)2.2 f odd(S) B</p><p> B(f odd(S))2.3 </p><p> 1/|S |. i f odd(S) j S , f (j) = i . , S A f odd(S) B </p><p>jS</p><p>1|S |</p><p>if odd(S)</p><p>1|f odd(S)|</p><p>=1|S |</p><p>.</p><p>. ( ) 9: , CSclub, 2016 10 / 26</p></li><li><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>1 S A(S)2.2 f odd(S) B</p><p> B(f odd(S))2.3 </p><p> 1/|S |. i f odd(S) j S , f (j) = i . , S A f odd(S) B </p><p>jS</p><p>1|S |</p><p>if odd(S)</p><p>1|f odd(S)|</p><p>=1|S |</p><p>.</p><p>. ( ) 9: , CSclub, 2016 10 / 26</p></li><li><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>1 S A(S)2.2 f odd(S) B</p><p> B(f odd(S))2.3 </p><p> 1/|S |. i f odd(S) j S , f (j) = i . , S A f odd(S) B </p><p>jS</p><p>1|S |</p><p>if odd(S)</p><p>1|f odd(S)|</p><p>=1|S |</p><p>.</p><p>. ( ) 9: , CSclub, 2016 10 / 26</p></li><li><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p>1 S A(S)2.2 f odd(S) B</p><p> B(f odd(S))2.3 </p><p> 1/|S |. i f odd(S) j S , f (j) = i . , S A f odd(S) B </p><p>jS</p><p>1|S |</p><p>if odd(S)</p><p>1|f odd(S)|</p><p>=1|S |</p><p>.</p><p>. ( ) 9: , CSclub, 2016 10 / 26</p></li><li><p>S(f (x)) = f odd(S)(x) (: f (x)j = xf (j)).</p><p>S(f (x)) =jS</p><p>f (x)j =jS</p><p>xf (j) =</p><p>if odd(S)</p><p>xi = f odd(S)(x),</p><p> : x2 = 1 xi , |f 1(i) S | , 1.</p><p>. ( ) 9: , CSclub, 2016 11 / 26</p></li><li><p>S(f (x)) = f odd(S)(x) (: f (x)j = xf (j)).</p><p>S(f (x)) =jS</p><p>f (x)j =jS</p><p>xf (j) =</p><p>if odd(S)</p><p>xi = f odd(S)(x),</p><p> : x2 = 1 xi , |f 1(i) S | , 1.</p><p>. ( ) 9: , CSclub, 2016 11 / 26</p></li><li><p>S(f (x)) = f odd(S)(x) (: f (x)j = xf (j)).</p><p>S(f (x)) =jS</p><p>f (x)j =jS</p><p>xf (j) =</p><p>if odd(S)</p><p>xi = f odd(S)(x),</p><p> : x2 = 1 xi , |f 1(i) S | , 1.</p><p>. ( ) 9: , CSclub, 2016 11 / 26</p></li><li><p> A, B &gt; 1/2 + . </p><p>S 6=A(S)2B(f odd(S))(1 2)|S | &gt; 2.</p><p> . . </p><p>Pr[A(x)B(y) = A(x + z)] &gt; 1/2 + ,</p><p> E[A(x)B(y)A(x + z)] &gt; 2.</p><p>. ( ) 9: , CSclub, 2016 12 / 26</p></li><li><p> A, B &gt; 1/2 + . </p><p>S 6=A(S)2B(f odd(S))(1 2)|S | &gt; 2.</p><p> . . </p><p>Pr[A(x)B(y) = A(x + z)] &gt; 1/2 + ,</p><p> E[A(x)B(y)A(x + z)] &gt; 2.</p><p>. ( ) 9: , CSclub, 2016 12 / 26</p></li><li><p>z = f (y) + w , w B ( ) :</p><p>Ex ,y ,w</p><p>[A(x)B(y)A(x + f (y) + w)] =</p><p>= Ex ,y ,w</p><p>[(S</p><p>A(S)S(x))(</p><p>U</p><p>B(U)U(y))</p><p>(</p><p>T</p><p>A(T )T (x + f (y) + w)))]</p><p>=</p><p>=S ,U,T</p><p>A(S)B(U)A(T ) Ex</p><p>[S(x)T (x)] Ey</p><p>[U(y)T (f (y))] Ew</p><p>[T (w)] =</p><p>=S,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] &gt; 2.</p><p>. ( ) 9: , CSclub, 2016 13 / 26</p></li><li><p>z = f (y) + w , w B ( ) :</p><p>Ex ,y ,w</p><p>[A(x)B(y)A(x + f (y) + w)] =</p><p>= Ex ,y ,w</p><p>[(S</p><p>A(S)S(x))(</p><p>U</p><p>B(U)U(y))</p><p>(</p><p>T</p><p>A(T )T (x + f (y) + w)))]</p><p>=</p><p>=S,U,T</p><p>A(S)B(U)A(T ) Ex</p><p>[S(x)T (x)] Ey</p><p>[U(y)T (f (y))] Ew</p><p>[T (w)] =</p><p>=S,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] &gt; 2.</p><p>. ( ) 9: , CSclub, 2016 13 / 26</p><p> S(x + y) = S(x) S(y).</p></li><li><p>z = f (y) + w , w B ( ) :</p><p>Ex ,y ,w</p><p>[A(x)B(y)A(x + f (y) + w)] =</p><p>= Ex ,y ,w</p><p>[(S</p><p>A(S)S(x))(</p><p>U</p><p>B(U)U(y))</p><p>(</p><p>T</p><p>A(T )T (x + f (y) + w)))]</p><p>=</p><p>=S,U,T</p><p>A(S)B(U)A(T ) Ex</p><p>[S(x)T (x)] Ey</p><p>[U(y)T (f (y))] Ew</p><p>[T (w)] =</p><p>=S,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] &gt; 2.</p><p>. ( ) 9: , CSclub, 2016 13 / 26</p></li><li><p> ()</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] =</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)f odd(S)(y)] Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S)) Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S))(1 2)|S| &gt; 2</p><p>. ( ) 9: , CSclub, 2016 14 / 26</p></li><li><p> ()</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] =</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)f odd(S)(y)] Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S)) Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S))(1 2)|S| &gt; 2</p><p> : </p><p>. ( ) 9: , CSclub, 2016 14 / 26</p></li><li><p> ()</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] =</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)f odd(S)(y)] Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S)) Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S))(1 2)|S| &gt; 2</p><p>. ( ) 9: , CSclub, 2016 14 / 26</p></li><li><p> ()</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)S(f (y))] Ew</p><p>[S(w)] =</p><p>=S ,U</p><p>A(S)2B(U) Ey</p><p>[U(y)f odd(S)(y)] Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S)) Ew</p><p>[S(w)] =</p><p>=S</p><p>A(S)2B(f odd(S))(1 2)|S| &gt; 2</p><p> E[wi ] = (1 ) 1 + (1) = 1 2 |S | .</p><p>. ( ) 9: , CSclub, 2016 14 / 26</p></li><li><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2</p><p> A, B &gt; 1/2 + . </p><p>S 6=A(S)2B(f odd(S))(1 2)|S | &gt; 2.</p><p> :</p><p>Pr[f ((u)) = (v)] &gt;S 6=</p><p>1|S |</p><p>A(S)2B(f odd(S))2 &gt; 2</p><p>. ( ) 9: , CSclub, 2016 15 / 26</p></li><li><p>(1 2)|S| 6 2|S |</p><p> &lt; 1/2</p><p>( ) </p><p>2 6S 6=</p><p>A(S)2B(f odd(S))(1 2)|S | 6S 6=</p><p>A(S)2B(f odd(S))2|S |</p><p> 6(</p><p>S 6=A(S)2</p><p>)1/2(S 6=</p><p>A(S)2B(f odd(S))21|S |</p><p>)1/2.</p><p>. ( ) 9: , CSclub, 2016 16 / 26</p></li><li><p>(1 2)|S| 6 2|S |</p><p> &lt; 1/2</p><p>( ) </p><p>2 6S 6=</p><p>A(S)2B(f odd(S))(1 2)|S | 6S 6=</p><p>A(S)2B(f odd(S))2|S |</p><p> 6(</p><p>S 6=A(S)2</p><p>)1/2(S 6=</p><p>A(S)2B(f odd(S))21|S |</p><p>)1/2.</p><p>. ( ) 9: , CSclub, 2016 16 / 26</p></li><li><p>(1 2)|S| 6 2|S |</p><p> &lt; 1/2</p><p>( ) </p><p>2 6S 6=</p><p>A(S)2B(f odd(S))(1 2)|S | 6S 6=</p><p>A(S)2B(f odd(S))2|S |</p><p> 6(</p><p>S 6=A(S)2</p><p>)1/2(S 6=</p><p>A(S)2B(f odd(S))21|S |</p><p>)1/2.</p><p>. ( ) 9: , CSclub, 2016 16 / 26</p></li><li><p> ()</p><p> 6(</p><p>S 6=A(S)2</p><p>)1/2(S 6=</p><p>A(S)2B(f odd(S))21|S |</p><p>)1/2.</p><p> , , A:</p><p>2 6S 6=</p><p>A(S)2B(f odd(S))21|S |</p><p>6 Pr[f ((u)) = (v)],</p><p> .</p><p>. ( ) 9: , CSclub, 2016 17 / 26</p></li><li><p> MAX-3LIN</p><p> &lt; 3. G (V ,E , [k], f ) MAX-LCk(1, ). PCP A = . . :</p><p>( ) G , ( ) &gt; 1 ( ).( ) 6 , ( ) 1/2 + .</p><p> MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + ). : .. ( ) 9: , CSclub, 2016 18 / 26</p></li><li><p> MAX-3LIN</p><p> &lt; 3. G (V ,E , [k], f ) MAX-LCk(1, ). PCP A = . . :</p><p>( ) G , ( ) &gt; 1 ( ).( ) 6 , ( ) 1/2 + .</p><p> MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + ). : .. ( ) 9: , CSclub, 2016 18 / 26</p></li><li><p> MAX-3LIN</p><p> &lt; 3. G (V ,E , [k], f ) MAX-LCk(1, ). PCP A = . . :</p><p>( ) G , ( ) &gt; 1 ( ).( ) 6 , ( ) 1/2 + .</p><p> MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + ). : .. ( ) 9: , CSclub, 2016 18 / 26</p></li><li><p> MAX-3LIN</p><p> &lt; 3. G (V ,E , [k], f ) MAX-LCk(1, ). PCP A = . . :</p><p>( ) G , ( ) &gt; 1 ( ).( ) 6 , ( ) 1/2 + .</p><p> MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + ). : .. ( ) 9: , CSclub, 2016 18 / 26</p></li><li><p> MAX-3LIN ()</p><p> : &lt; 3/8, = /2. , , .</p><p>MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + )</p><p> &lt; 3/8 ( ).</p><p>. ( ) 9: , CSclub, 2016 19 / 26</p></li><li><p> MAX-3LIN ()</p><p> : &lt; 3/8, = /2. , , .</p><p>MAX-LCk(1, ) 6p MAX-3-LIN(1 , 1/2 + )</p><p> &lt; 3/8 ( ).</p><p>. ( ) 9: , CSclub, 2016 19 / 26</p></li><li><p> MAX-3SAT</p><p> &gt; 0 MAX-3SAT(1 4, 7/8 + ) NP-.</p><p> x + y + z = a 3 4 . MAX-3LIN(1 4, 1/2 + 4) 6p MAX-3SAT(1 4, 7/8 + ). 3 4 , C . &gt; 1 4 , C &gt; 1 4 . 1/2 + 4 , C </p><p>1 (12 4) 1</p><p>4=</p><p>78</p><p>+ .</p><p>. ( ) 9: , CSclub, 2016 20 / 26</p></li><li><p> MAX-3SAT</p><p> &gt; 0 MAX-3SAT(1 4, 7/8 + ) NP-.</p><p> x + y + z = a 3 4 . MAX-3LIN(1 4, 1/2 + 4) 6p MAX-3SAT(1 4, 7/8 + ). 3 4 , C . &gt; 1 4 , C &gt; 1 4 . 1/2 + 4 , C </p><p>1 (12 4) 1</p><p>4=</p><p>78</p><p>+ .</p><p>. ( ) 9: , CSclub, 2016 20 / 26</p></li><li><p> MAX-3SAT</p><p> &gt; 0 MAX-3SAT(1 4, 7/8 + ) NP-.</p><p> x + y + z = a 3 4 . MAX-3LIN(1 4, 1/2 + 4) 6p MAX-3SAT(1 4, 7/8 + ). 3 4 , C . &gt; 1 4 , C &gt; 1 4 . 1/2 + 4 , C </p><p>1 (12 4) 1</p><p>4=</p><p>78</p><p>+ .</p><p>. ( ) 9: , CSclub, 2016 20 / 26</p></li><li><p> MAX-3SAT</p><p> &gt; 0 MAX-3SAT(1 4, 7/8 + ) NP-.</p><p> x + y + z = a 3 4 . MAX-3LIN(1 4, 1/2 + 4) 6p MAX-3SAT(1 4, 7/8 + ). 3 4 , C . &gt; 1 4 , C &gt; 1 4 . 1/2 + 4 , C </p><p>1 (12 4) 1</p><p>4=</p><p>78</p><p>+ .</p><p>. ( ) 9: , CSclub, 2016 20 / 26</p></li><li><p> MAX-3SAT</p><p> &gt; 0 MAX-3SAT(1 4, 7/8 + ) NP-.</p><p> x + y + z = a 3 4 . MAX-3LIN(1 4, 1/2 + 4) 6p MAX-3SAT(1 4, 7/8 + ). 3 4 , C . &gt; 1 4 , C &gt; 1 4 . 1/2 + 4 , C </p><p>1 (12 4) 1</p><p>4=</p><p>78</p><p>+ .</p><p>. ( ) 9: , CSclub, 2016 20 / 26</p></li><li><p> MAX-CUT</p><p> &gt; 0 MAX-CUT () 16/17 + P = NP.</p><p>. ( ) 9: , CSclub, 2016 21 / 26</p></li><li><p> MAX-CUT</p><p> &gt; 0 MAX-CUT () 16/17 + P = NP.</p><p>0</p><p>x1</p><p>x2</p><p>x3</p><p> G8 x1 + x2 + x3 = 0</p><p>x1</p><p>x2</p><p>x3</p><p>02</p><p> G9 x1 + x2 + x3 = 1</p><p>. ( ) 9: , CSclub, 2016 21 / 26</p></li><li><p> 8-</p><p> . 0 0. 1.</p><p>0</p><p>x1</p><p>x2</p><p>x3</p><p> G8 x1 + x2 + x3 = 0</p><p> x1, x2, x3 G8 , x1 + x2 + x3 = 0. G8 0 = 16. , x1 + x2 + x3 = 1, 14 = 0 2.</p><p>. ( ) 9: , CSclub, 2016 22 / 26</p></li><li><p> 9-</p><p> . 0 0. 1.</p><p>x1</p><p>x2</p><p>x3</p><p>02</p><p> G9 x1 + x2 + x3 = 1</p><p> x1, x2, x3 G9 , x1 + x2 + x3 = 1. G9 1 = 18. , x1 + x2 + x3 = 0, 16 = 1 2.</p><p>. ( ) 9: , CSclub, 2016 23 / 26</p></li><li><p> 2, . , . , 1/2. G : G8 G9, . 0 , .</p><p>. ( ) 9: , CSclub, 2016 24 / 26</p></li><li><p> 2, . , . , 1/2. G : G8 G9, . 0 , .</p><p>. ( ) 9: , CSclub, 2016 24 / 26</p></li><li><p> 2, . , . , 1/2. G : G8 G9, . 0 , .</p><p>. ( ) 9: , CSclub, 2016 24 / 26</p></li><li><p> p0 &gt; 1/2 , 0;p1 = 1 p0; = 0p0 + 1p1 = 16p0 + 18p1. w0 0 w1 1, w0 + w1 &gt; 1 . G </p><p>0w0 + (0 2)(p0 w0) + 1w1 + (1 2)(p1 w1) ==0p0 + 1p1 2 + 2(w0 + w1) &gt; 2.</p><p> w0 + w1 6 1/2 + , </p><p>0p0 + 1p1 2 + 2(w0 + w1) = 1 + 2.</p><p> = 0p0 + 1p1 p0 &gt; 1/2, </p><p>1 1</p><p>6 1 1(0 + 1)/2</p><p>= 1 216 + 18</p><p>=1617</p><p>.</p><p>. ( ) 9: , CSclub, 2016 25 / 26</p></li><li><p> p0 &gt; 1/2 , 0;p1 = 1 p0; = 0p0 + 1p1 = 16p0 + 18p1. w0 0 w1 1, w0 + w1 &gt; 1 . G </p><p>0w0 + (0 2)(p0 w0) + 1w1 + (1 2)(p1 w1) ==0p0 + 1p1 2 + 2(w0 + w1) &gt; 2.</p><p> w0 + w1 6 1/2 + , </p><p>0p0 + 1p1 2 + 2(w0 + w1) = 1 + 2.</p><p> = 0p0 + 1p1 p0 &gt; 1/2, </p><p>1 1</p><p>6 1 1(0 + 1)/2</p><p>= 1 216 + 18</p><p>=1617</p><p>.</p><p>. ( ) 9: , CSclub, 2016 25 / 26</p></li><li><p> p0 &gt; 1/2 , 0;p1 = 1 p0; = 0p0 + 1p1 = 16p0 + 18p1. w0 0 w1 1, w0 + w1 &gt; 1 . G </p><p>0w0 + (0 2)(p0 w0) + 1w1 + (1 2)(p1 w1) ==0p0 + 1p1 2 + 2(w0 + w1) &gt; 2.</p><p> w0 + w1 6 1/2 + , </p><p>0p0 + 1p1 2 + 2(w0 + w1) = 1 + 2.</p><p> = 0p0 + 1p1 p0 &gt; 1/2, </p><p>1 1</p><p>6 1 1(0 + 1)/2</p><p>= 1 216 + 18</p><p>=1617</p><p>.</p><p>. ( ) 9: , CSclub, 2016 25 / 26</p></li><li><p> MAX-CUT</p><p> MAX-CUT 16/17 + . &gt; 0, </p><p> 1 + 2 2</p><p> 1 w0 + w1 6 1/2 + . NP- MAX-3LIN(1 , 1/2 + ).</p><p>. ( ) 9: , CSclub, 2016 26 / 26</p></li><li><p> MAX-CUT</p><p> MAX-CUT 16/17 + . &gt; 0, </p><p> 1 + 2 2</p><p> 1 w0 + w1 6 1/2 + . NP- MAX-3LIN(1 , 1/2 + ).</p><p>. ( ) 9: , CSclub, 2016 26 / 26</p></li><li><p> MAX-CUT</p><p> MAX-CUT 16/17 + . &gt; 0, </p><p> 1 + 2 2</p><p> 1 w0 + w1 6 1/2 + . NP- MAX-3LIN(1 , 1/2 + ).</p><p>. ( ) 9: , CSclub, 2016 26 / 26</p></li></ul>