Теорија комплексности

Грана теорије израчунљивости у рачунарству, рачунарска теорија комплексности описује скалабилност алгоритама, и инхерентну тешкоћу у изналажењу скалабилних алгоритама за специфичне рачунарске проблеме. Другим речима, теорија комплексности одговара на питање Када се величина улаза за алгоритам повећава, како се мењају време извршавања и меморијски захтеви, и које су импликације и тих промена? Ова теорија одређује практичне границе онога шта рачунари могу да постигну.

Резултати теорије комплексности су од значаја и за науку и за привреду. Брзина и меморијски капацитет рачунара се стално повећавају, али се повећава и количина података која се анализира. Ако алгоритми нису скалабилни, тада чак и јако велика унапређења у рачунарској технологији понекад могу да доведу само до незнатних повећања количине података која може да се анализира.

Алгоритми и проблеми су категоризовани у класе комплексности. Најважније отворено питање у теорији комплексности је да ли је класа П иста као класа НП, или јој је само подскуп, као што је опште уверење. Ово није само суво теоријско разматрање, јер убрзо након што је ово питање први пут постављено, откривено је да су многи важни индустријски проблеми из подкласе класе НП, коју називамо класа НП-комплетних проблема. НП-комплетни проблеми имају својство да се њихова решења могу брзо проверити, али тренутно постојећи методи за налажење тачних решења нису скалабилни. Ако је класа НП једнака класи П, онда постоји скалабилно решење за све проблеме из класе НП. Ово међутим још увек није утврђено, и једно је од најважнијих отворених питања у рачунарству данас.[1]

Преглед

уреди

Теорија се сложености бави релативном рачунском тешкоћом израчунљивих функција. Ово се разликује од теорије израчунљивости, која се бави генералним питањем може ли се проблем решити, без обзира на захтеване ресурсе.

Један „проблем” је јединствен скуп повезаних питања, при чему је свако питање стринг коначне дужине. На пример, проблем ФАКТОРИЗИРАЈ јесте: за дати цели број записан у бинарном систему, врати све просте факторе тог броја. Појединачно се питање зове инстанцом. На пример, „дај факторе броја 15” је инстанца проблема ФАКТОРИЗИРАЈ.

Временска сложеност проблема је број корака потребан да би се инстанца проблема решила као функција величине улаза (обично мереног у битовима) користећи најефектнији алгоритам. Да би се ово интуитивно разумело, може се размотрити пример инстанце дужине n битова која може бити решена у n² корака. У овом примеру каже се да је проблем временске сложености n². Наравно, тачан ће број корака зависи од кориштеног приступа. Како би се избегао тај проблем, користи се велико О нотација. Ако проблем има временску сложеност O(n²) на једном типичном рачунару, тада ће такође имати сложеност O(n²) на већини других рачунара, тако да ова нотација омогућава поопштавање детаља појединачног рачунара.

Пример: Кошење траве има линеарну временску сложеност с обзиром да треба двоструко више времена како би се косило двоструко веће подручје. Међутим, бинарно претраживање речника има свега логаритамску временску сложеност будући да двоструко већи речник треба бити отворен тек један пут више (нпр. тачно у средини - тада се величина проблема смањи за пола).

Просторна сложеност проблема је повезан концепт, који мери количину простора, или меморије коју алгоритам захтева. Неформална би аналогија била количина папира кориштеног за скицирање приликом решавања проблема оловком и папиром. Просторна се сложеност такође мери великом О нотацијом.

Различита мера сложености проблема, корисна у неким случајевима, јест сложеност склопа. Ово је мера величине буловског склопа потребног за рачунање решења проблема, у терминима броја логичких врата захтеваних за изградњу склопа. Таква је мера корисна, на пример, приликом изградње склоповских микрочипова за израчунавање функције, радије него програмске подршке.

Класе сложености

уреди

Класа сложености је скуп свих рачунских проблема који се могу решити користећи одређену количину одређеног рачунског ресурса.

Класа сложености P је скуп свих проблема одлуке који могу бити решени детерминистичком Тјуринговим машином у полиномном времену. Ова класа одговара интуитивној идеји проблема који могу бити делотворно решени у најгорим случајевима.[2]

Класа сложености НП је скуп проблема одлуке који могу бити решени недетерминистичком Тјуринговом машином у полиномном времену. Ова класа садржи многе проблеме које би људи желели делотворно да реше, укључујући проблем буловске испуњивости, проблем хамилтоновског пута и проблем прекривања врхова. Сви проблеми у овој класи имају својство да им се решења могу делотворно проверити.[2]

Многе се класе сложености могу карактеризирати у терминима математичке логике потребних да би се изразили - ово се поље зове дескриптивна сложеност.

Отворена питања

уреди

P = NP питање

уреди

Питање истоветности скупова NP и P (тј. могу ли проблеми који могу бити решени у недетерминистичком полиномном времену, решени у детерминистичком полиномном времену) је једно од најважнијих отворених питања у теоретском рачунарству, с обзиром на широке импликације које би решење тог питања имало.[2] Једна негативна последица је та да би се многи облици криптографије могли једноставно „разбити” и стога постали бескорисни. Међутим, постојале би и огромне позитивне последице, будући да би многи важни проблеми имали ефикасна решења. Такви проблеми укључују разне типове целобројног програмирања у операцијским истраживањима, многе проблеме у логистици, предвиђању структуре беланчевина у биологији, те способности делотворног проналажења формалних доказа теорема у чистој математици кориштењем рачунара.[3][4] Клејов математички институт је 2000. обавио да ће исплатити награду од УСД$ 1 000 000 првој особи која докаже решење.[5]

Питања попут ових мотивирају концепте тежине и потпуности. Скуп проблема X је тежак за скуп проблема Y ако сваки проблем у Y може "лако" бити трансформиран у неки проблем у X који производи решење. Дефиниција „лаког” је различита у различитим контекстима. Важан тешки скуп у теорији сложености јесте NP-тежак - скуп проблема који нису нужно сами у NP, али на које било који NP проблем може бити сведен у полиномном времену.

Скуп X је потпун за Y ако је тежак за Y, али је такође и подскуп од Y. Важан потпун скуп у теорији сложености је NP-потпун скуп. Овај скуп садржи „најтеже” проблеме у NP, у смислу да су то они који најизгледније нису у P. Због чињенице да проблем P = NP остаје нерешен, свођење би проблема на познати NP-потпун проблем индицирало да не постоји познато временски полиномно решење за њега. Слично, будући да сви NP проблеми могу бити сведени на скуп, проналажење NP-потпуног проблема који би могао бити решен у полиномном времену би значило P = NP.[2]

Непотпуни проблеми у NP

уреди
 
Дијаграм класа сложености уз претпоставку да вреди PNP. Постојање проблема изван класа и P и NP-потпун у овом случају је поставио Ладнер.[6]

Друго отворено питање везано за проблем P = NP јесте постоје ли проблеми који су у NP, али не и у P, који нису NP-потпуни. Другим речима, проблеми који требају бити решени у недетерминистичком полиномном времену, али не могу бити сведени на полиномно време из других недетерминистичких временски полиномних проблема. Један такав проблем, за који се зна да је NP али не и да је NP-потпун, јест проблем изоморфизма графа - проблем који покушава одлучити јесу ли два графа изоморфна (тј. деле ли иста својства). Показано је да ако вреди PNP, да такви проблеми постоје.[7]

NP = ко-NP

уреди

Где је ко-NP скуп који садржи комплементарне проблеме (тј. проблем са инвертираним да/не одговорима) NP проблема. Верује се да те две класе нису једнаке, иако то досад није доказано. Показано је да ако ове две класе нису једнаке, да тада следи да недан NP-потпун проблем не може бити у ко-NP, и ниједан ко-NP-потпун проблем не може бити у NP.[7]

Види још

уреди

Референце

уреди
  1. ^ „P vs NP Problem | Clay Mathematics Institute”. www.claymath.org (на језику: енглески). Архивирано из оригинала 06. 07. 2018. г. Приступљено 14. 03. 2021. 
  2. ^ а б в г Sipser, Michael (2006). „Time Complexity”. Introduction to the Theory of Computation (2nd изд.). USA: Thomson Course Technology. ISBN 0-534-95097-3. 
  3. ^ Berger, Bonnie A.; Leighton, Terrance (1998). „Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.”. Journal of Computational Biology. 5 (1): 27—40. PMID 9541869. doi:10.1089/cmb.1998.5.27. 
  4. ^ Cook, Stephen (2000). „The P versus NP Problem” (PDF). Clay Mathematics Institute. Архивирано из оригинала (PDF) 12. 12. 2010. г. Приступљено 2006-10-18. 
  5. ^ Jaffe, Arthur M. „The Millennium Grand Challenge in Mathematics” (PDF). Notices of the AMS. 53 (6). Приступљено 2006-10-18. 
  6. ^ Ladner, Richard E. (1975). „On the structure of polynomial time reducibility” (PDF). Journal of the ACM (JACM). 22 (1): 151—171. S2CID 14352974. doi:10.1145/321864.321877. 
  7. ^ а б Du, Ding-Zhu; Ko, Ker-I (2000). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0. 

Литература

уреди

Спољашње везе

уреди