Как сообщила в среду газета Boston Global, решение одной из наиболее сложных проблем современной математики может лежать в самом необычном месте, которое только можно придумать: в принципе, на котором основана одна из самых популярных офисных игр – Minesweeper или просто «Сапер».
Математическая гипотеза о вычисляемых и невычисляемых задачах считается настолько важной для современных прикладных дисциплин, что в мае нынешнего года учредил премию размером в миллион долларов за решение этой задачи.
Многие распространенные проблемы легко решаются с помощью компьютера. Это так называемые вычисляемые или "P"(полиномиальные)-проблемы. Другие же, как, например, расшифровка кодов, используемых для защиты интернет-коммуникаций, с точки зрения большинства ученых, не рещаются на компьютере. Этот тип проблем носит название проблем “NP” (невычисляемых, неполиномиальных). Доказательство того, что это разделение ложно, и вычислению подлежит любая проблема, может означать, что современные шифровальные технологии легко нейтрализуются, надо только знать, как их атаковать.
В этой связи возникают принципиальные вопросы, привлекшие за последние 30 лет значительное внимание исследователей. Общий смысл этих вопросов заключается в следующем. Пусть для задачи не удается сконструировать алгоритм решения, несмотря на серьезные усилия многих математиков. В чем причина этих неудач - в том, что такой алгоритм не существует вовсе, или в том, что он все-таки существует, но найти его очень трудно?
Некоторые математики полагают, что проблемы “NP” на самом деле алгоритмизируются также легко, как и “P”-проблемы: просто никто еще не нашел простого способа их решить. Доказательство этой гипотезы явилось бы выдающимся математическим результатом.
Большинство специалистов склоняются к тому, что такого доказательства не существует, но в целом вопрос остается открытым и привлекающим значительное внимание исследователей.
Майкл Сипсер, профессор математики в , провел два десятилетия или «свыше 15 тысяч часов» в попытках решить, являются ли неполиномиальные задачи на самом деле полиномиальными. Тем не менее, пока гипотеза осталась недоказанной. По мнению Сипсера, доказательство этой гипотезы является попыткой с математической достоверностью установить границу, дальше которой не может развиваться ни один, даже самый мощный, компьютер.
В весеннем номере журнала английские специалисты по математической логике доказали, что гипотеза о тождестве "решаемых" и "нерешаемых" задач станет аксиомой, если кто-то найдет алгоритм игры в «Сапер». В среду в Гарварде состоялась специальная математическая конференция, посвященная этой незатейливой игре. Игра не выглядит особенно сложной и, с первого взгляда, не может привлечь серьезного внимания ученых-теоретиков. Однако, фокус заключается в том, что эта игра на первый взгляд кажется логически вычисляемой, но в какой-то момент в процессе "открывания мин" логика перестает действовать, и игроку приходится действовать наугад.
Эксперты считают, что тот, кто напишет программу для полного и логического решения «Сапера», будет занесен в сонм величайших математиков на свете, его имя будет стоять рядом с именами Пифагора и Эйлера. Ну и, конечно, этот великий математик получит 1 миллион долларов в качестве поощрительного приза.
Copyright © 2000-2002 Нетоскоп