Алгоритмы для NP-трудных задач, осень 2009: NP-полные задачи

  • Published on
    15-Apr-2017

  • View
    248

  • Download
    7

Embed Size (px)

Transcript

<ul><li><p> NP- 3: NP- </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (Computer Science ) 3. NP- 1 / 42</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 2 / 42</p></li><li><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 2 / 42</p></li><li><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 2 / 42</p></li><li><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 3 / 42</p></li><li><p> , , , , ( n, n2,n3) . (,, ) : n! n n , n nn2 , , , s t.</p><p>. (Computer Science ) 3. NP- 4 / 42</p></li><li><p> , , , , ( n, n2,n3) .</p><p> (,, ) : n! n n , n nn2 , , , s t.</p><p>. (Computer Science ) 3. NP- 4 / 42</p></li><li><p> , , , , ( n, n2,n3) . (,, ) : n! n n , n nn2 , , , s t.</p><p>. (Computer Science ) 3. NP- 4 / 42</p></li><li><p> , , . , 2n , . , , .</p><p>. (Computer Science ) 3. NP- 5 / 42</p></li><li><p> , , . , 2n , .</p><p> , , .</p><p>. (Computer Science ) 3. NP- 5 / 42</p></li><li><p> , , . , 2n , . , , .</p><p>. (Computer Science ) 3. NP- 5 / 42</p></li><li><p> (satisfiabilityproblem, SAT) :</p><p>(x y z)(x y)(y z)(z x)(x y z) .</p><p> .</p><p>. (Computer Science ) 3. NP- 6 / 42</p></li><li><p> (satisfiabilityproblem, SAT) :</p><p>(x y z)(x y)(y z)(z x)(x y z) .</p><p> .</p><p>. (Computer Science ) 3. NP- 6 / 42</p></li><li><p> (satisfiabilityproblem, SAT) :</p><p>(x y z)(x y)(y z)(z x)(x y z) .</p><p> .</p><p>. (Computer Science ) 3. NP- 6 / 42</p></li><li><p> (searchproblem). (instance) I ( , ; ) (solution) S(, ; ). , . S I .</p><p>. (Computer Science ) 3. NP- 7 / 42</p></li><li><p> (searchproblem).</p><p> (instance) I ( , ; ) (solution) S(, ; ). , . S I .</p><p>. (Computer Science ) 3. NP- 7 / 42</p></li><li><p> (searchproblem). (instance) I ( , ; ) (solution) S(, ; ). , .</p><p> S I .</p><p>. (Computer Science ) 3. NP- 7 / 42</p></li><li><p> (searchproblem). (instance) I ( , ; ) (solution) S(, ; ). , . S I .</p><p>. (Computer Science ) 3. NP- 7 / 42</p></li><li><p> , , I S |I | . , S I , (I , S) = true.</p><p>. (Computer Science ) 3. NP- 8 / 42</p></li><li><p> (traveling salesman problem, TSP) n 1, . . . , n n(n 1)/2 , b. , ( ) b, , . , (1), . . . , (n), </p><p>d(1),(2) + d(2),(3) + + d(n),(1) b .</p><p>. (Computer Science ) 3. NP- 9 / 42</p></li><li><p> (traveling salesman problem, TSP) n 1, . . . , n n(n 1)/2 , b.</p><p> , ( ) b, , . , (1), . . . , (n), </p><p>d(1),(2) + d(2),(3) + + d(n),(1) b .</p><p>. (Computer Science ) 3. NP- 9 / 42</p></li><li><p> (traveling salesman problem, TSP) n 1, . . . , n n(n 1)/2 , b. , ( ) b, , .</p><p> , (1), . . . , (n), </p><p>d(1),(2) + d(2),(3) + + d(n),(1) b .</p><p>. (Computer Science ) 3. NP- 9 / 42</p></li><li><p> (traveling salesman problem, TSP) n 1, . . . , n n(n 1)/2 , b. , ( ) b, , . , (1), . . . , (n), </p><p>d(1),(2) + d(2),(3) + + d(n),(1) b .</p><p>. (Computer Science ) 3. NP- 9 / 42</p></li><li><p> , ? , . TSP, b, ?</p><p>. (Computer Science ) 3. NP- 10 / 42</p></li><li><p> , ?</p><p> , . TSP, b, ?</p><p>. (Computer Science ) 3. NP- 10 / 42</p></li><li><p> , ? , .</p><p> TSP, b, ?</p><p>. (Computer Science ) 3. NP- 10 / 42</p></li><li><p> , ? , . TSP, b, ?</p><p>. (Computer Science ) 3. NP- 10 / 42</p></li><li><p> : b T , </p><p>(i ,j)T</p><p>dij b .</p><p> , , , . .</p><p>. (Computer Science ) 3. NP- 11 / 42</p></li><li><p> : b T , </p><p>(i ,j)T</p><p>dij b .</p><p> , , , . .</p><p>. (Computer Science ) 3. NP- 11 / 42</p></li><li><p> : b T , </p><p>(i ,j)T</p><p>dij b .</p><p> , , , .</p><p> .</p><p>. (Computer Science ) 3. NP- 11 / 42</p></li><li><p> : b T , </p><p>(i ,j)T</p><p>dij b .</p><p> , , , . .</p><p>. (Computer Science ) 3. NP- 11 / 42</p></li><li><p> , </p><p> (independent set problem) g g , , . (vertex cover problem) b, b , ( b , ). (clique problem) g g , .</p><p>. (Computer Science ) 3. NP- 12 / 42</p></li><li><p> , </p><p> (independent set problem) g g , , .</p><p> (vertex cover problem) b, b , ( b , ). (clique problem) g g , .</p><p>. (Computer Science ) 3. NP- 12 / 42</p></li><li><p> , </p><p> (independent set problem) g g , , . (vertex cover problem) b, b , ( b , ).</p><p> (clique problem) g g , .</p><p>. (Computer Science ) 3. NP- 12 / 42</p></li><li><p> , </p><p> (independent set problem) g g , , . (vertex cover problem) b, b , ( b , ). (clique problem) g g , .</p><p>. (Computer Science ) 3. NP- 12 / 42</p></li><li><p> , (longest path problem)? , s t, g . s t g .</p><p>. (Computer Science ) 3. NP- 13 / 42</p></li><li><p> , (longest path problem)?</p><p> , s t, g . s t g .</p><p>. (Computer Science ) 3. NP- 13 / 42</p></li><li><p> , (longest path problem)? , s t, g .</p><p> s t g .</p><p>. (Computer Science ) 3. NP- 13 / 42</p></li><li><p> , (longest path problem)? , s t, g . s t g .</p><p>. (Computer Science ) 3. NP- 13 / 42</p></li><li><p> (knapsack problem): w1, . . . ,wn N v1, . . . , vn N n . W g . , W , g . , O(nW ). , W , logW .</p><p>. (Computer Science ) 3. NP- 14 / 42</p></li><li><p> (knapsack problem): w1, . . . ,wn N v1, . . . , vn N n . W g .</p><p> , W , g . , O(nW ). , W , logW .</p><p>. (Computer Science ) 3. NP- 14 / 42</p></li><li><p> (knapsack problem): w1, . . . ,wn N v1, . . . , vn N n . W g . , W , g .</p><p> , O(nW ). , W , logW .</p><p>. (Computer Science ) 3. NP- 14 / 42</p></li><li><p> (knapsack problem): w1, . . . ,wn N v1, . . . , vn N n . W g . , W , g . , O(nW ). , W , logW .</p><p>. (Computer Science ) 3. NP- 14 / 42</p></li><li><p>, , , ., 12 IIIIIIIIIIII . , , , (unaryknapsack). , .</p><p>. (Computer Science ) 3. NP- 15 / 42</p></li><li><p>, , , .</p><p>, 12 IIIIIIIIIIII . , , , (unaryknapsack). , .</p><p>. (Computer Science ) 3. NP- 15 / 42</p></li><li><p>, , , ., 12 IIIIIIIIIIII .</p><p> , , , (unaryknapsack). , .</p><p>. (Computer Science ) 3. NP- 15 / 42</p></li><li><p>, , , ., 12 IIIIIIIIIIII . , , , (unaryknapsack).</p><p> , .</p><p>. (Computer Science ) 3. NP- 15 / 42</p></li><li><p>, , , ., 12 IIIIIIIIIIII . , , , (unaryknapsack). , .</p><p>. (Computer Science ) 3. NP- 15 / 42</p></li><li><p> . , W g . , (subset sum problem), W . , . ?</p><p>. (Computer Science ) 3. NP- 16 / 42</p></li><li><p> . , W g .</p><p> , (subset sum problem), W . , . ?</p><p>. (Computer Science ) 3. NP- 16 / 42</p></li><li><p> . , W g . , (subset sum problem), W . , . ?</p><p>. (Computer Science ) 3. NP- 16 / 42</p></li><li><p>NP- </p><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 17 / 42</p></li><li><p>NP- </p><p> (NP-) ( P)</p><p>3-SAT 2-SAT, Horn SAT</p><p>. (Computer Science ) 3. NP- 18 / 42</p></li><li><p>NP- </p><p> , , , , . . , . : , .</p><p>. (Computer Science ) 3. NP- 19 / 42</p></li><li><p>NP- </p><p> , , , , . .</p><p> , . : , .</p><p>. (Computer Science ) 3. NP- 19 / 42</p></li><li><p>NP- </p><p> , , , , . . , .</p><p> : , .</p><p>. (Computer Science ) 3. NP- 19 / 42</p></li><li><p>NP- </p><p> , , , , . . , . : , .</p><p>. (Computer Science ) 3. NP- 19 / 42</p></li><li><p>NP- </p><p> P NP</p><p>NP .P , .</p><p>. (Computer Science ) 3. NP- 20 / 42</p></li><li><p>NP- </p><p> P NP</p><p>NP .</p><p>P , .</p><p>. (Computer Science ) 3. NP- 20 / 42</p></li><li><p>NP- </p><p> P NP</p><p>NP .P , .</p><p>. (Computer Science ) 3. NP- 20 / 42</p></li><li><p>NP- </p><p> , P =NP, ? , , ( , )? (reductions), . , , , . , , , NP: , NP. , , P =NP, .</p><p>. (Computer Science ) 3. NP- 21 / 42</p></li><li><p>NP- </p><p> , P =NP, ? , , ( , )?</p><p> (reductions), . , , , . , , , NP: , NP. , , P =NP, .</p><p>. (Computer Science ) 3. NP- 21 / 42</p></li><li><p>NP- </p><p> , P =NP, ? , , ( , )? (reductions), . , , , .</p><p> , , , NP: , NP. , , P =NP, .</p><p>. (Computer Science ) 3. NP- 21 / 42</p></li><li><p>NP- </p><p> , P =NP, ? , , ( , )? (reductions), . , , , . , , , NP: , NP. , , P =NP, .</p><p>. (Computer Science ) 3. NP- 21 / 42</p></li><li><p>NP- </p><p> A B (f , h), f I A f (I ) B , h S f (I ) h(S) I , . . f (I ) , I . f h , B A.</p><p> If B</p><p> f (I )</p><p> S f (I )</p><p> f (I )</p><p>h h(S) I</p><p> I</p><p>. (Computer Science ) 3. NP- 22 / 42</p></li><li><p>NP- </p><p> A B (f , h), f I A f (I ) B , h S f (I ) h(S) I , . . f (I ) , I . f h , B A.</p><p> If B</p><p> f (I )</p><p> S f (I )</p><p> f (I )</p><p>h h(S) I</p><p> I</p><p>. (Computer Science ) 3. NP- 22 / 42</p></li><li><p>NP- </p><p>NP- </p><p> NP- (NP-complete), . NP-, !, . , .</p><p>. (Computer Science ) 3. NP- 23 / 42</p></li><li><p>NP- </p><p>NP- </p><p> NP- (NP-complete), .</p><p> NP-, !, . , .</p><p>. (Computer Science ) 3. NP- 23 / 42</p></li><li><p>NP- </p><p>NP- </p><p> NP- (NP-complete), . NP-, !</p><p>, . , .</p><p>. (Computer Science ) 3. NP- 23 / 42</p></li><li><p>NP- </p><p>NP- </p><p> NP- (NP-complete), . NP-, !, . , .</p><p>. (Computer Science ) 3. NP- 23 / 42</p></li><li><p>NP- </p><p> A B :</p><p> , B A. , A , , , B .</p><p> A B A B , , , . , NP- : , , , NP- . NP- P, P=NP.</p><p>. (Computer Science ) 3. NP- 24 / 42</p></li><li><p>NP- </p><p> A B : , B A.</p><p> , A , , , B .</p><p> A B A B , , , . , NP- : , , , NP- . NP- P, P=NP.</p><p>. (Computer Science ) 3. NP- 24 / 42</p></li><li><p>NP- </p><p> A B : , B A. , A , , , B .</p><p> A B A B , , , . , NP- : , , , NP- . NP- P, P=NP.</p><p>. (Computer Science ) 3. NP- 24 / 42</p></li><li><p>NP- </p><p> A B : , B A. , A , , , B .</p><p> A B A B , , , . , NP- : , , , NP- . NP- P, P=NP.</p><p>. (Computer Science ) 3. NP- 24 / 42</p></li><li><p>1 </p><p>2 NP- </p><p>3 </p><p>. (Computer Science ) 3. NP- 25 / 42</p></li><li><p> :</p><p> NP SAT 3SAT , .</p><p>. (Computer Science ) 3. NP- 26 / 42</p></li><li><p>3-SAT </p><p> 3-SAT , , ,</p><p>(x y z)(x y z)(x y z)(x y) ,</p><p> . g g . , , - .</p><p>. (Computer Science ) 3. NP- 27 / 42</p></li><li><p> I 3-SAT (G , g) .</p><p> G ( , ) , ; , , . g .</p><p>. (Computer Science ) 3. NP- 28 / 42</p></li><li><p> I 3-SAT (G , g) .</p><p> G ( , ) , ; , , .</p><p> g .</p><p>. (Computer Science ) 3. NP- 28 / 42</p></li><li><p> I 3-SAT (G , g) .</p><p> G ( , ) , ; , , . g .</p><p>. (Computer Science ) 3. NP- 28 / 42</p></li><li><p>x</p><p>y</p><p>z x</p><p>y</p><p>z x</p><p>y</p><p>z x</p><p>y</p><p>(x y z)(x y z)(x y z)(x y)</p><p>. (Computer Science ) 3. NP- 29 / 42</p></li><li><p> . S g G I . G g , I.</p><p>. (Computer Science ) 3. NP- 30 / 42</p></li><li><p> .</p><p> S g G I . G g , I.</p><p>. (Computer Science ) 3. NP- 30 / 42</p></li><li><p> . S g G I .</p><p> G g , I.</p><p>. (Computer Science ) 3. NP- 30 / 42</p></li><li><p> . S g G I . G g , I.</p><p>. (Computer Science ) 3. NP- 30 / 42</p></li><li><p>SAT 3-SAT</p><p> . , , - , . , ( ), , .</p><p>. (Computer Science ) 3. NP- 31 / 42</p></li><li><p>SAT 3-SAT</p><p> .</p><p> , , - , . , ( ), , .</p><p>. (Computer Science ) 3. NP- 31 / 42</p></li><li><p>SAT 3-SAT</p><p> . , , - , .</p><p> , ( ), , .</p><p>. (Computer Science ) 3. NP- 31 / 42</p></li><li><p>SAT 3-SAT</p><p> . , , - , . , ( ), , .</p><p>. (Computer Science ) 3. NP- 31 / 42</p></li><li><p> I I , (a1 a2 ak) 3 </p><p>(a1 a2 y1)(y1 a3 y2)(y2 a4 y3) . . . (yk3 ak1 ak) ,</p><p> {yi} . 3- I ., I I .</p><p>. (Computer Science ) 3. NP- 32 / 42</p></li><li><p> I I , (a1 a2 ak) 3 </p><p>(a1 a2 y1)(y1 a3 y2)(y2 a4 y3) . . . (yk3 ak1 ak) ,</p><p> {yi} .</p><p> 3- I ., I I .</p><p>. (Computer Science ) 3. NP- 32 / 42</p></li><li><p> I I , (a1 a2 ak) 3 </p><p>(a1 a2 y1)(y1 a3 y2)(y2 a4 y3) . . . (yk3 ak1 ak) ,</p><p> {yi} . 3- I .</p><p>, I I .</p><p>. (Computer Science ) 3. NP- 32 / 42</p></li><li><p> I I , (a1 a2 ak) 3 </p><p>(a1 a2 y1)(y1 a3 y2)(y2 a4 y3) . . . (yk3 ak1 ak) ,</p><p> {yi} . 3- I ., I I .</p><p>. (Computer Science ) 3. NP- 32 / 42</p></li><li><p>I I , {ai} (a1 a2 ak) , {yi}, . , , . a1, . . . , ak , y1 true, , y2 , ., (a1 a2 ak) , i ai . true y1, . . . , yi2, false. , .</p><p>. (Computer Science ) 3. NP- 33 / 42</p></li><li><p>I I , {ai} (a1 a2 ak) , {yi}, .</p><p> , , . a1, . . . , ak , y1 true, , y2 , ., (a1 a2 ak) , i ai . true y1, . . . , yi2, false. , .</p><p>. (Computer Science ) 3. NP- 33 / 42</p></li><li><p>I I , {ai} (a1 a2 ak) , {yi}, . , , . a1, . . . , ak , y1 true, , y2 , .</p><p>, (a1 a2 ak) , i ai . true y1, . . . , yi2, false. , .</p><p>. (Computer Science ) 3. NP- 33 / 42</p></li><li><p>I I , {ai} (a1 a2 ak) , {yi}, . , , . a1, . . . , ak , y1 true, , y2 , ., (a1 a2 ak) , i ai . true y1, . . . , yi2, false. , .</p><p>. (Computer Science ) 3. NP- 33 / 42</p></li><li><p> , , . , , S G (V ,E ) , , S V , G . , (G , g), (G , |V | g). , , . , G g .</p><p>. (Computer Science ) 3. NP- 34 / 42</p></li><li><p> , , .</p><p> , , S G (V ,E ) , , S V , G . , (G , g), (G , |V | g). , , . , G g .</p><p>. (Computer Science ) 3. NP- 34 / 42</p></li><li><p> , , . , , S G (V ,E ) , , S V , G .</p><p> , (G , g), (G , |V | g). , , . , G g .</p><p>. (Computer Science ) 3. NP- 34 / 42</p></li><li><p> , , . , , S G (V ,E ) , , S V , G . , (G , g), (G , |V | g). , , . , G g .</p><p>. (Computer Science ) 3. NP- 34 / 42</p></li><li><p> (complement) G (V ,E ) G = (V , E ), E , E . S G , S G . , G , G . , , (G , g) (G , g).</p><p>. (Computer Science ) 3. NP- 35 / 42</p></li><li><p> (complement) G (V ,E ) G = (V , E ), E , E .</p><p> S G , S G . , G , G . , , (G , g) (G , g).</p><p>. (Computer Science ) 3. NP- 35 / 42</p></li><li><p> (complement) G (V ,E ) G = (V , E ), E , E . S G , S G . , G , G .</p><p> , , (G , g) (G , g).</p><p>. (Computer Science ) 3. NP- 35 / 42</p></li><li><p> (complement) G (V ,E ) G = (V , E ), E , E . S G , S G . , G , G . , , (G , g) (G , g).</p><p>. (Computer Science ) 3. NP- 35 / 42</p></li><li><p> NP SAT</p><p> SAT . , N...</p></li></ul>