Наука 2018-11-15T09:57:07+02:00
Українські Новини
Математики засумнівалися в правильності розв’язання "задачі тисячоріччя"

Математики засумнівалися в правильності розв’язання "задачі тисячоріччя"

Вінай Деолалікар.
Вінай Деолалікар.

Співробітник Массачусетського технологічного інституту (MIT) Скотт Ааронсон навів вісім причин, які змушують його думати, що Деолалікар не зміг розв’язати задачу тисячоріччя.

світу сумніваються в правомірності доведення однієї із задач тисячоріччя - питання про нерівність класів складності P і NP. Нагадаємо, що препринт статті, у якій доводилося, що вони не рівні, представив на початку серпня 2010 року індійський математик Віней Деолалікар. Втім, поки стаття не подана в реферований науковий журнал.

Як стало відомо, Деолалікар розіслав препринт статті кільком провідним математикам 6 серпня 2010 року. Також, на прохання колег учений підготував короткий опис свого доказу та виклав його в інтернеті. Однак за кілька днів у блогах деяких математиків з'явилися записи, у яких вони висловлювали сумніви в тому, що Деолалікару справді вдалося строго довести, що класи складності P і NP не рівні.

Зокрема, співробітник Массачусетського технологічного інституту (MIT) Скотт Ааронсон навів вісім причин, які змушують його думати, що Деолалікар не зміг розв’язати задачу тисячоріччя. Зі слів Ааронсона, у своїй статті Деолалікар не пояснює, чому його доказ не працює для деяких окремих задач. Також вчений зазначає, що стаття витримана не в класичному стилі та у ній немає виразного короткого пояснення, чому новий доказ зміг перебороти бар'єри, які заважали математикам розв’язати завдання тисячоріччя раніше.

Також сумнівається в правильності розв’язання задачі і  Річард Ліптон, який, як і Ааронсон, є одним з найбільших фахівців в галузі, до якої належить завдання тисячоріччя. У своєму блозі Ліптон перераховує кілька недоліків у доведенні Деолалікара, які, з високою ймовірністю, роблять його неправомірним.

Слід зазначити, що питання про рівність або нерівність класів складності P і NP надзвичайно важливий для математики, а також для теорії обчислень і наук про шифрування даних. Стисло завдання звучить так: якщо позитивну відповідь на якесь питання можна швидко перевірити, то чи правда, що відповідь на це питання можна швидко знайти? Наприклад, перед людиною стоїть завдання скласти найкоротший маршрут подорожі між декількома містами. Після того як маршрут складений, можна легко перевірити, чи справді він є найбільш коротким, однак розв’язати цю задачу (воно належить до класу складності NP) за невеликий час неможливо.

Архів
Новини

ok