P   NP: ,    
 


    ,  P    NP.

. ,       ,      ,      :   .

      ,    P  NP         ,         .

 P vs NP     ,   ,  ,     ,      ;

  ,   ,      . ,  ,   ,   ,   . ,   ,      .  ,     ,     ,    .





 

P   NP: ,    





 I.   





 1. : ,   


1.1.     

 1900         ,    ,    23 , ,   ,         [1].      ,  ,   :  ,         .  ,      , :        [2]. ,       ,      .

     , ,     .      ,       .    ,  2+2=5. .   :       ,   ,       [3].

               .       :

:     ,     ,      .  ,  ,   .       [4].

 : ,                   ,   .    .

 :   ,   ,       , ,       0=1.       [1][3].

   (Entscheidungsproblem):  ,   ,       ,    . ,  -,     [5].

 ,   .      ,  ,       .

, ,       ,  ,         .       .   ,             ,        .  ,        ø  ,    .

1.2.  ø  :  

         ,     ø  ,       .  1931    ,   ,         , ,  , ,          [6].

 ,    ,    

  ø   ,    ,  ,    (       -),    [7].     ;    .

    . ø ,        ,     :       [8].   -,   :    .     ,     .       . ,     ,   .      ,  ,     .   (    ),     [9].

      . ,            .     ,    ,     .

 ,      

    ,    . ø :          [10].

       ,          0=1 ø :        .    ,     .         .    . ,       ,  ,      ,     .

     ,       .      .       ,   ,        ,    ,    -   .

    ,     ,  .                ,         .    ,    ,       ,   ,      . ,    ,             .

        ø.   ,         ,   .           .       ,   ,   ,    .

        . ,               .           ,    .  ,  ,    ,  .

1.3.   :  

        ,     .  1936    ,         ,      ,       [11].

               ,      ,    .    ,  ,   -       [12].    ,       ,  ,     ,    .

  ,         ,   :  ,       [11].

  Entscheidungsproblem    ,     ,    ,      ,   -      [13].    ,   ,     ,    .     .

   ,      .      ,    [14].

,  ,     HALT(P, I) .       P   I,    :    .   ,         .

  -.   BUSTER.       Q   :

  HALT(Q, Q).   :    Q,     ?

   , ,        .

   ,  ,  BUSTER  .

 BUSTER    .     ,   .

  BUSTER   .   BUSTER(BUSTER).  :   BUSTER(BUSTER)?

 .  : , .  BUSTER,   ,    .  .  .  : ,  .  BUSTER  .   .

,    ,   ,      ,      [15].    .        .

        . ,   ,   HALT .   .  ,  BUSTER  .    HALT     .   .

 ,      ,     ,        .  ,    ,    ,   ,  .  .

,    ,    .         ,    ,    ,     [12].     ,       .    .

       . ,     (ø),      ()    ,      ,     .

1.4.  P vs NP:  

 ø                ,    P vs NP   .   ,      .    :       .   ,      ,    [16].

  P vs NP     1970- ,                .  P (polynomial time)   ,    ,   .          .  ,  .  ,     ,        P [17].

 NP (nondeterministic polynomial time)   ,       ,   .         [18].   (  ,    ),    ,     ,      NP [19].

 P = NP?     :       ,       ?       ,    ,   ,    ?

  : NP-

 1971     ,  ,          [20].  ,       (SAT)  NP-.  :  - -     - SAT,      NP   P. .  .

    .    1972     21  ,   NP-    SAT [21]. ,  ,  ,          .          .      P vs NP         ,        2000       [16].

    .

  ?     

    P vs NP     ,        ,  ,           .

 1975   ,       ,             [22].  ,          ,    P = NP.    ,     ,   P ? NP.

   ?  ,          ,   ,       ,       P vs NP.       ,        ,    .   ,    A  ,    B   [23].

  ,   ,      ,     .   ,      ,  : ,       .

  ,     :            

   ,  ,   ,    .       ,    ,      .     .

        ,      -  [22].    ,   !    ,      .           : ,         ?     ,      .

    .             ,  ,         .     P     A ( P^A)   ,      ,       ,   A [22].

   ,     .

    ,       ,         [23].   ,  P ? NP,     (  ,     ),       ,         ,   ,    .

  ?   ,  ,       .     P = NP (           ).    P ? NP (    ,    ,  ) [22].

     ,  P = NP,         ,      .  :   ,  P ? NP,    ,   . .

 ,    ,          ,    [23].    ,      , ,      .   ,         .

        ,  ,       .       .  ,    ,    P vs NP        1975      ,    .

        .          .      .

    ?

      ,   ø  :       . NP-   -.      (  ),      ,   ,      .

       .  ,             , ,    .  ()    ,   ,    .           .

 P vs NP, ,      ,       ,      .    ,       .

1.5.  :     

,   ,  ,  . ø:       ,    [7]. :   ,     [11]. :  ,        ,     , ,  [22].

  ,     ,    ,    .  ,     ,       ? ,         , ,         ?   ,   .

    .

 : .    :  , ,  .    .  ,  ,     ,   .  .          ,   .      ,    ,       .

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

 :   .    .  .  .  .       -.    ,   - ,    ,      [24]. ,  , .     .

 : , , .  ,   .   .  .        ,    .        ,    ,         [3].

  , .    .     .  -    .



     ?         ,       ,   ,    .

ø    .  ,    ,            [9].  .  ,      ,   ,       .     .    ,    .

  - BUSTER,     HALT.   BUSTER,    HALT    .  ,         [14].  HALT     .    .

P vs NP.    ,     . NP-   ,      ,    (  ). P-   ,        (     ).     :        .  :    ,  -    [25].

  ,   ,  :          ?  ,       ,       .     .        .     ,        .

       .      :

    (     );

 -     (  -   ,  );

    (    );

    (    ).

,       ,     ,  .     ,   ,  ,       [26].   P vs NP       ,     : ,    ,  ,    .

   ,      ,         .    ,         ,    .

  ,     ,     [22].      ,  .        .  ,      ,    .

     XX    :     ,   .    (ø),  ()  ,      (P vs NP).  ,    ,  ,     .    ,  ,       .

1.6.   :     

,   .     ,        .    ? ø,    P vs NP    ,   .    . ,    ,  .

    

  ,          . -        .      .    :  :  ,    .

   XX     .   :     ?  :   ,    ,    ?

   1901  ,        :   ,   ,    ,    [27].          .   :      Principia Mathematica,    ,  1+1=2,     [28].      ZFC,        ,        ,    [26].

  ,   :      ?  , ,      ?   ,      ,              ,     ,   ?

- :   .       ,  ,    [29]. ø             [8].     ?  ,     .  :  .   ,  ,        .  .

,  ,    .                .         .

 1922    ,        ,        [30].   :    ,        ,           .     ,    .     .

     :     ,         .  ,    ,  .          .

    ,  

      ,    .  ,  ,     .         ,   [31].

      ,       .   ,  .     ,      :   ,      .   ,    .

 ,     ,   .         ,    .

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

P vs NP   

      P vs NP     ,       .      ,     ,     .    ,        ,    ( ),  ,     ( ).

  ,  .  ,  P ? NP,   ,    ,    ,     .    ,      .         ZFC        .

       ,     ,         ,        .    .       .

  ,     .      : , , , .     ,    .

         ,      .         ,      ,  ,  ,  .      ,      ,   .

,   ,    .        .     ,     ,  .




 2.     


2.1.    :   

    ,  ,             .      ,       :      .

     ,      ,   .      :  ,   ,   ,   ,   ,    [32].    ,  ,     ,   .    .  ,   .

   -.      ,       ,    .      .      .     ,  ,       [33].

          ,     .         .     , ,    .      ,    .   ,        .

   ,       .      [34].    ,    :     ,     .       : ,   ,  ,   .

 :      .      ,  ,        [35].

    ,    .   ,   :    ,    ,       .    .

   :      .      ,   ,     . ,     ,  :        .  :     ,        ,    ,    ,     . ,       .        :     ,    .            [40].

    ,  .      ,      .   ,        .     ,  .

         ,       .     .

  XIX     ,     -:      [36].

     ,      ,    .       ,       .  ,  ,   .    ( ),    ( ).           ,    [37].

  .  ,   ,    ,    -  [38].  ,  ,          [39].    ,  ,    ,        ,     .

   ,     .   .    ,     .  ,      ,   .   ,   ,      .

       .   XX      .  ZFC  .    philosophia non grata    ,   ,   .

              .

-,        .       .        .   ,      .   .  ,      ZFC, :            ,      .  ,     [26].    :   ,   .

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

-,         .     .       . ,  ,      .

      ,   ,  , .              .          ,    ,  ,     .

         ,      . ø, ,  P vs NP     ,   ,     .

  ,       ,       P vs NP     .  ,          .   , ,         ,    .

2.2.  :   

   ,    -,        .  ,               . ,   ,   ,         .

   :     

    . ,     300    ,    :  ,       [41].         .   .            ?      ,   . ,   ,      .

  ,   .           :  ,    ,  .      XIX   ,      ,       ,    [42]. ,     ,   ,     .

     .    : ,     ,      ,  : ,       ,  .      .  ,        [43].

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

       ,        , ,      [3]. -         .  , ,  .   .         ,   ,   ,   .

      ,  ,  .  ,     .    ,   ,          .   ,     ,                  [44].

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

   ,       ,     .    :   ?

    .     .        .       .

 ,    ,  ,    ,    .             .         -   ,      .

ZFC    . Ÿ    , ,           ,      [26].       . Ÿ           ,   [45].

    .           .  ,   .        ,    ,     ,   [46].   ,  .           ,    ,       .     ,     .

 ,     ,    ,   .        .

       ,     ,    .

  ,        .    , ,  .

  ,         .       , ,  .  ,   .

     :    .  ,  ZFC   ,   , .   ,       ,    . ,    ,            ,   .

    .      . P vs NP       ,      ,         .  ,  ,    .

2.3. -     

       ,  -      .     .    ,         .

, ,   ,       ,                [47].    .   ,  ,      ()  ,     ( ),         .

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

            . ,  ,  ,    ,    ,  - .     .     ,   .

,       ,   ,    .     , , ,     ,  ,  ,   ,       ,    .

        ,        .   ,       .  .

    .     (),      ,   ,       ( ).      ()    ,        ( ).      (),             ( ) [19].

    .   -,     -.   ,    .    :        .

 -    ,    ,      .   ,    ,     .

   .

  (- ): ,       . .  ,   ,     .

  ( ):    .    ,  .              ,     ,      . ,       [48].

  :     .  :    .  .  .          .     ,  , , , .

     . ,     ,     ,     ,  ,  .     ,      .    ,   .

,     ,    .        .      .      ,    ,    .

-       .        :      酻     ,   ,    .                ,    ,    .

         ,      -     .     .    .    ,     (, P vs NP)   ,      .

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

      .                .      ,    (,   P  NP)      .

,           ,        , , .  ,          .    ,      .     ,            .

     P  NP. P-  NP-  -    :       (),  - .   ,   P    ,   NP  .   -      .        .

 P vs NP      ,   .   ,        ,       [49].

 : ,     - ,    .                   ,     .             ,    (,   )    (,    ) [50].

        -     ,    , , .          . ,      .

2.4.  :  

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

    ,       .   :       ,           [51].  .      .    ?

       ,     .     ,     -.   :  ,  ,      ,               .

 ,    .      ,       .      , ,   .           .                .             [26].

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

 -,        

  ,    ,     -,   1924  [52].          ,         ,        ,     .  .  .   .          .

  .    ,   ZFC.     ,     ,         .

, ,    ,  .            [53].    .       -,    .    ,    ,   .

          ,    ,  ,        .  -      .  .    ,     ,         ,      .

   ,     

        ,         .  1904   ,     ,       ,  ,        [54].

    .  ,  ,             ,      [45].    :    ,      .         .  .    .

   .  ,       ,  .               ,      .        ,      [55].

  .  ,     .  ,            .   :        ,          .       ,       ,      [51].

       ,         ,     .      ,   , ,   .

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

  :   .      ,  ,   ,  ,   .       .    .       ,    ,   ,     .

,    ,       .   ,        , ,   ,            ,    ,     [56].

    .     ,     ,       ,      ,  P, ,   NP.

P vs NP     ,     ,    .    ,           .                  .  : .         .    ,    .

    ,          ?         ,     ?

   .    .   : ,  ,   ,    ,   .         ,  P ? NP   .         .

2.5. :      

 ,  :        .

   . ,    ,     .  :   X,   P.    ?     X?   ,   ?     , , , ?  .    :   ,    ,   .  .

    .    X.   ,   .     .   ,        .     :    [57].

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

,    ,    .     .    ,        ,  .              ,  ,  ,      ,     .                [58].

  ,           .    :   ,   .    :     ,    [59].

       .        . -         . ,   ,              .

 ,  ,   .          : ?.    ,    ,   ,     .   :      .        .

         P vs NP.   .

 P    ,      ,      [17].  NP    ,      ,     , ,  ,    [18].       .   ,   ?.

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

 ,   ZFC,     .       (  ).  ,    -     ,       [60].

 :   .          .  ,       .      .     ,      ,      .

    ,  ,    P vs NP     ,    .       ,      ,     .    :      ?       ,   ,  ,  ,    ,      ?

  ,       ,     ,  ,   .    P vs NP ,      ,   ,      .        ,       .

2.6.      

    .      .   .     .        . -     .      .

  : ?  ,    ,         ,   , , ?   ,   ,     ,     ?

 ,       .

 :  

   .    , ,  , , , .      .        .   , , .

,    ,  .     ,  , ,   ?   ,   :  ,  ,      .     - , , .  ,  ,  .   ,     [61].

       .  ,    .   ,     .       .    ,   .  ,      ,  ,   .

 :  

     . ,   ,   ,     ,   :       . , , .

   .   .  ,    .  ,    .  ,     .  ,  ,    .

,    ,   .  ,       ,         ,   .        ,   ,  ,    [62].

 ,   ,   .  ,    .  ,  .    ?   :     .       .

 :   

    ,   .       -.    .   .     ,  .

       .     .  .  .      - ,  : , , . ,    ,      [44].

    ,    .                .      ,   .      .      .

  ,      .   .   .       ,       .    ,  ,  .  ,              ,    ,    [63].

 :   

 ,     .     ,    .     .     ,     .    .         .

  :    ,      ?    ,        ?    [64].

     .          P vs NP.          .   ,    .              ,    .



      .         , ,   .      ,    , ,   .          ,   -     .

     . . .  P vs NP,      ,      ,       .

     ,                 ,  ?

       ,       .    ,     ,      .  ,         ,      ?.  ,    .

     ,        .     ,   ,              .




 3.    ( )


3.1.  

   ,   :   ?   ,    :         .      .     ,   - ,   .  ,    [65].

      .    .    ,   .     ,     .       .

    ,       :         .       - ,            ,    .  .    ,     [66].

     ,       :   ,  ,  ,   .     ,        .

   ,    ,       .      .

      , :    ,  ,   .         .  ,      : ,   ,   ,   .

 :      ,     .                 ,       [67]. ,   ,    .   ,        .    .

       a  b,   a   b .  ?2   ?2.        .        ?2   2,  .     a  b .              .     ,   ,    - .

     .    .   ,   a  b .    .      :    - .  : .    ,    [68].

   .           .    :

          .

     ,   .     ,     ,    .

         ,    ,    [69].

 ,    ,         P vs NP.     . ,    . ,     .

     ?   .

         ,         .        .    .

     ,       .  ,                      [70].           .

    .    .  1928 ,         Mathematische Annalen, ,        ( ),     .    ,     .    ,       [71].

   .  ,    ,   .    , , .    , , .   .

    .

-,    . , ,    .        ,     .      .

-,    .    ,     XX        ,     ,       .     ,  .     ,  .

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

   ,      ,   ,    .       ,   :   ,  ,         .  ,      ,    .

   1966 ,  ,      .     .    ,   ,    .

      , ,       ,    [72].  -˸        ,      [73].    1967     ,  ,          ,        [74].   -              computer science.

    ,   .        .  ,      P vs NP   , ,     .    .        .

3.2.      -

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

              ,   ,     .          ,   ,     ,       ,           .

,    ,   :   .  ,   ,        ,   .  :     .     ?     ?  ?

     ,        :       ,    [75].      ,     :      ,   ,   .

 .  .   .  .      ,       ,      .    .

    ,   .  :     .  :    ?            .  :     .          , ,  [76].

      ,          .

 :  .    .      :        ,             [77].

   .   . ,  - , :     ,  .     .     ,       .

 :        .    :    x  P(x)    ,    ,     x ,  P(x) .  :     ,   - x     .

      ,        ,     .        .    .    ,    [76].

 :    .  .          .       .     ,       ,   .     .

     .  ,    ,    ,    .     .

  ,     ,             [78].   :      ,   .

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

            .       ,     ,           .

    ,         .            ,   .           .

             P vs NP.   ,  ,       .  ,   ,    .

    P vs NP  :     ,    ?     ,          ,        .

       :   ,     ,   ,     ?

 :           .      .    -  .       .      .

 ,           .       ,      .      .       .         ,   ,   .        :  ,  .

  ,    ,  ,   P ? NP    ,    .                 ,         .

       ,       ?    . -,    ,            .          ,  ,         [79].

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

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

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

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

     ?

       ,      .  :   ,     ,   .  :   ,     ,   .  .  ,        ,      [78].    ,     ,    :  -,    ,  ,     ,      .

  , , .     ,   ,   .      .   ,         ,     .                   .

 -    :         .     ,    ,   ,   P vs NP  .      ,         ,   ,    .

 ,    ,     .        ,        .                  .    .

       ,  . Ÿ       computer science,     .  .           P vs NP. ,    ,    ,     .

3.3.   -˸   -

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

     .    .    .    .     ,   ,    ,     .     :    ,         .      ,    :    - .          .     ,          [80].

-˸  :    .       .        .   :  n   ,      ,  n   N.      ,   n : 0     ( );  m   ,  successor(m)     (   ).        [81].

   .    ,       .    ,     .   .   .  :   .  :   . -˸,  , ,  ,                   [82].

  ,    ,      .   -  ,  ,            .

        .  1930-                -.  1960-   ,  ,      :      ,         [83].   -˸          .

     .    A,  B     A  B.      ,       .  A  B   .  A  B   .      [84].

   :    ,        .     ,     ,    .      . .

,   ,           ,     .      ?         ?  ,    ? ,   ,    ?!

    .  , , .

    -˸            ,       ,    .      .

     : ,     - .     ,   .              x,   P(x)     :      a   ,  P(a) .      a,       .        [81].

  . -˸     .      .             ,       ,    :   .

          ,   ,  .   ,          ,      ,   .     ,         [85].

    ,         ZFC?     .

-, .         .  ,  ,   ,     ZFC.      ,      ,       .    ,       .

-,     ,   .  ZFC             .       ,        .         ,    .

-,     ,       P vs NP . ,      . ,    .    ,     .    ,     ,            . ,  .    ,     [86].

     .    ,        P vs NP.   ,      .     ,     .           .        .      .  .  .

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

3.4.       P vs NP

,         .  :     ,     .  :     ,    . -˸ :    ,     ,     .  ,     P vs NP     ,      .

 . ?

         :         .           :        .   P vs NP     .

      .  :  .  .      ,  .       ,      .               . ,   . ,   ,   .  ,      ,      ,   [87].

  :      .   ,  .     .    .  ,   ,      .   ,   ,          .   .   . ,       ,   .     ,   ,      [76].

-˸    .       ,   .                .    ,     ,    .      .  .  .  ,     ,    hardware,   mathematics [86].

  .   .      :   .   .   ,    ,            ,    ,     ,       .

     ?    ,   :        .   ,     ,      .

    .      .         .        ?          ,    ,    ,   [88].

,  ,   .    .      :  A  B,   ,    . ,    ,  ,    , . ,   ,  ,   ,   ,      .

 P vs NP      .     ,   .    ,     ,    ,    .                   [89].

   P vs NP,     .       .     ,    . ,           . ,        ,     .

,   -˸   .  :  .    :  ,     .    ,           .    ,       ,     .               [90].

 ,      ,   .  :   .             ,  ,     .          ,   .        ,     .

 ,       ,    .       ,    .     ,   ,   .



       P vs NP,      .         .   P vs NP     .    .   .   .

        .     ,   .   ,    .      ,      .

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

3.5.    :   

   .      ,   ,   .     ,   ,     , , . -˸  ,    ,    ,         .

       :    ,   .   ,  ,         ,     .            ,  ,       .    , ,  .      P vs NP.        .     ,        .

    :       .  ,    , ,               ,     ,    ,   .          ,    .

     ,        .   -˸   .        ,     .        .

    .   .    .    ,  .        .   ,         .    .    .    .

      .    ,   . ,   . ,       . ,  ,    . ,  ,  ,   .

    ,   ,     P vs NP   .    P vs NP      .   .   :        ?         ,       ,  ,     ,   [91].

   ,   -˸? -,   : .     .        ,     .        ,     .       ,    ,   .

 ,       ,    .    .    .   ,   ,    .      .    .    .

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

      .    .    ,           .   ,            .        .           ,    .



     .  ,       .  ,  -       ,       .      ,     .

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

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

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

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

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

           P  NP.   .   .  .        .     .     .

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

   .    .




 II.  :   





 4.    


4.1.  ?   

 ,     .    -      ,  ,  ,            .     ,   ,      .

          .     ,   .        ,    .      ,  ,     ,       .           .   ,        .

  .   ,          .   .   .  ,      ,     .

   ,      .

 .  .    . .  ,     .         .           ,    .

   ,    .   ,  .   .     .     .   ,         .

    ,     ?.        .     ,     .    ,      .  , ,    .     ,    [92].

:    .     .    ,    ,    .   :     ,        .   .   ,      [93].

   .

    .

.

,      .    .     .   ,        .    . ,  .

,     .

   .

     

.  .       ,     .

   ,  ,    ,   .    .

,     ,       ,       .  ,     ,   .        .       .       .

  :     ,        ,      ,   .   :     ,     ,   ,       .

 ,   ,   .          .       .    .              ,       [96].

   .   .  ,   ,    .        ,   , ,    . ,    ,     ,         .    ,   .  ,     .

        .       ,       .    .     .  ,    ,     .  ,   ,       ,         .

  ,     .        ,         .     .          .      .

  :    !  ,    ! .   ,    .  ,       .       ,    ,            .              ,     ,         ,    ,            .    ,     [95].

  ,     ,       ,   .  ,      .    ,    ,            .    . ,     ,    ,     :        .  ?

4.2.      

,  :     .   ,    ,    :      ?  ?    ?   ,      ,    , ,   ?

  . ,   ,      ,     , , :       ,   ?       ,     .

      ,         .   :       ?

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

  ,    .             . ,   :  ,      .    ,   ,           .  ,    ,        .         ,        [97].

,  ,  :      !  !   ! , .     .       .  ,    .        .  .  .    [98].

 .           ,    ,   ,     .      .       .  ,       [100].

  ,    ,         ,      ,   :

       .

   .    .     .      .   .     ,  ,  .  . ,       ,   .

     ,       .     ,  ,   .     ,  :   ,   .      .       .     [101].

  ,    ,     ,     ,        .

 ,  ,      .      .     ,  .         ,   ,    .      .   .      .   ,      .

,  ,   .   ,      ,     ,   .   ,       . ,   ,    : ,  ,      .      .         .

 P vs NP   .  ,       .         .    .     ,     P vs NP ,    .             , ,   ,   ,    .

4.3.    

       ,     . . .   .    ,         ,        ,   ,       ,      ,     .




  .


   .

   ,     (https://www.litres.ru/pages/biblio_book/?art=74130484)  .

      Visa, MasterCard, Maestro,    ,   ,     ,  PayPal, WebMoney, ., QIWI ,       .


