Утицај математике на настанак и темеље рачунарства (3. део)

Међу прве резултате спадају и резултати о немогућности решавања неких проблема алгоритмом. Један од таквих резултата је и проблем заустављања који се састоји у томе да за дати програм на улазу, који сам не захтева никакав улаз, одредимо да ли би се тај програм једном пуштен у рад завршио у коначном броју корака.

Други сродан резултат је да није могуће направити програмски језик који би обухватио све алгоритме и чији би се сви програми заустављали у коначном броју корака. Да би неки програмски језик обухватио све алгоритме (заустављиве поступке), он мора да допушта и конструкције као што су бесконачне петље, тј. конструкције које могу да раде, а да се никада не зауставе. Највећи број програмских језика је баш такав, а има и система код којих се жртвује обухватање свих алгоритама зарад универзалне заустављивости. Пример је помоћник у доказивању теорема Agda.

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

Понекад је добро што су неки проблеми алгоритамски јако тешки јер не желимо да буду решени. Такви су проблеми разбијања криптографских примитива чије би решавање довело до злоупотреба. Било би јако добро да имамо криптографске примитиве за које имамо доказе да се не могу разбити без одређених израчунатих ресурса који превазилазе снагу било каквог хардвера који се може произвести. Међутим, то није случај, а искључиви разлог је што још увек није достигнут потребан степен развоја математике. За сада се криптографска безбедност проверава емпиријски, тако што се алгоритми објављују у научним часописима, па ако се за одређен број година нико није јавио са поступком разбијања, онда се алгоритам сматра безбедним. Свакако би боље било имати доказ безбедности.

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

Све примитиве се могу разбити у полиномијалном времену на машинама са неограниченим паралелизмом (нпр. бесконачним бројем процесора који могу паралелно да раде). Ако тражимо приватни кључ од 100 битова када је дат јавни кључ, ми заправо треба да проверимо све могуће низове од 100 битова, који од њих чини приватни кључ који се слаже са датим јавним. Прво можемо проблем поделити на два случаја – оне код којих је први бит једнак 0 и оне код којих је први бит једнак 1. Те случајеве могу да обрађују два процесора паралелно. Затим, сваки од та два случаја поделимо на два подслучаја – када је други бит једнак 0 и када је други бит једнак 1. Те подслучајеве могу паралелно да обрађују четири процесора. Тако ћемо у сто корака цепања сваког од подслучајева на два подслучаја у сто корака упослити процесоре од којих сваки обрађује један низ од 100 битова и сви раде паралелно. То омогућава да се на таквим машинама тај проблем реши ефикасно. Слична идеја се може применити и на разбијање симетричних кључева и криптографских хеш (енг. hash) функција.

За такве проблеме се каже да припадају класи NP, која из наведених разлога чини теоријски максимум криптографске безбедности.

За класе P и NP се још увек не зна да ли су исте или различите. За решење тог проблема је чак понуђена награда од милион америчких долара и он свакако представља централни нерешени проблем теоријског рачунарства. Ако су те класе једнаке, с обзиром на то да проблеми разбијања увек припадају класи NP, они у том случају припадају и класи P, што значи да је ефикасно разбијање могуће, па би примена криптографије била знатно ограничена и отежана. У супротном остаје могућност да постоји проблем који је применљив на криптографију и има потребне особине. Стога је у сваком случају неопходно решити тај проблем да би се стигло до примена у криптографији.

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

Чак и када се то успе, остаје још један проблем. Физичари су открили другачији приступ израчунавању тзв. квантним рачунарима, који мада могу да решавају потпуно исте проблеме као класични (тј. не доводе у питање Черч-Тјурингову тезу), неке проблеме могу да решавају и ефикасније, где спадају и проблеми разбијања неких (не свих) криптографских алгоритама. Стога треба доказати отпорност и на нападе квантним рачунарима (тзв. проблем постквантне криптографије), што је још тежи задатак.

За крај, поменимо један правац истраживања који обједињује формализацију математике и формализацију појма алгоритма.

Програми се обично тестирају на коначном броју примера. Мада се примери пажљиво бирају тако да вероватноћа неиспољавања грешке ако постоји буде што мања, обично нешто промакне. Други пут је формална провера софтвера, где се жељене особине неког програмског кода доказују као теореме. Међутим, пошто су људи подложни грешкама, доказе треба да провери машина.

У том погледу, најпре имамо провераваче доказа којима мора целокупан доказ бити дат на улазу. С обзиром на то да је људима напорно да уносе баш сваки корак доказа, други приступ су доказивачи теорема који аутоматски доказују задату теорему. Међутим, пошто се испоставило да је тај циљ за већину математичких теорија чак недостижан, златна средина су помоћници у доказивању који такође захтевају доказ на улазу, али не сваки корак, јер имају „ограничену памет”, тако да човек не мора да уноси баш сваки корак, већ само оно за шта машина каже да јој је остало „нејасно”.

Водећи такви програми су Isabelle, Coq и Agda, при чему су сви они академски пројекти доступни као слободан софтвер отвореног кода. То је у овом случају чак неопходно, јер је провера исправности програма који проверава доказ, саставни део научне провере доказа које ти програми проверавају. Стога је тај модел уобичајен за академске пројекте, јер у супротном не би било могуће научно позивање на резултате који се њима добијају.

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

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

Претходни део