Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v13(1-4)/potseluevskaya-455-476.pdf Дата изменения: Thu Jul 1 08:48:12 2010 Дата индексирования: Tue Oct 2 00:34:36 2012 Кодировка: Поисковые слова: m 5

. .


( ) NP- . , , , , . , , , . , , . , . . . . [13] NP-, . ., . ., . . . . [14], , [4] .


456

. .

1.
1.1. , ()
. 1 , . . . , , 1 1 : ( 11 )( 1 ) . . . ( 1 ) , ( , , . . . , ). . 1 = 1 , . . . , = , ? , NP-. .

1.2.

-

. 1 , . . . , , . . 1 = 1 , . . . , = , ? - NP- 3. NP-, =3 , . = 2 2- . 2-, . 2- . ( 1 , . . . , ). ( 1 , . . . , ) , ( 1 , . . . , ), ( 1 , . . . , ), ( 1 , . . . , ) ( ): Ї( + + ) ( ) ( ) ( ) 0. , , () ().




457

1.3.

-

. 1 , . . . , , . . . 1 = 1 , . . . , = , , ? - NP- 3. = 2 2- .

1.4.

-

. 1 , . . . , , . . 1 = 1 , . . . , = , , ? - NP- 3. = 2 2- .

1.5.

-

. 1 , . . . , , . . 1 = 1 , . . . , = , , , , ? - NP- 3. = 2 2- . = 2. , 2- . NP-.


458

. .

1.6. 2-
. 1 , . . . , , 2 , . . 1 = 1 , . . . , = , ? , .

1.7. ( , )-
. 1 , . . . , , . . 1 = 1 , . . . , = , ? , (3, 4) , NP. , ( , )- . , [5]. 0 0 , ( 0 , 0 )- . ( 0 + 1, 0 + [ 0 / 0 ])-, [ ] . , ( , )- = 2 -1 . [5] = 5, = 11. , < 4.

1.8.
. 1 , . . . , , , , , : ( 1 Ї 2 Ї ) ( 1 Ї 2 Ї ) . . . ( 1 Ї 2 Ї ), ( , , . . . , ). . 1 = 1 , . . . , = , ?




459

. ( 1 , . . . , ). ( 1 , . . . , ) , ( 1 , . . . , ), ( 1 , . . . , ) ( ): ( Ї ) ( ) ( ) 0. , , .

1.9.
. 1 , . . . , , , , , , : ( 1 2 ) ( 1 2 )...( 1 2 ), ( , , . . . , ). . 1 = 1 , . . . , = , ? . ( 1 , . . . , ). ( 1 , . . . , ) , ( 1 , . . . , ), ( 1 , . . . , ) ( ): ( Ї ) ( ) ( ) 0. , , .

1.10.
. 1 , . . . , , , : ( 1 1 +... + 0 )( 1 1 + . . . + 0) . . . ( 1 1 + . . . + 0 ), ( , ,..., ).


460

. .

. 1 = 1 , . . . , = , ? , , (2).

1.11.

-

= 1, . . . , ( ). - 1 () 2 () . . . () 1 , , , . 1 = 1 , . . . , = , - ? , - -. [11] . 1. - , , , : (0, . . . , 0) = 1; (1, . . . , 1) = 1; ; ; ; . - NP--

.

, , , , .




461

1.12.
, ( -) . : 1 = 1 , . . . , = , , , . , , ( ) , ( ) ( ). , .

2.
( , ), : : ; , : ; : . . , , . .


462

. .

2.1.
, , ,..., {0, 1}. 1 . : : = , , = ( 1 , . . . , ) 1 . : ( )=
=1

( ),

( )=
=1

,

( ); ; ;

,

: min {0,1} ( ) , ( ) = 0 {1, 2, . . . , } . 1 , . . . , . ( ), ( ). [14] . : DPLL PPSZ-. 2.1.1. DPLL- DPLL- , [3] , [2]. , , . .

1- ( )= , 1,

, Ї .




463

DPLL- . 1. 1) , , . 2) , . 3) , , . [ ] [ Ї ], [ ] , 1. [ ] [ Ї ]. , , Ї , ( , ). , . , : , (, ); ( ). 1 . , . , , , , , [ ] [ Ї ]. ( ) . , ( ) 1: ( ) 2 ( - 1) + ( ).


464

. .

[6, 7] . . , , . , 1 , . . . , , : 1 , . . . , . 1, . . . , ( 1 , . . . , ) - 1 .
- =1

=1

(0, +). 1 ( ) , . 1.505 ( ) 3- [6], , . , DPLL-. 1) . , , {0, 1}, . 2) . , , =. 3) . . , . 2 ( 22 ) (Ї 2 ) 2 ( 22 2 , 1 .

),

=






465 ,

4) . .



5) . () , [ ] , , [ ]. 6) . , . , ( , ) ( , Ї ) ( , Ї) ( Ї , ) . , , ( , ), , (,
+1

),



[{

(,

+1

)}].

7) . , , , +1 , . . : , . : , , . -, [16] DPLL-. , , . 1+
=1

2



( ),

,



, , : =
=1

.


466

. .

2.1.2. PPSZ- , , [8]. . , . , - . - , . -, = 3, , . 1) {1, . . . , }. , -

2) 1 (1. ), 2 /3. , ( ) . 1, ; , . 22 /3 ( ). , , 1 , , . , , .

2.2.
1 , . . . , {0, 1}. -




467

. : : = , , = ( 1 , . . . , ) 1 . : ( )=
=1

( ),

( )=
=1

,

( ); ; ;

,

: min {0,1} ( ). , , , (. [4]). , , . 2.2.1. , , , , : , , . 2- , - (2 - 2 ) , . , = 3 (4/3) , , 3-.

1- , ( )= 1,

, Ї .


468

. .

( ) , . , , ( ) , ; ( ) . 2 1) ( ) : ) ( ). ) , . ( ) : . ( ) , . , ( := + 1). , . 2) . 2 ( ) = 1 ( ) = 2 2 2- [9]. 2 ( ) = (2 - 2 ) ( ) = 3 (2 - 2 ) - [12]. -. , , . , 1/ , , . , -




469

, , . , [0, . . . , ]. = 0 ( ) . , 0 < < , - 1 1/ + 1 1 - 1/ . = 0, 1. , , , 0 . , . 1. 2 exp - () 2
,() =0

,



.

. , . . ( ) , . 2 . , ( , ) , ( ) . , : =
=0

2

,()

, ( ) . , (1 - )
()

= exp( ( ) ln(1 - )) exp(- ( ) ) = = exp (- ( ))
=0

2

,()

.

.


470

. .

2.2.2. , , ( RW Random Walks) , RWB Random Walks with Back button. RWB , . . RW, RWB ( ) ; ( ) , , . RWB , RW; , RWB ; . , RWB ( , ). , RWB : 1) ( ) : ) . ) . ( ) : , . 1 - . 2) . . RWB , RW ( 2) . RWB , . , . RW,




471

. , , . = 0 . RWB: , ; 1 - . () , , 0 , . 2. RWB exp - () 2
() ,() =0

.

1. [14] , 0 , , 1 . 2

2.3.
, , , , . , , . : : = 1 , , = ( 1 , . . . , ) . : ( ) =
=1

( ),


472

. .

( )=
=1

,

( ); ; ;

,

. : min ( ), ( ) = 0 {1, 2, . . . , }. , , , . . , , . . . [4].

- , + , Ї ( )= 1, ,

2.4.
. . (UniSAT): , , : = 1 = ( 1, . . . , ) . : ( ) =
=1

( ),

( )=
=1

,

( ); ; ;

,

- , ( )= + , Ї 1, ,




473



. : min ( ). {0, 1} . . [4]. , , . , , , , . , , , , .

3.
, , . , , DPLL-. . , 2003 (Survey Propagation SP) [1], . SP- , : , . , , ,


474

. .

, . SP- . (Warning Propagation WP) (Belief Propagation BP). , . , (. . 1 [10]).

. 1. ( ).

, . , http://www.satlive.org.




475

4.
, 60­70- , . , . . . .


[1] Braunstein A., Mezard M., Zecchina R. Survey propagation: An algorithm for Satisfiability // Random Structures and Algorithms. 27. 2005. P. 201­226. [2] Davis M., Logeman G., Loveland D. A machine program for theoremproving // Communications of the ACM. 5 (7). 1962. P. 394­397. [3] Davis M., Putman H. A computing pro cedure for quantification theory // Journal of the ACM. 7 (3). 1960. P. 201­215. [4] Du D., Gu J., Pardalos P. M. Satisfiability problem: theory and applications // Pro ceedings of a DIMACS workshop. March 11­13, 1996. [5] Dub ois O. On the , -satisfiability problems and a conjecture of Tovey // Discrete Appl. Math. 1990. V. 26. P. 51­60. [6] Kullmann O. New metho ds for 3-SAT decision and worst-case analysis // Theoretical Computer Science. 223 (1­2). 1999. P. 1­72. [7] Kullmann O., Luckhardt. Deciding tautologies: Algorithms and their complexity http://www.cs.toronto.edu/~kullmann prop ositional / Preprint.

[8] Paturi R., Pudlak P., Saks M. E., Zane F. An improved exp onentialґ time algorithm for k-SAT // Pro ceedings of FOCS'98. 1998. P. 628­637.


476

. .

[9] Papadimitriou C. H. On selecting a satisfying truth assignment // Pro ceedings of FOCS'91. 1991. P. 163­169. [10] Malik S., Zhang L. Bo olean satisfiability. From theoretical hardness to practical success // Communications of the ACM. No. 8. Vol. 52. 2009. [11] Schaefer T. J. The complexity of satisfiability problems // Pro ceedings of the 10th ACM Symp osium on Theory of Computing. 1978. P. 216­226. [12] Shoning U. A probabilistic algorithm for k-SAT and constraint Ё satisfaction problems // Pro ceedings of FOCS'99. 1999. P. 410­414. [13] . ., . . NP- . // . . 4, . 2. 1997. . 165­193. [14] . ., . ., . ., . . // . VI. . . . . 277. .: , 2001. [15] . ., . . // . . 1. 1995. [16] . . - // . . 12. 2008. . 351­362.