Опис
„Теоријата на комплексност на пресметувањето претставува јадро на теоретското истражување во компјутерските науки. Оваа книга во основата го содржи поголемиот дел од напредокот во последните две децении, со високо ниво на проникливост и детални технички докази. Ова е задолжителна литература за сите што имаат интерес во оваа област.“
– Ави Видгерсон, професор на Институтот за напредно истражување, Принстон
„Книгата на Арора – Барак е големо постигнување што ги обединува сите важни напредоци во теоријата на комплексноста. И студентите и истражувачите во книгата гледаат неизмерно корисен извор.“
– Мајкл Сипсер, раководител на Одделот за математика, МИТ,
и автор на Вовед во теорија на пресметувањето
Овој воведен учебник, за постдипломци, ги опишува неодамнешните достигнувања и класичните резултати на теоријата за комплексноста на пресметувањата. Во основа, не барајќи никакви предзнаења, освен математичка зрелост, книгава може да се користи како референца за самоучење за секој што е заинтересиран за комплексноста, вклучувајќи физичари, математичари и други научници, како и учебник за повеќе предмети и за семинари. Вклучени се повеќе од 300 задачи со одбрано множество каде што има помош.
Книгата започнува со широк вовед во полето со напредни резултати. Содржината вклучува дефиниција на Туринговите машини и основните временски и просторни класи на комплексност, веројатносни алгоритми, интерактивни докази, криптографија, квантни пресметувања, долни граници за конкретни модели за пресметување (дрва на одлучување, комуникациска комплексност, константна длабочина, алгебарски и монотони кола, доказна комплексност), комплексност во просечен случај и цврстина на засилување, дерандомизација и псевдослучајни конструкции и PCP теоремата.
Санџив Арора е професор на департманот за компјутерски науки на универзитетот Princeton. Тој има фундаментални резултати за веројатносно проверливи докази и апроксимативност на NP-тешки проблеми. Тој е основачки директор на центарот за Пресметковна нерешливост, а е спонзориран од Националната фондација за наука (англ. National Science Foundation).
Боаз Барак е професор на департманот за компјутерски науки на Универзитетот Princeton. Тој има фундаментални резултати за комплексноста на пресметувањата и криптографијата, особено во развојот на техниките со „не-црни-кутии“.