Эффективные алгоритмы, осень 2007: Подходы к решению NP-трудных задач

  • Published on
    08-Feb-2017

  • View
    263

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>/ 13: NP- </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (CS ) 13. NP- 1 / 58</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p> 1 </p><p> ( )</p><p>2 </p><p>3 3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 2 / 58</p></li><li><p>, 1.7n , n0.</p><p>The hardware approach: 10 . n0 + 4.The brainware approach: 1.3n. 2 n0.</p><p> , , .</p><p>. (CS ) 13. NP- 3 / 58</p></li><li><p>, 1.7n , n0.</p><p>The hardware approach: 10 . n0 + 4.</p><p>The brainware approach: 1.3n. 2 n0.</p><p> , , .</p><p>. (CS ) 13. NP- 3 / 58</p></li><li><p>, 1.7n , n0.</p><p>The hardware approach: 10 . n0 + 4.The brainware approach: 1.3n. 2 n0.</p><p> , , .</p><p>. (CS ) 13. NP- 3 / 58</p></li><li><p>, 1.7n , n0.</p><p>The hardware approach: 10 . n0 + 4.The brainware approach: 1.3n. 2 n0.</p><p> , , .</p><p>. (CS ) 13. NP- 3 / 58</p></li><li><p> NP- , , . NP- . . .</p><p>. (CS ) 13. NP- 4 / 58</p></li><li><p> NP- , , .</p><p> NP- . . .</p><p>. (CS ) 13. NP- 4 / 58</p></li><li><p> NP- , , . NP- .</p><p> . .</p><p>. (CS ) 13. NP- 4 / 58</p></li><li><p> NP- , , . NP- . .</p><p> .</p><p>. (CS ) 13. NP- 4 / 58</p></li><li><p> NP- , , . NP- . . .</p><p>. (CS ) 13. NP- 4 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 5 / 58</p></li><li><p> , ( ) .</p><p>. (CS ) 13. NP- 6 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 7 / 58</p></li><li><p> , , , , </p><p>. (CS ) 13. NP- 8 / 58</p></li><li><p> , </p><p> , , , </p><p>. (CS ) 13. NP- 8 / 58</p></li><li><p> , , , , </p><p>. (CS ) 13. NP- 8 / 58</p></li><li><p> , , , , </p><p>. (CS ) 13. NP- 8 / 58</p></li><li><p> , , , , </p><p>. (CS ) 13. NP- 8 / 58</p></li><li><p> NP- </p><p>NP- , </p><p> , , .</p><p>. (CS ) 13. NP- 9 / 58</p></li><li><p> NP- </p><p>NP- , </p><p> , , .</p><p>. (CS ) 13. NP- 9 / 58</p></li><li><p> NP- </p><p>NP- , </p><p> , , .</p><p>. (CS ) 13. NP- 9 / 58</p></li><li><p> NP- </p><p>NP- , </p><p> , , .</p><p>. (CS ) 13. NP- 9 / 58</p></li><li><p> NP- </p><p>NP- , </p><p> , , .</p><p>. (CS ) 13. NP- 9 / 58</p></li><li><p> , , , 1.619K , K .</p><p>. (CS ) 13. NP- 10 / 58</p></li><li><p> , (1, 2)- ( , T (K ) T (K 1) + T (K 2) + poly(K )) ( ) , , , :</p><p>(x a . . . ) (x b . . . ) (x c . . . ) . . .XXXXXXXXz</p><p>9x = 1 x = 0</p><p>(c . . . ) . . . (a . . . ) (b . . . ) . . .</p><p>. (CS ) 13. NP- 11 / 58</p></li><li><p> , (1, 2)- ( , T (K ) T (K 1) + T (K 2) + poly(K ))</p><p> ( ) , , , :</p><p>(x a . . . ) (x b . . . ) (x c . . . ) . . .XXXXXXXXz</p><p>9x = 1 x = 0</p><p>(c . . . ) . . . (a . . . ) (b . . . ) . . .</p><p>. (CS ) 13. NP- 11 / 58</p></li><li><p> , (1, 2)- ( , T (K ) T (K 1) + T (K 2) + poly(K )) ( )</p><p> , , , :</p><p>(x a . . . ) (x b . . . ) (x c . . . ) . . .XXXXXXXXz</p><p>9x = 1 x = 0</p><p>(c . . . ) . . . (a . . . ) (b . . . ) . . .</p><p>. (CS ) 13. NP- 11 / 58</p></li><li><p> , (1, 2)- ( , T (K ) T (K 1) + T (K 2) + poly(K )) ( ) , , , :</p><p>(x a . . . ) (x b . . . ) (x c . . . ) . . .XXXXXXXXz</p><p>9x = 1 x = 0</p><p>(c . . . ) . . . (a . . . ) (b . . . ) . . .</p><p>. (CS ) 13. NP- 11 / 58</p></li><li><p> , , (1, 1)-, .</p><p>. (CS ) 13. NP- 12 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .</p><p>)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . )</p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p>?</p><p>(x . . .) (x . . .) . . .)</p><p>(x) (x . . .) . . .</p><p>PPPPq</p><p>y (x . . . ) </p><p>(x y . . . ) (x y . . . ) . . .</p><p>(x y . . . ) (x . . . ) (y . . . ) . . .</p><p>(2, 2)- x</p><p>(2, 1)- x</p><p>. (CS ) 13. NP- 13 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 14 / 58</p></li><li><p> - , , .</p><p>. (CS ) 13. NP- 15 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 16 / 58</p></li><li><p> PPSZ- </p><p> , , , </p><p>. (CS ) 13. NP- 17 / 58</p></li><li><p> PPSZ- </p><p>, , , </p><p>. (CS ) 13. NP- 17 / 58</p></li><li><p> PPSZ- </p><p> , , </p><p> , </p><p>. (CS ) 13. NP- 17 / 58</p></li><li><p> PPSZ- </p><p> , , , </p><p>. (CS ) 13. NP- 17 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n}</p><p> 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,</p><p>I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p>PPSZ- </p><p>PPSZ-SAT(F )</p><p> {1, . . . , n} 2n/3, </p><p>I ,I , , </p><p> - , , </p><p>. (CS ) 13. NP- 18 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 19 / 58</p></li><li><p> , . , . , .</p><p>. (CS ) 13. NP- 20 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 21 / 58</p></li><li><p> , . t d (t, d) ( t d) , d t.</p><p>. (CS ) 13. NP- 22 / 58</p></li><li><p> , .</p><p> t d (t, d) ( t d) , d t.</p><p>. (CS ) 13. NP- 22 / 58</p></li><li><p> , . t d (t, d) ( t d) , d t.</p><p>. (CS ) 13. NP- 22 / 58</p></li><li><p> F 3- (t, d) 3d :</p><p> t F , C = (x1 x2 x3) , t x1, x2 x3 </p><p>. (CS ) 13. NP- 23 / 58</p></li><li><p> F 3- (t, d) 3d :</p><p> t F , C = (x1 x2 x3)</p><p> , t x1, x2 x3 </p><p>. (CS ) 13. NP- 23 / 58</p></li><li><p> F 3- (t, d) 3d :</p><p> t F , C = (x1 x2 x3) , t x1, x2 x3</p><p>. (CS ) 13. NP- 23 / 58</p></li><li><p> F 3- (t, d) 3d :</p><p> t F , C = (x1 x2 x3) , t x1, x2 x3 </p><p>. (CS ) 13. NP- 23 / 58</p></li><li><p>3n-</p><p>Simple-3-SAT(F )</p><p>, (0n, n/2),(1n, n/2)</p><p> Simple-3-SAT 3n, n = n(F ) </p><p> F .</p><p>, , .</p><p>. (CS ) 13. NP- 24 / 58</p></li><li><p>3n-</p><p>Simple-3-SAT(F )</p><p>, (0n, n/2),(1n, n/2)</p><p> Simple-3-SAT 3n, n = n(F ) </p><p> F .</p><p>, , .</p><p>. (CS ) 13. NP- 24 / 58</p></li><li><p>3n-</p><p>Simple-3-SAT(F )</p><p>, (0n, n/2),(1n, n/2)</p><p> Simple-3-SAT 3n, n = n(F ) </p><p> F .</p><p>, , .</p><p>. (CS ) 13. NP- 24 / 58</p></li><li><p>3n-</p><p>Simple-3-SAT(F )</p><p>, (0n, n/2),(1n, n/2)</p><p> Simple-3-SAT 3n, n = n(F ) </p><p> F .</p><p>, , .</p><p>. (CS ) 13. NP- 24 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 25 / 58</p></li><li><p> k-SAT</p><p> k-SAT</p><p> ( , covering code) : (2 2/(k + 1))n</p><p> , .</p><p>. (CS ) 13. NP- 26 / 58</p></li><li><p> k-SAT</p><p> k-SAT ( , covering code)</p><p> : (2 2/(k + 1))n</p><p> , .</p><p>. (CS ) 13. NP- 26 / 58</p></li><li><p> k-SAT</p><p> k-SAT ( , covering code) </p><p> : (2 2/(k + 1))n</p><p> , .</p><p>. (CS ) 13. NP- 26 / 58</p></li><li><p> k-SAT</p><p> k-SAT ( , covering code) : (2 2/(k + 1))n</p><p> , .</p><p>. (CS ) 13. NP- 26 / 58</p></li><li><p> k-SAT</p><p> k-SAT ( , covering code) : (2 2/(k + 1))n</p><p> , .</p><p>. (CS ) 13. NP- 26 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 27 / 58</p></li><li><p> .</p><p>. (CS ) 13. NP- 28 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 29 / 58</p></li><li><p>Dynamic-TSP(G )</p><p> S {2, . . . , n} i S Opt[S , i ] . 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}</p><p>. (CS ) 13. NP- 30 / 58</p></li><li><p>Dynamic-TSP(G )</p><p> S {2, . . . , n} i S Opt[S , i ] . 1, S {i} i</p><p> :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}</p><p>. (CS ) 13. NP- 30 / 58</p></li><li><p>Dynamic-TSP(G )</p><p> S {2, . . . , n} i S Opt[S , i ] . 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}}</p><p> :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}</p><p>. (CS ) 13. NP- 30 / 58</p></li><li><p>Dynamic-TSP(G )</p><p> S {2, . . . , n} i S Opt[S , i ] . 1, S {i} i :Opt[S , i ] = min{Opt[S {i}, j ] + d(i , j) : j S {i}} :min{Opt[{2, . . . , n}, j ] + d(j , 1) : 2 j n}</p><p>. (CS ) 13. NP- 30 / 58</p></li><li><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p> , 1.99n. , 2n, .</p><p>. (CS ) 13. NP- 31 / 58</p></li><li><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p> , 1.99n. , 2n, .</p><p>. (CS ) 13. NP- 31 / 58</p></li><li><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p> , 1.99n. , 2n, .</p><p>. (CS ) 13. NP- 31 / 58</p></li><li><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p> , 1.99n.</p><p> , 2n, .</p><p>. (CS ) 13. NP- 31 / 58</p></li><li><p> Dynamic-TSP poly(n)2n.</p><p> 1962- .</p><p> , 1.99n. , 2n, .</p><p>. (CS ) 13. NP- 31 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 32 / 58</p></li><li><p> .</p><p>. (CS ) 13. NP- 33 / 58</p></li><li><p> k- (table-k-SUM problem) , k m , S .</p><p> mk .</p><p> 2- , x , S x . O(m logm) .</p><p>. (CS ) 13. NP- 34 / 58</p></li><li><p> k- (table-k-SUM problem) , k m , S .</p><p> mk .</p><p> 2- , x , S x . O(m logm) .</p><p>. (CS ) 13. NP- 34 / 58</p></li><li><p> k- (table-k-SUM problem) , k m , S .</p><p> mk .</p><p> 2- , x , S x . O(m logm) .</p><p>. (CS ) 13. NP- 34 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :I k/2 A ( )</p><p>I k/2 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :</p><p>I k/2 A ( )</p><p>I k/2 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :I k/2 A ( )</p><p>I k/2 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :I k/2 A ( )</p><p>I k/2</p><p> 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :I k/2 A ( )</p><p>I k/2 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> k-</p><p>Table-k-SUM-Alg(A[k ,m], S)</p><p> B[2,mk/2] :I k/2 A ( )</p><p>I k/2 2- B</p><p> Table-k-SUM-Alg O(mk/2 logm) O(mk/2) .</p><p>. (CS ) 13. NP- 35 / 58</p></li><li><p> 1 </p><p> ( )2 </p><p>3 </p><p>3-k-</p><p>4 </p><p>5 </p><p>6 3-</p><p>7 3-</p><p>. (CS ) 13. NP- 36 / 58</p></li><li><p> (subset-sum problem) , n , B .</p><p>Subset-Sum-Alg({bi}1in, B)</p><p> : b1, . . . , bn/2 bn/2+1, . . . , bn , , 2-</p><p>. (CS ) 13. NP- 37 / 58</p></li><li><p> (subset-sum problem) , n , B .</p><p>Subset-Sum-Alg({bi}1in, B)</p><p> : b1, . . . , bn/2 bn/2+1, . . . , bn , , 2-</p><p>. (CS ) 13. NP- 37 / 58</p></li><li><p> (subset-sum problem) , n , B .</p><p>Subset-Sum-Alg({bi}1in, B)</p><p> : b1, . . . , bn/2 bn/2+1, . . . , bn</p><p> , , 2-</p><p>. (CS ) 13. NP- 37 / 58</p></li><li><p> (subset-sum problem) , n , B .</p><p>Subset-Sum-Alg({bi}1in, B)</p><p> : b1, . . . , bn/2 bn/2+1, . . . , bn , , </p><p> 2-</p><p>. (CS ) 13. NP- 37 / 58</p></li><li><p> (subset-sum problem) , n , B .</p><p>Subset-Sum-Alg({bi}1in, B)</p><p> : b1, . . . , bn/2 bn/2+1, . . . , bn , , 2-</p><p>. (CS ) 13. NP- 37 / 58</p></li><li><p> Subset-Sum-Alg 2n/2 .</p><p> , . , 1.99n, .</p><p>. (CS ) 13. NP- 38 / 58</p></li><li><p> Subset-Sum-Alg 2n/2 .</p><p> , . , 1.99n, .</p><p>. (CS ) 13. NP- 38 / 58</p></li><li><p> Subset-Sum-Alg 2n/2 .</p><p> , .</p><p> , 1.99n, .</p><p>. (CS ) 13. NP- 38 / 58</p></li><li><p> Subset-Sum-Alg 2n/2 .</p><p> , . , 1.99n, .</p><p>. (CS ) 13. NP- 38 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G</p><p> A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p>3-</p><p> 3- (3-clique problem) 3- ( ) .</p><p>Matrix-Clique(G )</p><p> A G A3</p><p> , </p><p>. (CS ) 13. NP- 39 / 58</p></li><li><p> O(nw ), w 2.376 (matrix multiplication exponent).</p><p> : Ak [i , j ] k i j G ( )3- 3 A3 </p><p>. (CS ) 13. NP- 40 / 58</p></li><li><p> O(nw ), w 2.376 (matrix multiplication exponent).</p><p> : Ak [i , j ] k i j G ( )3- 3 A3 </p><p>. (CS ) 13. NP- 40 / 58</p></li><li><p> O(nw ), w 2.376 (matrix multiplication exponent).</p><p> : Ak [i , j ] k i j G ( )</p><p>3-