50-летнее путешествие Теории Сложности к пределам знаний
50-year journey of Complexity Theory to the limits of knowledge
.fav_bar { float:left; border:1px solid #a7b1b5; margin-top:10px; margin-bottom:20px; } .fav_bar span.fav_bar-label { text-align:center; padding:8px 0px 0px 0px; float:left; margin-left:-1px; border-right:1px dotted #a7b1b5; border-left:1px solid #a7b1b5; display:block; width:69px; height:24px; color:#6e7476; font-weight:bold; font-size:12px; text-transform:uppercase; font-family:Arial, Helvetica, sans-serif; } .fav_bar a, #plus-one { float:left; border-right:1px dotted #a7b1b5; display:block; width:36px; height:32px; text-indent:-9999px; } .fav_bar a.fav_de { background: url(../images/icons/de.gif) no-repeat 0 0 #fff } .fav_bar a.fav_de:hover { background: url(../images/icons/de.gif) no-repeat 0 0 #e6e9ea } .fav_bar a.fav_acm_digital { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_acm_digital:hover { background:url(‘../images/icons/acm_digital_library.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_pdf { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #FFF; } .fav_bar a.fav_pdf:hover { background:url(‘../images/icons/pdf.gif’) no-repeat 0px 0px #e6e9ea; } .fav_bar a.fav_more .at-icon-wrapper{ height: 33px !important ; width: 35px !important; padding: 0 !important; border-right: none !important; } .a2a_kit { line-height: 24px !important; width: unset !important; height: unset !important; padding: 0 !important; border-right: unset !important; border-left: unset !important; } .fav_bar .a2a_kit a .a2a_svg { margin-left: 7px; margin-top: 4px; padding: unset !important; }
В первую неделю осеннего семестра 2007 года Марко Кармозино пополз на математический курс, обязательный для всех студентов компьютерных наук в Университете Массачусетса, Амхерст. Кармозино, студент второго курса, собирался бросить учебу в колледже и заняться разработкой видеоигр. Но тогда преподаватель задал простой вопрос, который изменил ход его жизни: Как ты знаешь, что математика действительно работает?
“Это заставило меня прямо сесть и обратить внимание”, вспоминает Кармозино, который сейчас является теоретическим компьютерным ученым в IBM. Он записался на дополнительный семинар о работе Курта Гёделя, чьи ошеломляющие самореферентные аргументы впервые выявили ограничения математического рассуждения и заложили основу для всех будущих работ о фундаментальных границах вычислений. Это было много для усвоения.
“Я на 100% не понимал”, – сказал Кармозино. – “Но я знал, что хочу понять”.
Сегодня даже опытные исследователи испытывают недостаток понимания, когда сталкиваются с центральным открытым вопросом в теоретической компьютерной науке, известным как проблема P против NP. В сущности, этот вопрос спрашивает, можно ли решить многие вычислительные проблемы, которые долгое время считались крайне сложными, легко (по секретному пути, который мы еще не открыли), или же, как предполагает большинство исследователей, они действительно сложные. На кону стоит ничто иное, чем природа того, что можно знать.
Источник: Quanta Magazine Полная статья
