P срещу NP: Най-голямото предизвикателство в информатиката и неговото значение

 


Разбиране на прословутия проблем $P$ срещу $NP$

Проблемът $P$ срещу $NP$ е не само най-голямото нерешено предизвикателство в информатиката, но може би и в цялата математика. Освен че е обект на награда от милион долара, предположението, че $P \neq NP$, е в основата на почти цялата интернет сигурност – от криптиране на кредитни карти до добива на биткойни. Доказателство, че $P = NP$, би разклатило тези основи и би довело до революция в разбирането ни за изчисленията и решаването на проблеми.

Ето един интуитивен начин за разбиране на проблема:

  • $P$ представлява всички проблеми, които могат да бъдат решени за полиномиално време.
  • $NP$ представлява всички проблеми, чиито решения могат да бъдат проверени за полиномиално време.

Полиномът (да, помните го от часовете по алгебра в училище) може да се разгледа като функция, в която всички степенни показатели на променливата са положителни цели числа, например $f(x) = 4x^5 + 7x^3 - x + 1.5$.

Пример за задача в $NP$ е известната задача за пътуващия търговец. В нея трябва да се намери маршрут, който минава през всички градове на картата и чиято дължина е по-малка от някаква фиксирана граница (например общо под 200 км). Проблемът се усложнява експоненциално с увеличаването на броя на градовете $n$. Съществуват $\frac{(n-1)!}{2}$ възможни маршрута, което за 100 града означава около $10^{155}$ маршрута за проверка. Това е невероятно голямо число! Макар че има по-ефективни методи от грубата сила, досега не е открит алгоритъм, който да решава този проблем за полиномиално време.

НО! Ако някой ми предостави даден маршрут, мога бързо да проверя дали той е в рамките на зададената граница от 200 км. Единственото, което трябва да направя, е да сумирам 100 разстояния и да отговоря с „да“ или „не“. Фактът, че решението може да бъде проверено за полиномиално време, прави задачата за пътуващия търговец част от $NP$.

Ако $P = NP$, това би означавало, че всички проблеми, които могат да бъдат проверени за полиномиално време, също могат да бъдат решени за полиномиално време. В свят, където $P = NP$, щяхме да разполагаме с алгоритъм, който решава задачата за пътуващия търговец за полиномиално време. А също така и задачи като:

  • задачата за сумиране на подмножества,
  • задачата за граф-клика,
  • алгоритъмът RSA, който криптира номера на кредитни карти,
  • криптографията с елиптични криви, използвана в Биткойн...

Разбирате идеята, нали?

Но... ако $NP$ е класът на проблемите, чиито решения могат да бъдат проверени, какво всъщност означава буквата „N“?

Недетерминистично изчисление



Буквата „N“ означава „недетерминистично“.
Класът от задачи $NP$ (обяснен по-горе като проблеми, които могат да бъдат проверени за полиномиално време) първоначално е дефиниран като такива, които могат да бъдат решени за полиномиално време от недетерминистична машина на Тюринг. Доказано е, че това определение е еквивалентно на интуитивното, което споменахме по-рано.

„$NP$ е множеството от проблеми за вземане на решения, за които примерите с отговор „да“ имат доказателства, проверими за полиномиално време от детерминистична машина на Тюринг,
или алтернативно – множеството от проблеми, които могат да бъдат решени за полиномиално време от недетерминистична машина на Тюринг.“ – Уикипедия

Вероятно сте любопитни какво всъщност представлява недетерминистичната машина на Тюринг.

Какво е недетерминистична машина на Тюринг?

Машината на Тюринг е теоретичен модел на компютър. Тя изпълнява инструкции (т.е. алгоритъм) за записване на символи върху „лента“, което я прави способна да решава почти всяка изчислителна задача, която можете да си представите.

Недетерминистичната машина на Тюринг е още по-абстрактен модел, който има възможността да преминава паралелно в множество състояния. Тя е наречена „недетерминистична“, защото следващото ѝ състояние не се определя изцяло от текущото.

Този модел е напълно нереалистичен – днес не разполагаме с компютри, които могат да работят в паралелни вселени и след това да се връщат в нашата с правилния резултат!

История на недетерминистичните машини



Концепцията за недетерминизъм е въведена през 1959 г. от Рабин и Скот в тяхната статия „Крайни автомати и техните задачи за решения“. В нея те описват:

„Недетерминистичният автомат не е вероятностна машина, а машина с много възможности за избор на ходове. На всеки етап той има свободата да избере едно от няколко нови вътрешни състояния. Ние приемаме, че машината приема дадена лента, ако има поне една успешна комбинация от избори, водеща до крайно състояние.“ – Рабин и Скот (1959)

Концепцията за недетерминизъм се утвърждава в рамките на модела на машините на Тюринг. През 1971 г. Стивън Кук публикува своята статия „Сложността на процедурите за доказване на теореми“, смятана за начало на проблема $P$ срещу $NP$. Той формулира проблема чрез недетерминистичните машини на Тюринг и идентифицира първата $NP$-пълна задача – задачата за удовлетворяемост на булеви формули (SAT).

През 1972 г. Ричард Карп разширява изследванията на Кук, като идентифицира 21 $NP$-пълни задачи, включително задачата Graph Clique и задачата за Хамилтонов цикъл (вариант на задачата за пътуващия търговец). Днес има хиляди известни $NP$-пълни проблеми.

Защо $P$ срещу $NP$, а не $P$ срещу $VP$?


Може би се питате: защо класът $NP$ е дефиниран чрез недетерминистични машини, вместо по-интуитивното определение за проблеми, които могат да бъдат проверени за полиномиално време?

Отговорът е прост: използването на недетерминистични машини на Тюринг дава общ подход към проблема. Те позволяват да разсъждаваме върху $P$ и $NP$ от гледна точка на решението („Какво е нужно, за да го намерим?“), вместо върху проверката на вече съществуващо решение.

Освен това математическото определение на недетерминистична машина на Тюринг е сходно с това на детерминистичната. Единствената разлика е, че функцията за преход към следващото състояние е заменена с релация за множество възможни състояния.

Заключение

Докато дефиницията чрез недетерминизъм е удобна за математиците, интуитивното определение за проверяемост е далеч по-ясно за повечето хора. И двете обаче са математически еквивалентни, което означава, че разбирането на едното автоматично води до разбирането на другото.


Коментари

Публикуване на коментар

Популярни публикации от този блог

Триъгълник. Сбор на ъгли в триъгълник. Външен ъгъл на триъгълник 7 клас

Изображение
В настоящият урок ще научим на колко е равен сборът от ъглите в произволен триъгълник, какво е външен ъгъл на триъгълник, на колко е равен сборът от външните ъгли в триъгълника, както и ще решим някои задачи. Нека разгледаме следният чертеж  Теорема 1: Сборът от ъглите на всеки триъгълник е равен на $180^{\circ}$ или $\alpha+\beta+\gamma=180^{\circ}.$ Като следствие от тази теорема, можем да кажем, че всеки триъгълник има най-много един тъп ъгъл, както и, че сборът от острите ъгли в правоъгълен триъгълник е равен на $90^{\circ}.$ Определение 1: Външен ъгъл на триъгълник се нарича ъгъл, съседен на вътрешен ъгъл на триъгълник ( в случая на чертежа външните ъгли са съответно $\alpha^{\prime}, \beta^{\prime}, \gamma^{\prime}$). Теорема 2: Всеки вънжен ъгъл на триъгълник е равен на сбора от двата несъседни на него вътрешни ъгли на триъгълник. Казано с други думи, от Теорема 2 можем да запишем равенствата $\alpha^{\prime}=\beta+\gamma$, $\beta^{\prime}=\alpha+...
Прочетете още

Височина, медиана и ъглополовяща към основата в равнобедрен триъгълник. Симетрала на отсечка 7 клас

Изображение
Ще започнем този урок, като припомним някои важни теореми, които ще използваме в решаването на задачите. Теорема 1: В равнобедрен триъгълник височината, медианата и ъглополовящата към основата му съвпадат. Теорема 2: Ако в един триъгълник височината и медианата през един от върповете съвпадат, триъгълникът е равнобедрен. Теорема 3: Ако в един триъгълник височината и ъглополовящата през един от върховете съвпадат, триъгълникът е равнобедрен. Теорема 4: Ако в един триъгълник медианата и ъглополовящата през един от върховете съвпадат, триъгълникът е равнобедрен. Теорема 5: В равностранен триъгълник всички височини, медиани и ъглополовящи са равни. Определение 1: Права, която е пепендикулярна на дадена отсечка и минава през средата й, се нарича симетрала на тази отсечка. Симетралата на отсечката $AB$ ще отбелязваме с $s_{AB}$. Теорема 6: Всяка точка от симетралата на дадена отсечка е на равни разстояния от краищата на отсечката. Теорема 7: Всяка...
Прочетете още

Ъгли получени при пресичането на две прави с трета. Теореми признаци, за успоредност на две прави 7 клас

Изображение
Нека разгледаме следният чертеж: Имаме две прави $a$ и $b$, които са пресечени с трета права $c$. Както се вижда от чертежа се образуват осем ъгъла, които имат специални имена. Определение 1: Двойките ъгли $\sphericalangle 3$ и $\sphericalangle 5$; $\sphericalangle 4$ и $\sphericalangle 6$ се наричат вътрешни кръстни ъгли, а двойките $\sphericalangle 1$ и $\sphericalangle 7$; $\sphericalangle 2$ и $\sphericalangle 8$ се наричат външни кръстни ъгли. Определение 2: Двойките ъгли $\sphericalangle 1$ и $\sphericalangle 5$; $\sphericalangle 2$ и $\sphericalangle 6$; $\sphericalangle 3$ и $\sphericalangle 7$; $\sphericalangle 4$ и $\sphericalangle 8$ се наричат съответни ъгли. Определение 3: Двойките ъгли $\sphericalangle 3$ и $\sphericalangle 6$; $\sphericalangle 4$ и $\sphericalangle 5$ се наричат вътрешни прилежащи ъгли, а двойките $\sphericalangle 1$ и $\sphericalangle 8$; $\sphericalangle 2$ и $\sphericalangle 7$ се наричат външни прилежащи ъгли. Теорема 1: Ако п...
Прочетете още