Эта техносреда – об одной из центральных проблем информатики. Включая многопроцессорный компьютер, пользуясь интернетом, открывая электронную почту или отправляя номер кредитной карты в интернет-магазин, мы редко задумываемся о математике, которая стоит за сложными компьютерными системами. Создают ее ученые-информатики, а воплощают в жизнь конструкторы компьютерных систем. Что можно понять в этой математике и взять для себя – без специальной подготовки? Сегодня у нас есть возможность «попробовать на вкус» теорему «о равенстве классов сложности P и NP». За решение этой проблемы Clay Mathematics Institute of Cambridge предлагает приз в 1 миллионов долларов.
У нас в гостях Алексей Винокуров, выпускник МФТИ, PhD (информатика). Его профессиональные интересы включают: искусственный интеллект, Machine Learning (машинное обучение), Information Retrieval (поиск информации), алгоритмы обработки больших объемов текстов, видео и графической информации. Его научная карьера состоялась в University of London и University of Southampton. Сейчас он работает в частной компании в Кембридже, Англия.
6-го августа появилось доказательство теоремы о том, что классы сложности P и NP неравны. Его представил сотрудник Hewlett-Packard Research Labs по имени Vinay Deolalikar. Показательно, что сотрудник крупной компании занимается теоретическими проблемами. Не только государство, но и крупный бизнес США вкладывает значительные средства в разработки с долгими циклами окупаемости.
Его ищут уже 30 лет, и появление этой работы вызвало ожидаемый всплеск в информатике. Однако в работе были найдены определенные проблемы, которые ставят под сомнение корректность доказательства. История этого доказательства развивается в живом времени.
Вопрос Алексею Винокурову: Как можно объяснить задачу о равенстве классов сложности P и NP, не прибегая к специальным знаниям, т.е. «для чайников»?
Алексей Винокуров: В принципе, очень просто. Полиномиальные задачи сродни задачам, решение которых "линейно": чтобы приготовить бутерброд, нужно намазать масло на хлеб, а сверху положить сыр. Просто и быстро. Неполиномиальные – это, грубо говоря, те, в которых вам нужно найти иголку в стоге сена, причем практически единственный способ – просто перерыть весь стог. В общем – долго и затратно. Одним из крупных достижений теории алгоритмов было доказательство того, что есть такие особые задачи – вроде задачи коммивояжера, где вам нужно обегать N пунктов назначения, при этом затратив минимальное время на путь. К которым, как оказалось, можно свести все (!) неполиномиальные задачи. То есть, если бы явился такой волшебник и решил задачу коммивояжера за полиномиальное время / память, то это бы означало для человечества фантастическое ускорение очень многих алгоритмов. С другой стороны, это означало бы и появление некоторых проблем. Например, ваша электронная почта или номер кредитной карты могли бы попасть в руки злоумышленника. Дело в том, что единственное, что предохраняет ваши данные, это невозможность за полиномиальное время "крэкнуть" алгоритм шифрования! Поэтому вопрос о возможности решить за полиномиальное время задачу коммивояжера (то есть доказать что P=NP) оказывается очень животрепещущим – ведь пришлось бы срочно изобретать новый алгоритм шифрования. С другой стороны, доказательство P!=NP означало бы, что криптологам можно спать спокойно: их алгоритм не скоро вскроют.
Дмитрий Крылов: Что можно сказать о доказательстве неравенства, которое представил недавно Vinay Deolalikar?
А.В.: Оно очень длинное, 66 страниц! Если серьезно, то деолаликаровское доказательство кажется очень оригинальным – с использованием знаний из теоретической физики. Это очень показательно. В природе – одни законы, и похожие задачи возникают и в физике, и в информатике. Взять хотя бы близость таких понятий, как энтропия в физике и в информатике. Мой коллега, Андрей Соклаков, даже пытался на теоретическом уровне выявить фундаментальную связь между такими понятиями из информатики, как сложность алгоритма, и законами физики. Ссылка на его статью есть в википедийной статье об известной всем бритве Оккама.
Д.К.: Что значило бы доказательство этого неравенства для прикладной информатики?
А.В.: В принципе для прикладной – business as usual; просто это отбой для тех теоретиков, кто копал и надеялся на халяву, что решит НП-полную задачу за полиномиальное время, что было бы шикарно для всей алгоритмистики, но что, похоже, все-таки является недостижимой утопией. Ну, и как я уже отметил, также отбой для шифровальщиков.
Д.К.: Полиномиальное время, т.е. физическое время для решения задачи, которое зависит от сложности задачи (числа узлов, например) как степенная функция. Т.е., если бы можно было решать НП-полные задачи в полиномиальном времени, то это как-то расширило бы возможности программеров, которые пишут/оптимизируют код?
А.В.: Однозначно. Если бы даже просто было доказано, что существует такой алгоритм, то рано или поздно он был бы найден. Хотя, думаю, что, скорее всего, был бы сразу предложен алгоритм. Неудачные попытки найти каковой на протяжении вот уже 30 лет склоняют многих к мысли, что такого алгоритма не существует.
Продолжение – в следующем выпуске техносреды, а сейчас вернемся к предыдущей теме Пожарное дело.
В комментариях – сожаления по поводу развала существовавшей до 2006-го года системы управления лесными пожарами и неожиданное предложение журналистам «Голоса» провести расследование в российском МЧС. Респираторы в РФ никто не носит, если судить по комментариям. А по-моему, стоило бы.
Дмитрий Крылов, PhD, независимый эксперт по инновационным технологиям
