Ави Вигдерсон занимается изучением проблем более 40 лет. Но как теоретик вычислительной сложности его не обязательно интересуют ответы на эти проблемы. Часто он просто хочет знать, разрешимы они или нет, и как это узнать. «Ситуация смешная», — заявил Вигдерсон, ученый-компьютерщик из Института перспективных исследований в Принстоне, штат Нью-Джерси. Каким бы сложным ни казался вопрос, эффективный способ ответить на него может скрываться вне досягаемости. «Насколько нам известно, для каждой проблемы, с которой мы сталкиваемся и пытаемся решить, мы не можем исключать наличие алгоритма, способного ее решить. Это самая интересная для меня проблема».

Сегодня Вигдерсон был назван победителем конкурса Премия AM Тьюринга, широко считающийся одной из высших наград в области компьютерных наук, за фундаментальный вклад в теорию вычислений. Работа Вигдерсона затронула почти все области науки. Его коллеги, сотрудники и подопечные говорят, что он постоянно находит неожиданные мосты между разрозненными областями. А его работа по случайности и вычислениям, начавшаяся в 1990-х годах, выявила глубокие связи между математикой и информатикой, которые лежат в основе сегодняшних исследований.

Мадху Судан, ученый-компьютерщик из Гарвардского университета, получивший в 2002 году премию Рольфа Неванлинны (теперь называемую премией Абакус), сказал, что влияние Вигдерсона на эту область невозможно не заметить. «Очень сложно работать в любой области компьютерных наук, не пересекаясь с работой Ави», — сказал Судан. «И везде можно найти очень глубокие прозрения». Например, в конце 1980-х годов Судан работал с Вигдерсоном над статьей, исследующей связи между некоторыми математическими функциями и полиномами. Эта работа положила начало всей карьере Судана. «Это типично для Ави», — сказал Судан. «Он попадает в какое-то пространство, задает правильные вопросы, а затем идет дальше».

Вигдерсон вырос в Хайфе, Израиль, как один из трех сыновей медсестры и инженера-электрика, переживших Холокост. Его отец любил головоломки и сильно интересовался фундаментальными идеями математики, которыми делился со своими детьми. «Это тот парень, от которого я заразился этим вирусом», — сказал Вигдерсон. Когда в 1970-х годах он поступил в колледж в Технионе в Хайфе, он хотел изучать математику, но вместо этого родители направили его на информатику. «Они подумали, что, возможно, было бы неплохо, если бы я нашел работу, когда закончу», — сказал он.

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

«Человек, который видит доказательство, ничего не узнает о самом доказательстве», — сказал Ран Раз, ученый-компьютерщик из Принстонского университета. В 1985 году Шафи Голдвассер, Сильвио Микали и Чарльз Ракофф представили эту концепцию. интерактивные доказательства с нулевым разглашением, демонстрируя его использование для нескольких утверждений. Вигдерсон вместе с Микали и Одедом Голдрейхом позже разъяснил эту идею, изложив условия, показывающие, что, если утверждение может быть доказано, оно также имеет доказательство с нулевым разглашением.

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

Но, возможно, самый основополагающий результат Вигдерсона лежит в другой области: связь вычислительной сложности с хаотичность. К концу 1970-х годов ученые-компьютерщики поняли, что для многих сложных задач алгоритмы, использующие случайность, также называемые вероятностными алгоритмами, могут значительно превзойти свои детерминированные альтернативы. В 1977 доказательствоНапример, Роберт Соловей и Фолькер Штрассен представили рандомизированный алгоритм, который мог определить, является ли число простым, быстрее, чем лучшие детерминированные алгоритмы того времени.

Для некоторых задач вероятностные алгоритмы могут указывать на детерминированные. В начале 1980-х годов Вигдерсон работал с Ричардом Карпом из Калифорнийского университета в Беркли, чтобы связать идею случайности с проблемами, которые считались сложными в вычислительном отношении, а это означает, что ни один известный детерминированный алгоритм не может решить их за разумное время. «Мы не знаем, как доказать, что они крутые», — сказал Вигдерсон. Однако он и Карп нашли рандомизированный алгоритм для решения определенной сложной задачи, которую позже смогли дерандомизировать, эффективно обнаружив для нее детерминированный алгоритм. Примерно в то же время другие исследователи показали, как предположения о вычислительной сложности в задачах криптографии могут способствовать дерандомизации в целом.

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

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

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

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

Судан отмечает, что случайность, кажется, проявляется повсюду, но на самом деле ее чрезвычайно трудно обнаружить. «Люди говорят вам, что цифры числа «пи» выглядят случайными, или последовательность простых чисел выглядит случайной», — сказал он. «Они полностью детерминированы, но нам кажутся случайными». По его словам, восприятие случайности сегодня лежит в основе компьютерной науки. «И это то, что Ави активно продвигал».

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

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