Математик заявив про вирішення однієї з задач тисячоліття

8
11 серпня 2010

Індійський математик Віней Деолалікар представив докази вирішення однієї з так званих задач тисячоліття, - вчений опублікував 100-сторінкову статтю, в якій зроблено висновок, що класи складності P і NP не рівні.

Коротко про роботу науковця йдеться у New Scientist, пише Лента.ру.

Питання про рівність класів складності P і NP можна сформулювати так: якщо позитивну відповідь на якесь питання можна швидко перевірити, то чи правда, що відповідь на це питання можна швидко знайти?

Це завдання надзвичайно важлива для комп'ютерних обчислень і прикладних наук, зокрема для наук про шифрування даних. Наприклад, якщо можна швидко перевірити, чи є введений шифр правильним, то чи можна досить швидко зламати цей шифр?

Доказ, що класи складності P і NP не рівні, означає, що відповіді на подані вище два питання будуть негативними. Іншими словами, перевірка шифру і його підбір є завданнями різного класу складності.

Наразі експертне співтовариство не винесло однозначної думки з приводу статті Деолалікара. Варто очікувати, що оцінки інших математиків щодо строгості і правомірності доказу почнуть з'являтися після того, як буде опубліковано остаточний варіант статті. Планується, що це відбудеться протягом тижня.

Задачі тисячоліття - це сім задач, за вирішення кожної з яких математичний інститут Клея пропонує приз розміром в один мільйон доларів. Однією з таких завдань було доказ гіпотези Пуанкаре.

Приз за вирішення цього завдання був присуджений російському математику Григорію Перельману, який, проте, відмовився від грошей, аргументувавши це тим, що не згоден з рішенням інституту Клея.

powered by lun.ua