Одну из «задач тысячелетия», объявленных американским Институтом Клэя, решил россиянин Григорий Перельман, за что ему был присужден миллион долларов. Похоже, что наши ученые замахнулись еще на одну проблему — ее решение предложил Владимир Романов из Владимирского университета. Речь идет о гипотезе P=NP, одной из ключевых проблем теории алгоритмов.
Суть дела в следующем. Допустим, у нас есть некий вопрос, который имеет решения на двух уровнях сложности: общем (задача класса NP) и конкретном (задача класса P). На уровне общего рассуждения мы должны доказать, что у задачи существует положительное решение, а на конкретном уровне — это решение найти. Вопрос в следующем: если мы можем быстро доказать первое, означает ли это, что мы можем так же быстро найти второе? Другими словами, равны ли между собой эти классы сложности или нет. Если равенство классов будет доказано, это будет иметь далеко идущие последствия для всего, что требует алгоритмизации.
Как утверждают специалисты, у профессора Владимира Романова есть все шансы на лавры. Свое доказательство он опубликовал на знаменитом сайте arXiv.org — там же, где появилась статья с доказательством Перельмана.
Источник: //arxiv.org/abs/1011.3944v2.
