Теорија комплексности
From Wikipedia, the free encyclopedia
Грана теорије израчунљивости у рачунарству, рачунарска теорија комплексности описује скалабилност алгоритама, и инхерентну тешкоћу у изналажењу скалабилних алгоритама за специфичне рачунарске проблеме. Другим речима, теорија комплексности одговара на питање Када се величина улаза за алгоритам повећава, како се мењају време извршавања и меморијски захтеви, и које су импликације и тих промена? Ова теорија одређује практичне границе онога шта рачунари могу да постигну.
Резултати теорије комплексности су од значаја и за науку и за привреду. Брзина и меморијски капацитет рачунара се стално повећавају, али се повећава и количина података која се анализира. Ако алгоритми нису скалабилни, тада чак и јако велика унапређења у рачунарској технологији понекад могу да доведу само до незнатних повећања количине података која може да се анализира.
Алгоритми и проблеми су категоризовани у класе комплексности. Најважније отворено питање у теорији комплексности је да ли је класа П иста као класа НП, или јој је само подскуп, као што је опште уверење. Ово није само суво теоријско разматрање, јер убрзо након што је ово питање први пут постављено, откривено је да су многи важни индустријски проблеми из подкласе класе НП, коју називамо класа НП-комплетних проблема. НП-комплетни проблеми имају својство да се њихова решења могу брзо проверити, али тренутно постојећи методи за налажење тачних решења нису скалабилни. Ако је класа НП једнака класи П, онда постоји скалабилно решење за све проблеме из класе НП. Ово међутим још увек није утврђено, и једно је од најважнијих отворених питања у рачунарству данас.[1]