Исследователь, изучающий вычислительную технику, создавая новые миры | Журнал Кванта

Представьте, что вы стремитесь понять саму природу вычислений. Ты глубоко в пустыне, вдали от любых путей, и непостижимый Сообщения вырезаны на стволах деревьев вокруг вас — БПП, АС⁰[м], Σ₂P, YACC и сотни других. Символы пытаются вам что-то сказать, но с чего начать? Вы даже не можете держать их все прямо.

Лишь немногие исследователи сделали столько же, сколько Рассел Импальяццо чтобы прорваться сквозь этот кажущийся хаос. В течение 40 лет Импальяццо работал в авангарде теории сложности вычислений, изучая внутреннюю сложность различных задач. Самый известный открытый вопрос в этой области, называемый проблемой P и NP, заключается в том, являются ли многие, казалось бы, сложные вычислительные задачи на самом деле простыми — с правильным алгоритмом. Ответ будет иметь далеко идущие последствия для науки и безопасности современной криптографии.

В 1980-х и 1990-х годах Импальяццо сыграл ведущую роль в объединении теоретические основы криптографии. В 1995 году он сформулировал значение этих новых разработок в знаковой статье, в которой переформулировал возможные решения проблемы P и NP, а также нескольких связанных проблем на языке пять гипотетических миров мы могли бы обитать в мире, получившем причудливое название «Алгоритмика», «Эвристика», «Пессиленд», «Миникрипт» и «Криптомания». Пять миров Импальяццо вдохновили целое поколение исследователей и продолжают направлять исследования в процветающей области науки. метасложность.

И это не единственные миры, которые он придумал. Импальяццо на протяжении всей жизни был поклонником настольных ролевых игр, таких как Dungeons and Dragons, и ему доставляет удовольствие изобретать новые своды правил и новые настройки для изучения. Тот же игривый дух оживляет его 30-летнюю практику импровизационной комедии.

Импальяццо также проделал фундаментальную работу, разъяснившую фундаментальную роль случайности в вычислениях. В конце 1970-х годов ученые-компьютерщики обнаружили, что случайность иногда может улучшать алгоритмы для решения детерминистских задач по своей сути — противоречивое открытие, которое годами озадачивало исследователей. Работа Импальяццо с теоретиком сложности Ави Вигдерсон и другие исследователи в 1990-х годах показали, что если некоторые вычислительные задачи действительно фундаментально сложны, то это всегда возможно преобразовать алгоритмы, использующие случайность, в детерминированные. И наоборот, доказывая, что случайность можно исключить из любого алгоритма также доказало бы что действительно серьезные проблемы существуют.

Quanta поговорил с Импальяццо о разнице между сложными задачами и сложными головоломками, консультациях с оракулами и математических уроках комедийной импровизации. Интервью было сокращено и отредактировано для ясности.

Когда вы впервые заинтересовались математикой?

Я интересовался математикой еще до того, как по-настоящему понял, что это такое. В третьем классе мои оценки по математике начали снижаться, потому что нам нужно было учить наизусть таблицу умножения, а я отказался. Моя мать сказала: «Но Рассел, ты любишь математику, почему ты этим не занимаешься?» И я сказал: «Это не математика, это запоминание. Настоящая математика не предполагает запоминания». Все, что я знал на тот момент, это арифметика, поэтому я не уверен, откуда я взял, что математика связана с абстрактными понятиями.

А как насчет информатики? Части этой области очень абстрактны, но это не то, с чем большинство людей сталкивается впервые.

В старшей школе я прошел курс программирования на Бейсике, но добиться чего-либо было очень сложно. Программы приходилось переносить на бумажные ленты, которые нужно было запускать через очень старый компьютер, который часто давал сбои и разрывал бумагу пополам. Поэтому я подумал, что информатика ужасно скучна.

Я намеревался изучать логику. Но многие концепции, когда вы пытались их формализовать, включали вычисления и особенно ограничения на вычисления. Такие вопросы, как «Откуда мы знаем, что некоторые математические утверждения верны?» и «Как мы понимаем сложность занятий математикой?» привело к теоретической информатике и особенно теории сложности.

Некоторые из ваших самых известных работ исследуют связь между криптографией и теорией сложности вычислений. Почему эти два поля связаны?

Когда вы настраиваете криптографическую систему, вам необходимо различать законных пользователей — людей, которым вы хотите предоставить доступ — и всех остальных. Вычислительно сложные задачи дают нам возможность различать эти группы на основе того, что им известно. Но если вы хотите, чтобы знание ответа на проблему позволило различать две группы людей, вы не можете просто использовать любую сложную задачу — вам нужна сложная головоломка.

В чем разница между проблемой и головоломкой?

В общем, человек, задающий проблему, может не знать ответа. Головоломка — это задача, созданная с учетом ответа. Так зачем же нам нужна головоломка? Потому что нам нужно иметь возможность определить, действительно ли человек, который предположительно решил эту задачу, сделал это. В повседневной жизни мы используем головоломки для развлечения, но мы также используем их в классах, чтобы проверить, поняли ли люди материал. Вот что происходит в криптографии: мы используем головоломки, чтобы проверить чьи-то знания.

Разница между пятью мирами заключается в том, как они отвечают на вопросы «Есть ли сложные проблемы?» и «Есть ли сложные головоломки?»

Как проявляются эти разные ответы?

В первом мире, Algorithmica, нет сложных проблем. Вам не обязательно знать, как кто-то придумал вашу проблему: вы всегда можете ее решить. Эвристика говорит: «Ну, может быть, некоторые проблемы сложны». Затем мы попадаем в Пессиленд, где многие задачи сложны, но большинство головоломок - нет. Почти любую проблему, которую я придумываю, и если я знаю решение, вы тоже сможете ее решить. Все эти миры вредны для криптографии.

В Minicrypt я могу создавать головоломки, которые я знаю, как решить, но которые по-прежнему сложны для вас. И, наконец, Криптомания — это мир, в котором два человека могут стоять в общественном месте, где подслушивающий может услышать, и вместе создавать головоломку, которая по-прежнему сложна для подслушивающего.

Что побудило вас написать статью о пяти мирах?

В то время было известно, что разные ответы на вопрос P и NP окажут большое влияние на то, какие проблемы мы можем решить, а также на какую безопасность мы можем надеяться, но качественные различия между различными формами легкости и твердость не совсем ясна.

Всего несколькими годами ранее была опубликована очень содержательная статья, в которой различия были изложены с использованием множества взаимосвязанных вопросов с примерно 20 возможными ответами. Одной из причин, по которой я захотел написать статью о пяти мирах, было то, что за эти несколько лет мы добились огромного прогресса. Было бы трудно найти названия для 20 возможных миров.

Так зачем же представлять это так, как разные миры с причудливыми названиями?

Я согласился написать эту статью для конференции. Я не спал допоздна, пытаясь сообразить, что я собираюсь сказать, и где-то около часа ночи создание изображения разных миров показалось мне хорошей идеей. А потом я прочитал это на следующее утро, и это все еще казалось мне хорошей идеей — это был способ показать, как эти идеи на самом деле повлияют на мир, не углубляясь в количественные детали. Что меня больше всего радует в этой статье, так это то, что я слышу от людей, занимающихся исследованиями сложности, что именно эта статья заинтересовала их в этой области, когда они были студентами.

Исключили ли исследователи какой-либо из пяти возможных миров?

На самом деле мы добавляем больше — люди начали говорить о Обфустопия как мир еще более мощных криптографических инструментов. Немного удручающе, что мы добились такого большого прогресса в конце 1980-х годов и с тех пор не уничтожили ни одного мира. Но зато мы гораздо больше знаем о связях между мирами и имеем гораздо более четкая картина того, как будет выглядеть каждый мир.

Гипотетические миры играют еще одну роль в теории сложности, в доказательствах, предполагающих существование «оракулов». Итак, прежде всего, что такое оракул?

Представьте, что кто-то создает гениальное устройство, которое может решить какую-то проблему, при этом мы не знаем алгоритма решения этой проблемы. Вот что такое оракул. Если бы у нас было такое чудесное устройство и мы поместили его в наши компьютеры, оно могло бы сместить грань между тем, что вычислимо, и тем, что невычислимо.

Считают ли исследователи, что эти волшебные ящики действительно могут существовать?

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

Вы также обнаружили связь между вычислительной сложностью и случайностью. Как работает эта связь?

На самом деле это способ сказать, что если вы чего-то не понимаете, то это может показаться случайным. Предположим, я говорю, что думаю о числе от одного до тысячи. Если я выберу число наугад, у вас будет один шанс из тысячи его угадать. А если я спрошу — вслед за «Монти Пайтоном» — «Какова средняя скорость полета европейской ласточки в милях в час?» у вас примерно такой же шанс. Вероятно, он движется со скоростью более одной мили в час и, вероятно, не превышает тысячи миль в час.

На самом деле это не случайность — это детерминированный вопрос, на который можно ответить. Мы могли бы просто измерить всех летающих ласточек, но это сложно определить, имея ограниченные ресурсы, например, при отсутствии бюджета на измерение скорости ласточек и отсутствии бесконечного запаса ласточек.

Итак, идея заключается в том, что сложные проблемы, решения которых мы не знаем, могут стать источником «псевдослучайных» чисел, которые выглядят случайными.

Говоря о «Монти Пайтон», я знаю, что вы уже давно снимаетесь в комедийных импровизациях. С чего вы начали?

Я начал свою карьеру в качестве доцента в Сан-Диего в 1991 году. И где-то в 94-м или около того я подумал: «У меня действительно не так уж много жизни за пределами кафедры». Итак, я получил бесплатную еженедельную газету и просмотрел список клубов и мероприятий. Я исключил все, кроме комедийной импровизации — я думал, что, по крайней мере, вполне вероятно, что у меня с этим все получится. Я встретил свою жену в этом классе для начинающих.

Что она думала?

Она говорит, что я вела себя ужасно. Когда вы логик, вас приучают всегда думать о нюансах каждого слова. Вы не хотите сказать что-то неправильное. Импровизация хороша тем, что она меняет ситуацию: дело не в том, чтобы сказать что-то идеальное, а в том, чтобы быстро что-то придумать. Это была противоположность остальной части моей жизни.

Моя нынешняя жена взяла перерыв в учебе, и когда она вернулась год спустя, мне удалось произвести на нее впечатление. Это было 30 лет назад. Я до сих пор хожу на те же занятия с тем же преподавателем.

Изменила ли импровизация ваш подход к исследованиям?

Это хорошая практика, чтобы не быть слишком критичным к каждой своей мысли. Это особенно полезно при сотрудничестве. Работая с другими людьми, я обычно говорил что-то вроде: «Но эта идея не сработает по следующей причине. Это не совсем так». В импровизации вы всегда должны принимать то, что говорит ваш партнер. И я думаю, что это хорошая позиция, особенно когда вы проводите исследование со студентами: не отвергайте то, что они говорят, только потому, что вы знаете, что это неправильно. Есть много хороших идей, которые не являются на 100% верными.

Как что?

Когда вы пытаетесь использовать интуицию для решения проблемы, вам может помочь одно — начать с некоторых упрощающих предположений. Эти предположения обычно не соответствуют действительности, но они могут помочь вам составить план действий. Скажите: «Если бы у меня был слон, я мог бы преодолеть горы. Конечно, у меня нет слона. Но если бы я это сделал, вот как бы я это сделал». И тогда ты понимаешь: «Ну, может быть, мне для этого шага слон и не нужен. Мул подойдет.

А как насчет твоей любви к ролевым играм — это вообще повлияло на твою работу?

Возможно, это не повлияло на все мои исследования, но определенно повлияло на мою статью о пяти мирах. У меня всегда был общий интерес к фэнтези и научной фантастике, а также к придумыванию различных возможных миров — как бы все было, если бы все было по-другому?

Почему ролевые игры являются таким привлекательным способом исследования гипотетических миров?

Люди, увлекающиеся спекулятивной фантастикой, всегда изобретали миры. Толкин наиболее известен этим, и у него было такое огромное воображение, что его мир действительно казался живым. Для тех из нас, кто не столь изобретателен, лучший способ добиться этого — пригласить людей в свою среду и сыграть в игру. это способ сделать это. Теперь это не только мой мир. Возможно, все началось так, как я это себе представлял, но, как и в любом сотрудничестве, благодаря вкладу всех остальных, оно развилось далеко за пределы этого.