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

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

Алгоритми и проблеми су категоризовани у класе комплексности . На?важни?е отворено пита?е у теори?и комплексности ?е да ли ?е класа П иста као класа НП , или ?о? ?е само подскуп, као што ?е опште увере?е. Ово ни?е само суво теори?ско разматра?е, ?ер убрзо након што ?е ово пита?е први пут постав?ено, откривено ?е да су многи важни индустри?ски проблеми из подкласе класе НП, ко?у називамо класа НП-комплетних проблема . НП-комплетни проблеми има?у сво?ство да се ?ихова реше?а могу брзо проверити, али тренутно посто?е?и методи за налаже?е тачних реше?а нису скалабилни. Ако ?е класа НП ?еднака класи П, онда посто?и скалабилно реше?е за све проблеме из класе НП. Ово ме?утим ?ош увек ни?е утвр?ено, и ?едно ?е од на?важни?их отворених пита?а у рачунарству данас. ^[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 [ уреди | уреди извор ]

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

NP = ко-NP [ уреди | уреди извор ]

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

Види ?ош [ уреди | уреди извор ]

• Мастер теорема

Референце [ уреди | уреди извор ]

Литература [ уреди | уреди извор ]

Спо?аш?е везе [ уреди | уреди извор ]

Теори?а комплексности на Викимеди?ино? остави .

• The Complexity Zoo Архивирано на са?ту Wayback Machine (27. август 2019)
• Hazewinkel Michiel, ур. (2001). ?Computational complexity classes”. Encyclopaedia of Mathematics . Springer. ISBN 978-1556080104 .  
• What are the most important results (and papers) in complexity theory that every one should know?
• Scott Aaronson: Why Philosophers Should Care About Computational Complexity