.


:




:

































 

 

 

 





 

. , , , , . , . , - . , .

, , -, . . , .

.

, (, , , ) , . , . , , , . , , , , . , . , , , , . [177].

, , ; , , , ( , - ); , , . , : ; : .

? , [178]. . , , .

, , . , , . , , ( -, ) . , , . .

. , : , M S , (, , ) . M S. , M S , . , : , M S S M. , - - , : M S, - - (S)r[M]i(S) (M)r[S]i(M). M S (S)r[M]i(S) (M)r[S]i(M).

- - . () , , .. . - , . : . , , .

. : , , . .

, , , , , .. , , . .

, . .

, , . , , , - [179].

, . : - . , , , . , . .

-, -, -, - . . , ; , , , . , , , . , , .

. , , , - .

, [180]:

1) , - , , - , .

2) -- .

3) , , , , .

4) - - - ( ) () - ().

5) , , : , , , .

6) ( ) ( , ) , , .

7) .

8) .

9) - -.

10) , [181].

11) .

, . , , , , . , -, . , , , , , () , . , . - . .

 

P NP

 

, (P)[182], , (NP)[183]. P=?NP.

, . P , . NP , . , .

, , : , ; : , . , , . . P, NP, , . .

NP , , . , . NP , . . .

- , , . , , . ( )[184], , , , .

. , , , . 3 1 , . , , . ( P) ( NP) [P] (NP) , .

, -. P=?NP , , , . -. . . , NP, , P, »-.

, --- . , P, , NP, - P NP. - .

- . »- NP. »- P. P. NP - . - , . / .

P=?NP : [P] (NP), [P] (NP). [P] (NP) , (NP) [P]. P=?NP P≠NP, . , [P] (NP), [P] , (NP).

 





:


: 2016-10-06; !; : 353 |


:

:

- , 20 40 . - .
==> ...

1591 - | 1546 -


© 2015-2024 lektsii.org - -

: 1.887 .