П=НП проблем

Аутор: Лука Хаџи-Ђокић

Од свог зачетка, теоријско рачунарство бавило се решавањем проблема уз помоћ опипљивих или замишљених машина које покрећу и извршавају алгоритме. Оно што су приметили математичари и рачунарски научници који су се овим бавили јесте да постоје проблеми који су нерешиви, док су касније нашли да се они решиви лако могу разврстати по времену (или меморији) које је потребно да би се алгоритам извршио. Тако је настала теорија израчунљивости, а касније и овај наизглед лак (а после темељне инспекције ђаволски тежак) проблем: „Који је однос класа П и НП?”, познатији као „П=НП” проблем. Њега су формално дефинисали (независно један од другог) Стивен Кук (енг. Stephen Cook) и Леонид Левин, 1971. године. Увидевши могуће последице које би изазвало решење, 2000. године је заједно са још шест других отворених питања сврстан међу „Миленијумске проблеме”, па је тако награда за његово савладавање у износу од милион долара понуђена од стране Клејовог математичког института (енг. Clay Mathematics Institute). Као увод у проблем, морамо прво дефинисати шта тачно значе П и НП.

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

Остатак НП чине проблеми до чијег се решења долази тешко, у ц·кн корака (експоненцијално време извршавања), али се ипак оно лако потврђује. Пример за ово би био проблем налик следећем: „У неком студентском дому треба изабрати 100 студената од укупно 400 који могу бити примљени у дом. Уз задатак, добили смо и листу парова ученика који, из нама непознатих разлога, не смеју бити заједно на списку.” Да бисмо направили распоред, једино што можемо урадити јесте да пробамо све могуће комбинације „студент-соба” и да потом сваку упоредимо са листом коју смо добили. Од 400 студената изабрати одговарајућих 100 је практично немогуће, јер број могућих комбинација надмашује укупан број атома у нама познатом универзуму (за неке мање бројеве је могуће решити, али број корака нагло расте са повећањем улазног податка). У односу на то, да бисмо проверили једно решење овог проблема, све што треба да урадимо јесте да изабраних 100 упоредимо са листом.

Још један битан случај класе НП су НП-комплетни проблеми – специфични су по томе што се сваки други проблем из класе НП на њих може свести. Ту спадају проблеми трговачког путника, проблем задовољивости (САТ проблем, који је у ствари први доказан као члан НП-комплетних проблема, Кук-Левиновом теоремом) и многи други. Трговачки путник је, на пример, проблем који поставља питање да ли је, уз помоћ карте са неким градовима и дужине пута између сваког града, могуће проћи кроз сваки од тих градова и вратити се у почетни, тако да дужина целог пута буде мања од произвољно изабране дужине Л. Када би неко за овај или неки од осталих таквих проблема нашао „лако” решење (оно које се извршава у полиномијалном времену) и тако га сврстао у групу П, доказао би да се, у ствари, цела група НП може свести на један П проблем, што би довело до њихове једнакости (П=НП). Овакво решење тог гигантског питања рачунарства имало би, без претеривања, у исто време ужасавајући и охрабрујући ефекат. Наиме, ако би оно било истинито, шифровање података би изгубило свој смисао (јер се они шифрују под претпоставком да је један проблем који спада у НП скоро немогуће решити), али би исто тако и омогућило лако решавање многих других проблема. Како је то рекао др Скот Аронсон (енг. Scott Aaronson) са МИТ-а: „Ако је П=НП, онда би свет био доста другачије место него што ми претпостављамо да јесте. ‘Креативни скокови’ не би имали никакву специјалну вредност, основна празнина између решавања проблема и препознавања његовог већ пронађеног решења такође би нестала. Свако ко схвата вредност симфоније постао би Моцарт; свако ко може да пропрати кораке аргумента био би Гаус.”

Међутим, ако је веровати стручњацима, чије је знање и схватање овог проблема на много вишем нивоу од нас који о њему прочитамо у часопису или другде на интернету, тако нешто је врло мало вероватно. У анкети спроведеној 2002. године, од 100 рачунарских научника 61 је мишљења да је одговор П≠НП, њих 22 није било сигурно, 8 је веровало да је долажење до решења немогуће, док је само 9 њих рекло да је одговор П=НП.

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