За хората, които мразят математиката и се плашат от сложни уравнения, изразът NP=P е измамно прост.
Но върху доказателството му или за доказването на обратното (NP ≠ P) са работили безуспешно десетки години най-добрите умове на нашата планета. Това е една от седемте задачи на хилядолетието, за чието решаване математическият институт Клей дава един милион долара.
Нещо повече, ако някой успее обосновано и категорично да даде отговор, че NP и P са равни, това ще премахне всякакви ограничения пред човешкия ум и би отворило невероятни възможности пред нашата цивилизация.
Просто казано
Просто казано, P са всички относително лесни задачи и NP е набор, който включва изглеждащи много, много трудни задачи, така че ако P = NP, това би означавало, че очевидно сложни проблеми всъщност имат сравнително лесни решения.
Въпросът се свежда до: задължително ли е по-лесно да се провери една задача, отколкото да се реши?
Разбира се, има някои подробности.
Полиномно време
Един от най-важните въпроси в компютърните науки е колко време е необходимо, за да се изпълни даден алгоритъм. Времето зависи от броя на елементите на алгоритъма, които трябва да се обработят.
Представете си, например, че имате несортиран списък с числа, а искате да напишете един алгоритъм, който да намира най-голямото. Алгоритъмът трябва да разгледа всички числа в списъка и няма как това да се избегне. Но ако просто запомня в регистър най-голямото число, което е срещнал досега, е достатъчно да провери всеки запис само веднъж. По този начин времето за изпълнение на алгоритъма е право пропорционално на броя на елементите, с които се работи. Може да ги означим с N. Разбира се, повечето алгоритми са по-сложни и по този начин по-малко ефективни, отколкото този, някои алгоритми имат време за изпълнение, пропорционално на N2 например.
Математически израз, който включва елементи, пропорционални на N, N2 и N на някаква друга степен, се нарича полином и това означава "P"-то в “P = NP”. P е набор от задачи, чието време за решаване е пропорционално на полином с членове N, N2 и т.н.
Очевидно е, че един алгоритъм, чието време за изпълнение е пропорционално на N3, е по-бавен, отколкото такъв, чието време за изпълнение е пропорционално на N. Но тези разлики са незначителни в сравнение с разликата между полиномни изрази - където N се повдига на числови степен - и изрази, при които число се издига на N-та степен, като например 2N.
Ако алгоритъм, чието време за изпълнение е пропорционално на N, извършва изчисленията си за 100 елемента за секунди, алгоритъм, чието време за изпълнение е пропорционално на N3 работи почти три часа. Но за алгоритъм, чието време за изпълнение е пропорционално на 2N, му трябват 300 квинтилион години. И положеннието става много, много по-лошо с нарастването на N. Възможно е времето на Вселената да не ни стигне.
Така че въпросът "P равно ли е на NP?" означава "Ако решението на проблема може да се провери в полиномно време, може ли да се намери за полиномно време?".
Казано по-просто: задължително ли е по-лесно да се провери една задача, отколкото да се реши?
Примери
В общи линии може да се каже, че нещо, което е решимо в полиномиално време, е решимо от практическа гледна точка, а нещо, което се решава в експоненциално време, за нетривиални примери, може да не успеем да решим преди края на Вселената.
Намиране на делители на 13717421 е много сложно, но много лесно е да се провери, че 3607 x 3808 = 13717421. Това е в основата на повечето видове криптиране: много трудно да се разчете, но лесно за проверка. Това изглежда очевидно, но никой не може досега да го докаже.
Още един пример - вярно ли е, че сред числата {−2, −3, 15, 14, 7, −10, …} има такива, чиято сума е равна на 0? Отговорът е да, защото −2 −3 + 15 −10 = 0 . Този отговор лесно се проверява - трябва само да съберем числата. Следва ли от това, че също толкова лесно се намира кои са тези числа? Дали да се провери сертификата (информацията, необходима за проверка на положителния отговор) е също толкова лесно, както да се намери? Изглежда, че да се намерят числата е по-сложно, но това не е доказано.
Ето още един пример, илюстриращ задачата, който дава на страницата си Институтът Клей:
Да предположим, че организирате настаняването в жилища на група от 400 студенти. Местата са ограничени и само 100 от студентите ще получат места в двойна стая в общежитието. Нещата се усложняват, защото деканът е предоставил списък на несъвместими двойки студенти, които не може да са в една и съща стая. Лесно е да се провери дали дадена избрана група от сто студенти е задоволителна (т.е. няма двойка в списъка, която да е включена и в списъка на декана), обаче задачата за създаване на такъв списък от нулата изглежда толкова трудна, колкото и напълно непрактична. Всъщност общият брой варианти за избор на сто от четиристотин заявки е по-голям от броя на атомите в познатата Вселена! По този начин в бъдеще цивилизацията не може да се надява да изгради суперкомпютър, който да може да реши проблема с груба сила - тоест чрез проверка на всяка възможна комбинация от 100 студенти.
Класовете P и NP
Кратко и просто може класовете P и NP да се опишат по следния начин: P са изчислителни задачи, които лесно се решават; NP - задачи, за които е лесно да се провери дали твърдението е правилно.
Всички помним от детството си квадратните уравнения, които се решават с дискриминанта (тези, които не помнят - да погледнат по-долу). Решението на задачата се отнася към клас P (Polynomial time) - за нея има бърз (тук под "бърз" се разбира, че се изпълнява за полиномно време) алгоритъм за решаване:
*Квадратното уравнение има следния вид: ax2 + bx + c = 0
където a,b,c са реални числа и a ≠ 0. Всяко квадратно уравнение може да има 0, 1 или 2 реални корена,
получени по следната формула:
Числото D = b2 - 4ac се нарича дискриминанта. Ако D < 0, квадратното уравнение няма реални корени. Ако D = 0, уравнението има 1 реален корен - x=−b/2a. Ако D > 0, квадратното уравнение има 2 реални корена.
Съществуват и NP-задачи (Non-deterministic Polynomial time - което означава недетерминирано полиномно време), намереното решение на които може бързо да се провери по определен алгоритъм - тоест решенията могат да бъдат проверени за полиномно време.
Ако се върнем към решаването на квадратното уравнение, виждаме, че в този пример съществуващият алгоритъм за решаване се проверява също така лесно и бързо, както се и решава. Това означава, че тази задача се отнася и към първия клас, и към втория.
Класът P е подмножество на клас NP или както биха казали математиците - P ⊂ NP:
P ⊂ NP (Проблемите P са подвид на проблемите NP)
Досега никой не може да докаже или отрече строгостта на това включване, с други думи, да намери алгоритъм, който се намира в класа NP, но не принадлежи към P (т.е. е в жълтата част на схемата). Отговорът дали P = NP ще определи дали задачите, които могат да бъдат проверени в полиномиално време, също могат да бъдат решени в полиномиално време.
NP-пълните задачи
Ако се окаже, че P ≠ NP , това би означавало, че има задачи в NP, които е по-трудно да се изчислят, отколкото да се проверят - те не могат да бъдат решени в полиномиално време, но отговорът може да бъде проверен в полиномиално време.
Такива са т. нар. NP-пълни (NP-Complete) задачи. От определенията на класовете следва, че клас P е класът на най-лесните задачи в NP. Класът на NP-пълните задачи е най-сложен.
NP-пълните задачи се решават за експоненциално време (или за време n!) и това може да бъде много, много дълго. Такива са изброените в началото примери. За малки стойности на параметрите те се решеват сравнително бързо, но после бързо нарастват. И ако на 21 е лесно да се намерят делителите, то за 13717421 е много по-трудно. Решението на задачата за 8-те царици, които не се застрашават взаимно за стандартната шахматна дъска, е открито почти веднага след публикуването на задачата, но с увеличаването на размера на дъската и броя на фигурите търсенето на решение стана по-сложно. За 27 царици и дъска 27х27 броят на решенията е повече от 2.34 * 10 17, а за дъска 1000х1000 никоя съвременна машина не може да се справи.
Така NP-пълните задачи формират в определен смисъл подмножество от "стандартните" задачи в клас NP. Ако за някои от тях се намери "полиномно бърз" алгоритъм за решение, тогава за всяка друга задача от NP класа може да бъде решена точно толкова бързо.
NPC ⊂ NP (където NPC - NP-Complete - NP-пълни задачи). На схемата класовете Р и NPC не се пресичат:
NPC ∩ P = ∅
Какво би станало, ако се докаже, че P = NP
Какво би станало, ако клас P и клас NPC се пресичат? По определение към NP-пълната задача може да се сведе всяка задача от клас NP. Следователно, ако поне за една от тях се намери алгоритъм за решение за полиномно време - това ще означава, че проблемът е решен.
Но ако човечеството се научи да решава бързо NP-пълни задачи (в полиномно време), последствията могат да бъдат много неприятни. Практическата криптография в по-голямата си част ще стане безполезна. Цялата защитена информация (например паролата ви за банковата ви сметка) ще бъде напълно "беззащитна".
Ако се докаже равенството P = NP, цялата йерархия класове ще се побере в един клас P. Ползите също могат да бъдат огромни. Ще се научим да пресмятаме бързо и то всичко.
Казват, че една програма никога не може да стане писател, както Photoshop никога не може да бъде Рафаел. Но ако P = NP, ще бъде само въпрос на време, преди някой да измисли как да се създадат доказуемо "велики" романи и картини с математическа ефективност.
В един свят, в който Р е доказано равно на NP, лесно можем да изчислим всичко. Да си представим, например, онколог, комуто вече не се налага да се бори с пробите и грешките на химиотерапията, защото "сега ще можем да разгледаме ДНК на човека, както и на мутиралия ДНК на раковите клетки, и да разработим протеини, които се огъват само по правилния начин, ефективно изтощавайки от глад раковите клетки, без да причиняват никакви проблеми за нормалните клетки", както обяснява Ланс Фортнау (Lance Fortnow) в книгата си "Златният билет: P, NP и Търсенето на невъзможното" (“The Golden Ticket: P, NP and the Search for the Impossible”).
Според Фортнау отношението между P и NP е "един от най-големите отворени проблеми за цялата математика", не само защото е изключително трудно да се реши, а защото има такива всеобхватни практически приложения. Това е мечтата за пълна лекота, за увереност, че има ефективен начин да се изчисли почти всичко, "от лекуването на смъртоносни болести до природата на Вселената", дори "алгоритмичен процес за разпознаване на величието", пише New Yorker.
Теорията на изчислителната сложност
Много математици, макар и не всички, са склонни да смятат, че отговорът на въпроса е отрицателен, т.е. че P всъщност не е равно на NP. Ако това е така, ще е много трудно да се докаже такова твърдение, защото трябва да анализираме всички "възможни" алгоритми и по някакъв начин да докажем, че никой от тях не става. Това изглежда много по-трудно от представата за един, дори и "сложен" алгоритъм, който решава конкретен проблем.
Като се има предвид, че P вероятно не е равно на NP, вероятно никога няма да бъдат намерени ефективни решения на проблемите NP - тогава защо е целият този шум?
Майкъл Сипсър (Michael Sipser), ръководител на катедрата по математика в Масачузетския технологичен институт (MIT), казва, че проблемът с P и NP е важен за задълбочаване на нашето разбиране за изчислителаната сложност (computational complexity).
Теорията на изчислителната сложност изучава проблемите. По-конкретно тя се опитва да класифицира колко "трудни" са те, доколко ефективно решение на изчисление може да се намери при реалистични условия.
Това е проблем на Computer Science ("Компютърна наука"). На английски език този термин е стандартен, но на български не може да се преведе буквално. Това е теоретична наука, а не програмиране. Това е сравнително нова област, която няма пряка връзка с числени методи и други подобни.
Движението е всичко, крайната цел е нищо
В едно интервю Скот Ааронсън (Scott Aaronson), компютърен учен от MIT, повтаря мисълта на Бернщайн, като твърди, че е важен пътят, а не целта:
Да, почти всички от нас смятат вече, че P не е равно на NP. Но това е едно от онези неща, които са посока, а не крайната цел на пътуването. За да се докаже твърдението, ще бъде необходимо огромно количество знания в едно ново разбиране за изчисленията. Какво се опитваме да докажем? Това означава, че ще бъде реално решаването на всички тези нелинейни оптимизационни задачи или тези проблеми за търсене, или доказателство на теорема за намирането на най-добрия график за авиокомпаниите, или криптографски кодове - всички тези неща, които сега нямат алгоритъм. Това е невероятно трудна задача. Така че можем да очакваме, че по пътя към доказването на това нещо ще научим огромно количество ефективни алгоритми, които са извън това, което вече знаем, и много, много е вероятно ще открием нови алгоритми, които вероятно ще имат приложения, които дори не можем да предвидим.
Често в историята на теоретичната компютърна наука идеите, които използваме, за да докажем, че нещо е невъзможно, могат да се обърнат, за да докажат, че нещо друго е възможно и обратното.
А ето един начин, по който бихте могли да използвате P ≠ NP следващият път, когато пропуснете крайния срок на работата си, когато решението някак си успява да ви убегне, кажете на много информирания си шеф: "Знаете, че P ≠ NP", а той ще бъде принуден да ви отговори: "Да, така е".
Ползата от математиката
Много млади хора и някои в съзнателна възраст твърдят, че математиката е безполезна наука, че след като завършим училище или институт, тя не може да ни бъде полезна в живота.
Но всъщност това не е така - математиката е създадена като механизъм, чрез който може да се опише и наблюдава нашия свят. Тя е навсякъде - във всеки дом, във всяка тревичка или облак.
"Не обвинявайте цветята, че слепите не могат да ги видят", казва руският историк Василий Ключевский.
И ако тази наука изглежда сложна, то и нашият свят не е толкова прост, колкото изглежда, и математиката му съответства, за да осигури основа за по-добро разбиране реалността.
Източници:
A New Map Traces the Limits of Computation, Quanta magazine
Explained: P vs. NP, MIT News
3 questions: P vs. NP, MIT News
Наконец-то! P?=NP и институт Клэя
P vs NP Problem, Clay Mathematics Institute
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
15914
1
20.09 2017 в 11:30
Последни коментари