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

Учений опублікував 100-сторінкову статтю, у якій довів, що класи складності P і NP не рівні.

Індійський математик Вінай Деолалікар представив докази розв’язання однієї із "задач тисячоліття". Учений опублікував 100-сторінкову статтю, у якій довів, що класи складності P і NP не рівні. Препринт статті у форматі pdf можна скачати тут . Коротко про роботу написало видання New Scientist.

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

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

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

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