Математика Какво представлява P ≠ NP
Александър Разборов заложи двадесет цента. Математикът от Чикагския университет го губи от колега, когато се оказва, че доказателство, публикувано преди две седмици от професора по компютърни науки в Бон Норберт Блум, е вярно. Blum, от друга страна, би бил с един милион долара по-богат. Тъй като неговото доказателство се отнася до така наречения проблем P = NP, един от шестте математически пъзела, за решението на които Американската фондация Клей задели милион през 2000 г. Седмата вече беше решена през 2002 г.
Ефективното от медиите високо дарение отбелязва особената научна значимост на тези така наречени проблеми на хилядолетието, но също така и предполагаемата им трудност, измерена и по отношение на живота на математика, който е пропилян в търсене на решение. Но P = NP има специална позиция сред проблемите на хилядолетието.
NP означава: труден за решаване, лесен за проверка
Това в никакъв случай не е само научно важно, тъй като засяга основната технология на днешната цивилизация - компютъра. P и NP са и двете групи от възможни задачи, които могат да бъдат обработвани от цифрови компютри с помощта на алгоритми. Например задачата за сортиране на списък с n числа според размера. Въпросът сега е колко бързо се увеличава изчислителното време с размера на входа. При сортиране компютърът се нуждае, в най-лошия случай, четири пъти по-дълго за списък, който е два пъти по-дълъг - изчислителното време се увеличава квадратично или с n⊃2;. Това n⊃2; е прост пример за това, което математиците наричат полином. Следователно сортирането принадлежи към така наречения клас на сложност P като полином. Това би включвало и задача, за която необходимото изчислително време, да речем, с n⊃3; се увеличава, или n⊃1; ⁰ или n⊃3; + n⊃2;. Това са всички полиноми и съвременните компютри обикновено се справят доста добре с проблемите с P, дори и с високи n.
За много задачи обаче не са известни алгоритми, които доказват, че принадлежат на P, а само тези, чието изчислително време се увеличава с входа, например също като 2, т.е.експоненциално. За все по-големи дължини на въвеждане n, компютрите се забавят толкова бързо, че дори най-мощните мейнфрейм компютри ще бъдат заети с практически подходящи n за милиарди години. Един от проблемите, за които има само такива алгоритми, е разлагането на n-цифрените числа на фактори. Това се използва, например, общите методи за криптиране в Интернет: Те не могат да бъдат взломени директно, ако дължината на ключа n е достатъчно висока, тъй като това би изисквало такова разлагане на факторизация и няма метод, с който прекъсвачът на кода да може да постигне целта си за поносимо време . Това, което обаче остава просто тук - т.е. да се обработи с P-процедура - това е изследването на решение: Ако представите на компютъра предполагаем прост фактор на входното число, той лесно може да разпознае дали всъщност е основен фактор на входа . Достатъчно е просто разделяне.
Такива задачи, чиито решения могат да бъдат проверени полиномиално бързо, образуват клас NP. По исторически причини съкращението означава „недетерминиран полином“, а не „не-P“. Защото, ако изходите на P-алгоритмите се генерират полиномиално бързо, те, разбира се, също могат да бъдат проверени полиномиално бързо. Така че P е подмножество на NP.
Ако P = NP, светът би бил съвсем различен.
Но въпросът е: Не е ли възможно бързата проверимост на решението винаги да означава бърза разрешимост на проблема, дори ако съответният метод за решение, алгоритъмът, все още не е намерен? Тогава NP също ще бъде в P, така че двата класа ще бъдат еднакви: P = NP. Никой не знае дали е така. Но никой не знае, че това не е така.
Днешните знания показват, че P ≠ NP и цялата световна икономика се основава на него, доколкото той вече не би функционирал без сигурно криптиране. Но може да е P = NP. И тогава светът би бил съвсем различно място.
От една страна, комуникацията тогава вече няма да бъде сигурна. Математикът Джон Неш посочи това пред Американската агенция за национална сигурност през 1955 г. - 16 години преди проблемът P = NP (който, разбира се, също толкова лесно може да се нарече проблем P P NP) беше официално строг. От друга страна, биха били възможни ефективни алгоритми, за да се предскаже сгъването на протеини, например, което би революционизирало медицината. Задачи за оптимизация в промишлеността и научните изследвания, но също така и във военната сфера, прогнози за времето, изкуствен интелект: навсякъде, където са включени проблеми с NP, ще бъде възможен напредък, последствията от който за ежедневието може дори да не бъдат представени от авторите на научната фантастика. Доказателство, че P = NP първоначално само теоретично ще отвори вратата, но познаването на принципната осъществимост много вероятно ще освободи огромни енергии за намиране на ефективните алгоритми.
Математика, която премахва себе си
Последиците от P = NP биха били още по-мащабни: през 1956 г., година след писмото на Наш до НСА, Курт Гьодел, вероятно най-важният логик от Аристотел, пише писмо до колегата си Джон фон Нойман, в което описва почти странно последствие от П. = NP за самата математика призна: „Това би означавало ясно. че интелектуалната работа на математик може да бъде напълно заместена от машини в случай на да-не въпроси. “Който докаже N = NP, теоретично може да намери и алгоритъм, който намира формални доказателства за други математически теореми - включително тези, които са предмет на шест Проблемите на хилядолетието все още са нерешени. Вместо един, тогава той спечели шест милиона долара.
Доказателството на Норберт Блум от 11 август сега стига до успокояващото от една страна, а от друга до скучното заключение, че P ≠ NP. Само: прав е?
Краткият отговор е, че 38-те страници трябва първо да бъдат проверени от експерти, което може да отнеме време. Вярно е, че Александър Разборов и други изследователи, работещи в тази област, се срещнаха за семинар в Математическия изследователски център в Оберволфах в Шварцвалд, точно в седмицата, когато Блум пусна работата си в Интернет. Но Разборов не е наясно, че някой от участниците е разгледал внимателно доказателствата. „Трябва да знаете, че имахме тясна програма“, казва той. Оставаше при правенето на залози.
Този проблем с кликите
Блум подхожда към проблема от позната страна: чрез така наречения проблем с клика. Представете си училище с голям брой ученици, всички се познават, но не всички се познават. Сега давате списъка на сдвоените познати на компютър със задачата да разберете дали има група от n ученици, които всички се познават. Този проблем е NP и дори принадлежи към клас проблеми, наречени NP-complete. Това са NP и в същото време са "NP-трудни", което означава, че всеки друг проблем в NP може да бъде проследен до такъв проблем с полиномиални усилия. Доказателство, че дори NP-пълен проблем всъщност също е в P, веднага ще докаже P = NP - а доказателството, че не може да бъде в P, доказва P ≠ NP.
Показване на цялото съдържание в оригиналната публикация
Алгоритмите вече могат да бъдат картографирани върху мрежи на формални вериги от логическите връзки „и“, „или“ и отрицанието и показват, че броят на необходимите връзки нараства само полиномиално с входа, дори ако оригиналният алгоритъм прави това също. Александър Разборов доказа през 1985 г., по това време като докторант в Москва, че задачата на кликата не може да бъде овладяна с помощта на полиномиален вход от нарастващи мрежи, при условие че те съдържат само връзки „и“ и „или“. Сега Блум твърди, че е адаптирал метода на доказателство, така че теоремата на Разборов да се прилага за всички мрежи, включително тези с отрицания. Което означава: Clique никога не е в P - и поради NP-пълнотата на проблема с кликата, P ≠ NP.
Въпреки че днес в това вярват повечето теоретични компютърни учени, в момента преобладава скептицизмът. Фактът, че „не“ - добавянето на отрицания в комутационните мрежи - трябва да има тази сила, може би също се съмнява, защото тази опция трябва да е била пред експертите от дълго време. За математик, който коментира темата в Интернет, доказателството на Блум е в известен смисъл твърде конвенционално, не показва прекъсването на напълно нови пътища, които бихме могли да очакваме от доказателството на теорема, която толкова много експерти вече са намерили за недостатък . Не можеше ли Александър Разборов да рискува по-висок дял в Оберволфах? „Залогът беше 1: 1000“, казва той. „И колегата ми даде веднага 20-те цента. Това може да се тълкува като индикация за това как той оценява шанса. "