йУУМЕДХЕНБС РТПВМЕНБ СЧМСЕФУС NP-ФТХДОПК Ч ПВЩЮОПН УНЩУМЕ [1]. мБХМЕТ РТЕДМПЦЙМ [2] РУЕЧДПРПМЙОПНЙБМШОЩК БМЗПТЙФН ТЕЫЕОЙС ПВЭЕЗП УМХЮБС РТПВМЕНЩ ФТХДПЕНЛПУФЙ O(n^4 sum p_j). ыЧБТГ Й ДТ. РПУФТПЙМЙ [3] БМЗПТЙФНЩ ТЕЫЕОЙС РТПВМЕНЩ, ЛПФПТЩЕ ВЩМЙ РТПФЕУФЙТПЧБОЩ ДМС РТЙНЕТПЧ n < 600 (ФЕУФПЧЩЕ РТЙНЕТЩ рПФФУБ Й чБО чБУУЕОИПЧБ [4]). йУУМЕДПЧБОЙЕ РТЙВМЙЦЕООЩИ БМЗПТЙФНПЧ ТЕЫЕОЙС РТПВМЕНЩ ВЩМП РТПЧЕДЕОП Ч ТБВПФЕ [5], ЗДЕ РПУФТПЕОЩ РТЙНЕТЩ, ОБ ЛПФПТЩИ ЙЪЧЕУФОЩЕ РТЙВМЙЦЕООЩЕ БМЗПТЙФНЩ ОБИПДСФ ТЕЫЕОЙЕ У ПФОПУЙФЕМШОПК РПЗТЕЫОПУФША РПТСДЛБ ТБЪНЕТОПУФЙ РТЙНЕТБ n.
вБХЬТ Й ДТ. РТЕДМПЦЙМЙ БМЗПТЙФН нХТБЧШЙОЩЕ ЛПМПОЙЙ ОБ ВБЪЕ ЙЪЧЕУФОПЗП НЕФБЬЧТЕУФЙЮЕУЛПЗП РПДИПДБ [7].



оБ ПУОПЧЕ ОБКДЕООЩИ УЧПКУФЧ (РПДИПДСЭЙЕ РПЪЙГЙЙ Ч ПРФЙНБМШОПН ТБУРЙУБОЙЙ) РПУФТПЕО ФПЮОЩК БМЗПТЙФН б [11] ТЕЫЕОЙС ЪБДБЮЙ НЙОЙНЙЪБГЙС УХННБТОПЗП ЪБРБЪДЩЧБОЙС ДМС ПДОПЗП РТЙВПТБ $1||\sum T_j$.

ьЛУРЕТЙНЕОФБМШОП, Б ЪБФЕН Й ФЕПТЕФЙЮЕУЛЙ ВЩМЙ ЧЩДЕМЕОЩ ОБЙВПМЕЕ УМПЦОЩЕ ЮБУФОЩЕ УМХЮБЙ, ДМС ЛПФПТЩИ БМЗПТЙФН б ЙНЕЕФ ОБЙВПМШЫЕЕ ЛПМЙЮЕУФЧП ЧЕФЧМЕОЙК Ч ДЕТЕЧЕ РПЙУЛБ.

дМС ЬФЙИ ОБЙВПМЕЕ УМПЦОЩИ ЮБУФОЩИ УМХЮБЕЧ РПУФТПЕО ОБВПТ РПМЙОПНЙБМШОЩИ Й РУЕЧДПРПМЙОПНЙБМШОЩИ БМЗПТЙФНПЧ: ч-1 (ФТХДПЈНЛПУФЙ $O(n \sum p_j)$), ч-Л ($O(n^2 \sum p_j)$), B-n ($O(n^2)$), у-1 ($O(n^2)$) [12].

хУФБОПЧМЕОП, ЮФП БМЗПТЙФН ч-1 ТЕЫБЕФ ЛБОПОЙЮЕУЛЙЕ РТЙНЕТЩ ЙЪ ТБВПФЩ [9], Л ЛПФПТЩН УЧПДСФУС РТЙНЕТЩ NP-РПМОПК ЪБДБЮЙ юЈФОП-оЕЮЈФОПЗП тБЪВЙЕОЙС.

рПУФТПЕО БМЗПТЙФН ч-1 НПДЙЖЙГЙТПЧБООЩК, ЛПФПТЩК УПЛТБЭБЕФ РУЕЧДПРПМЙОПНЙБМШОХА УПУФБЧМСАЭХА $(\sum p_j)$ БМЗПТЙФНБ ч-1.

рПЛБЪБОП, ЮФП ЙЪЧЕУФОЩЕ ФПЮОЩЕ БМЗПТЙФНЩ ыЧБТГБ, юЕОЗБ Й ДТ.[9] ЙНЕАФ ЬЛУРПОЕОГЙБМШОХА ФТХДПЕНЛПУФШ ДМС ОЕЛПФПТЩИ ЛМБУУПЧ РТЙНЕТПЧ. дМС ЬФЙИ ЛМБУУПЧ РТЙНЕТПЧ ОБНЙ РПУФТПЕОЩ РУЕЧДПРПМЙОПНЙБМШОЩЕ Й РПМЙОПНЙБМШОЩЕ ФПЮОЩЕ БМЗПТЙФНЩ.

дПЛБЪБОБ NP-ФТХДОПУФШ ЮБУФОПЗП УМХЮБС B-1 ЪБДБЮЙ Й ЕЗП УЧСЪШ У ЛМБУУЙЮЕУЛЙНЙ ЪБДБЮБНЙ тБЪВЙЕОЙС Й тАЛЪБЛБ [10].

рТЕДМПЦЕО ОПЧЩК РПДИПД Л ТЕЫЕОЙА NP-ФТХДОЩИ ЪБДБЮ: зТБЖЙЮЕУЛБС ТЕБМЙЪБГЙС НЕФПДБ ДЙОБНЙЮЕУЛПЗП РТПЗТБННЙТПЧБОЙС. оБНЙ РПУФТПЕОЩ "ЗТБЖЙЮЕУЛЙЕ БМЗПЙТФНЩ" ДМС ТСДБ ЪБДБЮ ЛПНВЙОБФПТОПК ПРФЙНЙЪБГЙЙ: "ъБДБЮБ ТБЪВЙЕОЙС", "ЪБДБЮБ П ТАЛЪБЛЕ". рПЛБЪБОП ФЕПТЕФЙЮЕУЛЙ Й ЬЛУРЕТЙНЕОФБМШОП, ЮФП ЗТБЖЙЮЕУЛЙЕ БМЗПТЙФНЩ ЪОБЮЙФЕМШОП ЬЖЖЕЛФЙЧОЕЕ ЙЪЧЕУФОЩИ БМЗПТЙФНПЧ ДЙОБНЙЮЕУЛПЗП РТПЗТБННЙТПЧБОЙС Й РТЙНЕОЙНЩ, Ч ФПН ЮЙУМЕ, ДМС ОЕГЕМПЮЙУМЕООЩИ РТЙНЕТПЧ.

рПУФТПЕО зЙВТЙДОЩК БМЗПТЙФН, ЙУРПМШЪХАЭЙК ЙДЕА ЙЪЧЕУФОПЗП НЕФБЬЧТЙУФЙЮЕУЛПЗП БМЗПТЙФНБ "нХТБЧШЙОЩЕ ЛПМПОЙЙ" Й ЛПНВЙОБФПТОЩЕ УЧПКУФЧБ рТБЧЙМ ЙУЛМАЮЕОЙС 1-4. рП ТЕЪХМШФБФБН ЬЛУРЕТЙНЕОФПЧ, зЙВТЙДОЩК БМЗПТЙФН УХЭЕУФЧЕООП ЬЖЖЕЛФЙЧОЕЕ БМЗПТЙФНБ ACO ОБ РПРХМСТОЩИ ФЕУФПЧЩИ РТЙНЕТБИ. дМС 99.5% РТЙНЕТПЧ зЙВТЙДОЩН БМЗПТЙФНПН ОБКДЕОП ФПЮОПЕ ТЕЫЕОЙЕ. пФОПУЙФЕМШОБС РПЗТЕЫОПУФШ ОЕ РТЕЧПУИПДЙФ 0.5 %. уТЕДОЕЕ ОЕПВИПДЙНПЕ ЛПМЙЮЕУФЧП ЙФЕТБГЙК ОЕ РТЕЧПУИПДЙФ 5 [11].

пУОПЧОЩЕ ТЕЪХМШФБФЩ ОБЫЕК ЗТХРРЩ РП ДБООПК ЪБДБЮЕ РТЕДУФБЧМЕОЩ Ч РТЕРТЙОФЕ [9].