Одну из так называемых задач тысячелетия, объявленных американским Институтом Клэя, решил россиянин Григорий Перельман, за что ему была присуждена премия размером в миллион долларов. Похоже, что российские ученые замахнулись еще на одну проблему — ее решение предложил Владимир Романов из Владимирского университета. Речь идет о так называемой гипотезе P=NP, одной из ключевых проблем теории алгоритмов.

Суть дела в следующем. Допустим, у нас есть некий вопрос, который имеет решения на двух уровнях сложности: общем (задача класса NP) и конкретном (задача класса P). На уровне общего рассуждения мы должны доказать, что у задачи существует положительное решение, а на конкретном уровне — это решение найти. Вопрос в следующем: если мы можем быстро доказать первое, означает ли это, что мы можем так же быстро найти второе? Другими словами, равны ли между собой эти классы сложности или нет. Если равенство классов будет доказано, это будет иметь далеко идущие последствия для всего, что в современном мире требует алгоритмизации.

Попытки доказать это равенство публикуются в мировой научной печати примерно раз в месяц, но из-за откровенной халтурности работ особого внимания они не вызывают. Однако, как утверждают специалисты, у профессора Владимира Романова есть все шансы на лавры. Свое доказательство он опубликовал на знаменитом сайте arXiv.org — там же, где появилась статья с доказательством Перельмана, имя которого было тогда никому не известно. Никому не известно сегодня и имя Романова, но скоро все может измениться.
Источник: rusrep.ru

загрузка...