Знайомі з наукою люди чули про одну з найбільших проблем математики – так звану «проблему рівності класів P та NP». Але це не просто чудернацька математична головоломка. Людина, яка її вирішить, миттєво стане на мільярди доларів багатшою, адже вона зможе повелівати всіма криптовалютами. І зможе, наприклад, присвоїти усі Bitcoin у світі.
Важливість проблеми P vs NP показує те, що її додали в одну із семи задач списку «Задачі тисячоліття» (Millennium Prize Problems)». За вирішення такої задачі кембриджський Математичний інститут Клея видає $1 млн. Але це дріб’язок, якщо порівняти з тим, які можливості відкриваються у випадку, якщо P = NP.
«Якщо хтось доведе, що P = NP, перша річ, яку вони повинні зробити, – вкрасти $200 млрд у Bitcoin, – каже науковець Скотт Ааронсон. – Друга річ, яку вони повинні зробити, – вирішити всі інші задачі списку «Задачі тисячоліття».
Загалом проблему рівності P = NP можна описати так: якщо ствердну відповідь на питання можна досить швидко перевірити, то чи правда, що відповідь на це питання можна досить швидко знайти. Якщо зовсім коротко: чи дійсно рішення задачі перевірити не легше, ніж його відшукати?
Наслідки, якщо виявиться P = NP, будуть масштабними через особливість роботи комп’ютерів. Для обрахунку задач процесор виконує набір кроків. Чим складніша задача, тим більше кроків потрібно. Символом «P» позначають задачі, які комп’ютери вирішують постійно: від множення чисел до серфінгу в інтернеті. Зі зростанням складності задачі час для її вирішення зростає поліноміально, тобто в декілька разів швидше.
Існує багато проблем, для яких можна швидко оцінити правильність запропонованого рішення. Однак відшукати це рішення потребує значно більше часу. Такий тип задач називається недетермінований поліноміальний час (Nondeterministic Polynomial time), або проблеми NP. З такими задачами знайомий майже кожен. Наприклад, судоку є NP-проблемою – складно вирішити, легко перевірити.
Основою криптографії сучасних комп’ютерів є задача NP – розкладання дуже великих чисел на прості числа. Нині на це потрібно дуже багато часу, але перевірити розкладання просто – потрібно лише перемножити запропоновані прості числа. Криптографія, у свою чергу, є основою для віртуальних грошей, з Bitcoin включно.
Очікувалося, що ривок у задачах P та NP дадуть квантові комп’ютери, які б змогли швидко вирішувати найскладніші задачі NP і відкрити шлях до вирішення будь-яких задач NP. Але хайп пройшов, і людство продовжує користуватися звичайними кремнієвими процесорами, а квантовий комп’ютер все ще дивина, яка вирішує дуже обмежене коло задач. Утім, ще рано втрачати надії: прогнозується, що блокчейн Bitcoin зламають десь до 2027 року.
За матеріалами: Gizmodo
