Математика Што е P P NP
Александар Разборов се обложи на дваесет центи. Математичарот од Универзитетот во Чикаго го губи од колега кога ќе се покаже дека е точен доказ објавен пред две недели од професорот по компјутерски науки во Бон, Норберт Блум. Од друга страна, Блум би бил побогат за еден милион долари. Бидејќи неговиот доказ се однесува на таканаречениот проблем P = NP, една од шесте математички загатки за чие решение Американската фондација Клеј издвои милион во 2000 година. Седмиот веќе беше решен во 2002 година
Ефективно медиумското високо доделување ја означува посебната научна важност на овие таканаречени милениумски проблеми, но исто така и нивната претпоставена тешкотија, измерена и во однос на животот на математичарот, што е веќе потрошено во барање решение Но, P = 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-постапка - тоа е испитување на решение: Ако претставиш претпоставен прост фактор на влезниот број на компјутерот, лесно може да препознае дали тој е всушност главен фактор на влезот . Едноставна поделба е доволна.
Таквите проблеми, чии решенија можат полиномски да се проверат брзо, ја формираат класата НП. Од историски причини, кратенката значи „не-детерминистички полином“, а не „не-П“. Затоа што ако излезите од P-алгоритмите се генерираат полиномично брзо, тие, се разбира, исто така може да се проверат полиномично брзо. Значи P е подмножество на НП.
Ако P = NP, светот би бил сосема поинаков.
Но, се поставува прашањето: Дали не може брзото тестирање на решението секогаш да значи брза решавање на проблемот, дури и ако соодветниот метод на решение, алгоритмот, сè уште не е пронајден? Тогаш NP исто така би бил во P, така што двете класи би биле идентични: P = NP. Никој не знае дали е тоа така. Но, никој не знае дека не е така.
Денешното знаење сугерира дека P ≠ NP, и целата светска економија се заснова на тоа, колку што повеќе не би функционирало без безбедна енкрипција. Но, може да биде дека P = NP. И тогаш светот би бил сосема поинакво место.
Од една страна, комуникацијата тогаш веќе не би била безбедна. Математичарот Johnон Неш и укажа на ова на Американската агенција за национална безбедност во 1955 година - 16 години пред проблемот P = NP (што се разбира исто така лесно може да се нарече P ≠ NP проблем) формално да биде строг. Од друга страна, ефикасни алгоритми би биле возможни да се предвиди преклопувањето на протеините, на пример, што ќе направи револуција во медицината. Задачи за оптимизација во индустријата и истражувањето, но исто така и во војската, временски прогнози, вештачка интелигенција: каде и да се вклучени проблеми со НП, би бил можен напредок, чии последици за секојдневниот живот можеби не ги ни замислуваат авторите на научна фантастика. Доказ дека P = NP првично само теоретски ќе ја отвори вратата, но познавањето на основната изводливост многу веројатно ќе ослободи огромни енергии за наоѓање на ефикасни алгоритми.
Математика што сама по себе се отстранува
Импликациите на П = НП би биле уште подалекусежни: во 1956 година, една година по писмото на Неш до НСА, Курт Гадел, веројатно најважниот логичар од Аристотел, му напишал писмо на неговиот колега Johnон фон Нојман во кое ја опишал скоро морничавата последица на П. = Признаена НП за самата математика: „Тоа би значело јасно. дека интелектуалната работа на еден математичар може целосно да се замени со машини во случај на прашања да-не “. Кој докаже N = NP теоретски може да најде и алгоритам кој наоѓа формални докази за другите математички теореми - вклучувајќи ги и оние што се предмет на шесте Милениумските проблеми сè уште се нерешени. Наместо еден, тој тогаш заработи шест милиони долари.
Доказот на Норберт Блум за 11 август сега доаѓа од една страна смирувачки, а од друга страна досаден заклучок дека P ≠ NP. Само: тој е во право?
Краткиот одговор е дека 38-те страници на работа мора прво да бидат проверени од експерти, што може да потрае. Вистина е дека Александар Разборов и другите истражувачи кои работат во оваа област се состанаа на работилница во Центарот за математички истражувања во Оберволфах во Црната шума, токму во неделата кога Блум ја стави својата работа на Интернет. Сепак, Разборов не е свесен дека некој од учесниците одблизу ги разгледал доказите. „Треба да знаете дека имавме густ распоред“, вели тој. Остана со обложување.
Тој проблем со кликовите
Блум му пристапува на проблемот од позната страна: преку таканаречениот проблем со клика. Замислете училиште со голем број ученици, сите се познаваат, но не сите се познаваат. Сега му дадете список на спарени познаници на компјутер со задача да откриете дали постои група n студенти кои сите се познаваат едни со други. Овој проблем е НП и дури спаѓа во класа на проблеми наречени НП-комплетни. Овие се НП и во исто време „НП-тежок“, што значи дека секој друг проблем во НП може да се пронајде до таков проблем со полиномните напори. Доказ дека дури и само еден комплетен проблем со НП лежи во P, веднаш би докажал P = NP - и доказ дека не може да биде во P, докажете P ≠ NP.
Покажете целосна содржина во оригиналниот пост
Алгоритмите сега можат да бидат мапирани на формалните мрежни кола од логичките врски „и“, „или“ и негацијата и да покажат дека бројот на потребни врски расте полиномично само со влезот, дури и ако тоа го прави и оригиналниот алгоритам. Александар Разборов во 1985 година, во тоа време како докторски студент во Москва, докажа дека задачата за клика не може да се совлада со употреба на полиномски влез од растечките мрежи, се додека тие содржат само врски „и“ и „или“. Блум сега тврди дека го прилагодил методот на докажување така што теоремата на Разборов се однесува на сите мрежи, вклучително и на оние со негации. Што значи: Клике никогаш не е во P - и поради NP-комплетноста на проблемот со кликата, P ≠ NP.
Иако ова одговара на она што денес веруваат повеќето теоретски компјутерски научници, во моментов преовладува скептицизам. Можеби се сомнева и во фактот дека „не“ - додавање на негации при префрлување мрежи - треба да ја има оваа моќ, затоа што оваа опција сигурно била пред експертите подолго време. За математичар кој ја коментираше оваа тема на Интернет, доказот на Блум е во извесна смисла премногу конвенционален, не покажува кршење на комплетно нови патеки што би можеле да се очекуваат од докажувањето на теоремата за која многу експерти веќе нашле грешка . Дали Александар Разборов не можеше да ризикува поголем удел во Оберволфах? „Облогот беше 1: 1000“, вели тој. „И мојот колега веднаш ми ги даде 20-те центи. Ова може да се толкува како индикација за тоа како тој ја проценува шансата “.