Аві Вігдерсон, піонер теорії складності, отримав премію Тюрінга | Журнал Quanta

Понад 40 років Аві Вігдерсон досліджував проблеми. Але як теоретика обчислювальної складності, він не обов’язково дбає про відповіді на ці проблеми. Часто він просто хоче знати, чи можна їх вирішити чи ні, і як це сказати. «Ситуація смішна», — сказав Віґдерсон, фахівець з інформатики в Інституті перспективних досліджень у Прінстоні, Нью-Джерсі. Незалежно від того, яким складним здається питання, ефективний спосіб відповісти на нього можна сховати поза межами досяжності. «Наскільки нам відомо, для кожної проблеми, з якою ми стикаємося і намагаємося вирішити, ми не можемо виключити, що у неї є алгоритм, який може її вирішити. Це єдина найцікавіша проблема для мене».

Сьогодні Вігдерсон був названий переможцем А.М. Премія Тюрінга, який вважається однією з найвищих нагород у галузі інформатики, за його фундаментальний внесок у теорію обчислень. Робота Віґдерсона торкнулася майже всіх сфер діяльності. Його колеги, співробітники та підопічні кажуть, що він постійно знаходить несподівані мости між різними сферами. А його робота над випадковістю та обчисленнями, починаючи з 1990-х років, виявила глибокі зв’язки між математикою та інформатикою, які лежать в основі сучасних досліджень.

Мадху Судан, вчений з інформатики з Гарвардського університету, який отримав премію Рольфа Неванлінни 2002 року (тепер вона називається премією «Абакус»), сказав, що вплив Віґдерсона на цю сферу неможливо не помітити. «Дуже важко працювати в будь-якій галузі інформатики, фактично не перетинаючись із роботою Аві», — сказав Судан. «І скрізь ви знаходите дуже глибоке розуміння». Наприкінці 1980-х, наприклад, Судан працював з Віґдерсоном над документом, який досліджував зв’язки між певними математичними функціями та поліномами. Ця робота поклала початок усій кар’єрі Судана. «Це типово для Аві», — сказав Судан. «Він потрапляє в певний простір, ставить правильні запитання, а потім йде далі».

Віґдерсон виріс у Хайфі, Ізраїль, як один із трьох синів медсестри та інженера-електрика, обидва пережили Голокост. Його батько любив головоломки і дуже цікавився фундаментальними ідеями в математиці, якими він ділився зі своїми дітьми. «Це той хлопець, від якого я заразився цим вірусом», — сказав Вігдерсон. Коли він у 1970-х роках вступив до Техніону в Хайфі, він хотів вивчати математику, але батьки спрямували його на інформатику. «Вони подумали, що, можливо, було б гарною ідеєю, що я знайду роботу, коли закінчу», — сказав він.

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

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

«Це ключовий результат у криптографії; це надзвичайно центральне місце», – сказав Раз. Використовуючи підтвердження з нульовим знанням, хтось може довести, що він правильно зашифрував або підписав повідомлення за допомогою свого секретного ключа, не розкриваючи жодної інформації про нього. «Avi має кілька надзвичайно важливих результатів у криптографії, і це може бути найважливішим із них».

Але, мабуть, найбільш основоположний результат Віґдерсона лежить в іншій області: зв’язок обчислювальної складності з випадковість. До кінця 1970-х років комп’ютерні вчені зрозуміли, що для багатьох складних проблем алгоритми, які використовують випадковість, також звані імовірнісними алгоритмами, можуть значно перевершити свої детерміновані альтернативи. В 1977 доказ, наприклад, Роберт Соловей і Фолькер Штрассен представили рандомізований алгоритм, який міг визначити, чи є число простим швидше, ніж найкращі детерміновані алгоритми того часу.

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

Нерозумна ефективність випадковості наштовхнула його на думку про природу самої випадковості. Він, як і інші дослідники того часу, сумнівався, наскільки це необхідно для ефективного вирішення проблем і за яких умов воно може бути усунено взагалі. «Спочатку було незрозуміло, чи це лише наша власна дурість, що ми не можемо усунути випадковість», — сказав він. «Але більшим питанням було те, чи завжди можна ефективно усунути випадковість чи ні». Він зрозумів, що потреба у випадковості була тісно пов’язана з обчислювальною складністю проблеми.

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

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

Судан сказав, що папір допоміг комп’ютерникам розпізнати ступені випадковості, які могли б допомогти розкрити складні проблеми та способи їх вирішення. «Це не просто випадковість, а сприйняття випадковості», – сказав він. «Це ключ».

Судан зазначає, що випадковість, здається, з’являється всюди, але насправді її надзвичайно важко знайти. «Люди кажуть вам, що цифри числа «пі» виглядають випадковими або послідовність простих чисел виглядає випадковою», — сказав він. «Вони повністю визначені, але здаються нам випадковими». Сприйняття випадковості, за його словами, лежить в основі сучасної інформатики. «І це те, що Avi дуже пропагував».

Випадковість стала потужним ресурсом у теорії складності, але вона невловима. Підкидання монет і кубиків, зазначає Вігдерсон, не зовсім випадкові: якщо у вас достатньо інформації про фізичну систему, то результат цілком передбачуваний. Ідеальна випадковість, за його словами, невловима, і її важко перевірити.

Але для Вігерсона приклади обчислень є скрізь — не лише в смартфонах і ноутбуках і алгоритмах шифрування, але також у біологічних і фізичних системах. В останні десятиліття результати теорії обчислень дозволили зрозуміти низку несподіваних проблем, від роїння птахів і результатів виборів до біохімічних реакцій в організмі. «По суті, будь-який природний процес — це еволюція, яку можна розглядати як обчислення, тож ви можете вивчати його як таке. Майже все обчислюється».