Математика Що таке P ≠ NP?
Олександр Разборов поставив двадцять центів. Математик з Чиказького університету програє його колезі, коли виявляється, що доказ, опублікований два тижні тому професором Боннської інформатики Норбертом Блумом, є вірним. З іншого боку, Блюм був би багатшим на мільйон доларів. Оскільки його доказ стосується так званої задачі P = NP, однієї з шести математичних головоломок, на рішення якої Американський фонд Глини виділив мільйон у 2000 році. Сьома вже була вирішена в 2002 році
Медіа-ефективна висока обдарованість відзначає особливу наукову важливість цих так званих проблем тисячоліття, а також їх передбачувану складність, виміряну також з точки зору життя математика, яке вже було витрачено даремно на пошуки рішення. Але P = NP займає особливе місце серед проблем тисячоліття.
NP означає: важко вирішити, легко перевірити
Це далеко не лише науково важливо, оскільки воно впливає на основну технологію сучасної цивілізації - комп’ютер. P і NP - це набори можливих завдань, які можуть бути оброблені цифровими комп’ютерами за допомогою алгоритмів. Наприклад, завдання сортування списку з n чисел за розміром. Питання зараз полягає в тому, як швидко обчислювальний час збільшується із збільшенням розміру вхідних даних. При сортуванні комп’ютеру потрібно, у гіршому випадку, в чотири рази більше списку, що вдвічі довший - час обчислень збільшується в квадратичному порядку або з n with2;. Це n⊃2; є простим прикладом того, що математики називають багаточленом. Отже, сортування належить до так званого класу складності P, як поліном. Це також включало б завдання, для якого необхідний обчислювальний час, скажімо, з n with3; збільшується, або n⊃1; ⁰ або n⊃3; + n⊃2;. Це всі поліноми, і сучасні комп’ютери, як правило, досить добре справляються з проблемами P, навіть з великим n.
Однак для багатьох завдань не відомі алгоритми, які доводять, що вони належать P, а лише ті, чий обчислювальний час збільшується із входом, наприклад, наприклад, 2ⁿ, тобто експоненційно. При все більшій довжині вводу n комп’ютери уповільнюються так швидко, що навіть найпотужніші комп’ютери мейнфреймів будуть зайняті практично відповідними n протягом мільярдів років. Однією з проблем, для якої існують лише такі алгоритми, є розкладання n-значних чисел на фактори. Для цього використовуються, наприклад, загальнодоступні методи шифрування в Інтернеті: їх неможливо зламати безпосередньо, якщо довжина ключа n досить велика, оскільки для цього потрібна така факторизація, і немає методу, за допомогою якого вимикач коду міг би досягти своєї мети за допустимий час . Однак те, що залишається простим тут - тобто обробляти за допомогою P-процедури, - це перевірка рішення: якщо ви подаєте на комп’ютер передбачуваний простий коефіцієнт вхідного числа, йому легко зрозуміти, чи насправді це простий фактор вхідного . Досить простого поділу.
Такі задачі, рішення яких можна поліноміально швидко перевірити, утворюють клас NP. З історичних причин абревіатура означає "недетермінований поліном", а не "не-Р". Оскільки якщо виходи P-алгоритмів генеруються поліноміально швидко, їх, звичайно, також можна перевірити поліноміально швидко. Отже, P - підмножина NP.
Якби P = NP, світ був би зовсім іншим.
Але питання полягає в тому: чи не може бути так, що швидка перевірочність рішення завжди означає швидку розв’язаність проблеми, навіть якщо відповідний метод рішення, алгоритм, ще не знайдений? Тоді NP також буде в P, тож два класи будуть однаковими: P = NP. Ніхто не знає, чи це так. Але ніхто не знає, що це теж не так.
Сучасні знання свідчать про те, що P ≠ NP, і на ньому базується вся світова економіка, оскільки вона більше не буде функціонувати без безпечного шифрування. Але може бути так, що P = NP. І тоді світ став би зовсім іншим місцем.
З одного боку, спілкування тоді вже не буде безпечним. Математик Джон Неш вказував на це Американському агентству національної безпеки в 1955 році - за 16 років до того, як проблема P = NP (яку, звичайно, так само легко назвати проблемою P P NP), була офіційно жорсткою. З іншого боку, ефективні алгоритми могли б передбачити згортання білків, наприклад, що зробило б революцію в медицині. Завдання оптимізації у промисловості та наукових дослідженнях, а також у військовій галузі, прогнози погоди, штучний інтелект: де б не стосувались проблем НП, можливий прогрес, наслідки якого для повсякденного життя автори наукової фантастики можуть навіть не уявити. Доказ того, що P = NP спочатку лише теоретично відкрив би двері, але знання фундаментальної доцільності дуже ймовірно вивільнило б величезні енергії для пошуку ефективних алгоритмів.
Математика, яка знищує себе
Наслідки P = NP будуть ще більш далекосяжними: у 1956 році, через рік після листа Нєша до АНБ, Курт Гедель, мабуть, найважливіший логік з часів Арістотеля, написав листа своєму колезі Джону фон Нейману, в якому описав майже моторошні наслідки П. = NP для самої математики визнано: «Це означало б ясно. що інтелектуальна робота математика може бути повністю замінена машинами у разі запитань так-ні ". Хто доводить N = NP, теоретично також може знайти алгоритм, який знаходить формальне підтвердження інших математичних теорем - включаючи ті, що є предметом шести Проблеми тисячоліття все ще залишаються невирішеними. Замість одного він тоді заробив шість мільйонів доларів.
Доказ Норберта Блума від 11 серпня тепер приходить до, з одного боку, заспокійливого, а з іншого боку, нудного висновку, що P ≠ NP. Тільки: він правий?
Коротка відповідь полягає в тому, що 38 сторінок роботи спочатку повинні перевірити експерти, що може зайняти час. Це правда, що Олександр Разборов та інші дослідники, що працюють у цій галузі, зустрілися на семінарі в Центрі математичних досліджень в Обервольфаху, що у Шварцвальді, якраз у той тиждень, коли Блум розмістив свою роботу в Інтернеті. Однак Разборову невідомо, що хтось із учасників уважніше розглянув докази. "Ви повинні знати, що у нас був щільний графік", - говорить він. Залишалося робити ставки.
Ця проблема з кліками
Блум підходить до проблеми зі звичного боку: через так звану проблему клік. Уявіть собі школу з великою кількістю учнів, усі знають одне одного, але не всі знають одне одного. Тепер ви даєте список парних знайомих на комп’ютер із завданням з’ясувати, чи існує група російських студентів, які всі знають один одного. Ця проблема є NP і навіть належить до класу задач, що називається NP-повною. Це NP і водночас "NP-важко", що означає, що будь-яку іншу задачу в NP можна простежити до такої проблеми за допомогою поліноміального зусилля. Доказ того, що навіть NP-повна проблема насправді також знаходиться в P, тоді негайно доведе P = NP - а доказ того, що вона не може бути в P, доводить P ≠ NP.
Показати повний вміст в оригінальній публікації
Алгоритми тепер можна відобразити на формальних мережах з логічних зв’язків “і”, “або” та заперечення і показати, що кількість необхідних зв’язків зростає лише поліноміально із входом, навіть якщо оригінальний алгоритм це теж робить. Олександр Разборов довів у 1985 р., На той час ще докторантом у Москві, що завдання кліки не можна засвоїти, використовуючи поліноміальний вхід від зростаючих мереж, за умови, що вони містять лише посилання «і» та «або». Зараз Блум стверджує, що скоригував метод доказу таким чином, щоб теорема Разборова застосовувалась до всіх мереж, включаючи мережі з негаціями. Що означає: Кліке ніколи не буває в P - і завдяки NP-повноті проблеми кліки, P ≠ NP.
Хоча саме так вважає сьогодні більшість теоретиків-комп’ютерників, скептицизм на сьогодні переважає. Той факт, що "ні" - додавання заперечень у комутації мереж - повинен мати цю силу, можливо, також сумнівається, оскільки цей варіант, мабуть, був довгий час перед експертами. Для математика, який коментував цю тему в Інтернеті, доказ Блума в певному сенсі занадто умовний, не показує розриву абсолютно нових шляхів, яких можна було б очікувати від доказу теореми, в якій так багато експертів вже знайшли помилку . Чи не міг Олександр Разборов ризикнути вищим пакетом акцій Обервольфаха? "Ставка була 1: 1000", - говорить він. «І мій колега відразу дав мені 20 центів. Це можна трактувати як вказівку на те, як він оцінює шанс ".