Прекрасные результаты в TCS

Недавно мой друг (работающий в TCS) упомянул в разговоре, что «он хотел увидеть / узнать все (или как можно больше) о прекрасных результатах в TCS за всю свою жизнь». Это заставило меня задуматься о прекрасных результатах в этой области и, следовательно, мотивации для следующего вопроса:

Какие результаты (или идеи), на ваш взгляд, прекрасны в теоретической информатике? Было бы здорово, если бы вы также упомянули причину. [Также было бы хорошо, даже если идеи берут свое начало в математике, но вызвали интерес и нашли применение в TCS]

Я бы начал с ответа в качестве диагонального аргумента Кантора, потому что это простой, элегантный и вместе с тем мощный результат.

Неразрешимость проблемы остановки.

Красив по многим причинам. Это результат невозможности. Доказательство использует диагонализацию. Это утверждение относится к широкому кругу моделей вычислений. Его можно сформулировать различными способами, в частности, используя стандартные языки программирования. Это был переломный момент в истории вычислительной техники. Расширение этого утверждения приводит к теореме Райса, степеням Тьюринга и многим другим интересным результатам. И т. Д. И т. Д.

На мой взгляд, переписка Карри-Ховарда - один из самых красивых теоретических результатов, который побудил меня заняться исследованиями.

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

Возможность криптографии с открытым ключом, например, схема обмена ключами Диффи-Хеллмана.

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

Я был и до сих пор удивлен алгоритмом Евклида. Для меня это свидетельство силы человеческого мышления - что люди могли придумать такой алгоритм так рано (около 300 г. до н.э., если я доверяю своей памяти).

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

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

Вероятностный метод доказательства существования объектов, которые нам трудно построить, включая локальную лемму Ловаша. Эти методы такие простые, но очень мощные.

Построения теории кодирования Мадху Судана с использованием полиномов.

Расширители (это началось как графы Рамануджана) и экстракторы и их приложения в псевдослучайности.

Алгоритм быстрого преобразования Фурье Кули и Тьюки для нахождения ДПФ. (Хотя, как предположил Тьюки, это было повторное открытие хорошо известного метода, по крайней мере, известного Гауссу!)

Теорема Баррингтона (очень неожиданный результат в свое время)

Теорема о параллельном повторении (хотя результат хороший, доказательство нелегкое)

Тета-функция Ловаша для оценки шенноновской емкости графа.

Эллипсоидный алгоритм, который показал, что LP находится в P, удивляя многих в то время, когда многие все еще подозревали, что это может быть NP-Complete.

Удивительно, но один из самых очевидных ответов еще не добавлен. иногда кто-то слишком много работает с чем-то, чтобы увидеть это беспристрастно. теория NP полноты запущенного Cook / Левина и сразу же усиливается Карп , который дал раннее указание на его повсеместность, еще более пророческим задним числом. во многом это рождение современной теории TCS и теории сложности, и ее основной / ключевой / печально известный вопрос P =? NP все еще остается открытым после четырех десятилетий интенсивного изучения / атаки. P =? NP имеет награду Claymath в размере $ 1 млн. За свое решение.

доказательство Кука представило NDTM, который, по-видимому, вовсе не просто теоретическое любопытство, а почти чрезвычайно фундаментальная часть TCS. запустил, так сказать, тысячу кораблей. кроме того, он постоянно сопротивляется / не поддается усилиям с помощью одной из других ключевых / мощных методик TCS, упомянутых в этом списке, - диагонализации, которую можно увидеть, например, в результатах Oracle / Relativization BGS-75 - предполагая, что в любом возможном должно быть что-то экзотическое и отличающееся решение, также предложенное / расширенное в статье Разборова-Рудича о естественных доказательствах (премия Годеля 2007).

есть много, много ссылок на subj, но еще один недавний с некоторым рассказом из первых рук об истории может быть найден в Вопросе P =? NP и Потерянном письме Годеля RJ Lipton

Сложность Колмогорова и метод несжимаемости .

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

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

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

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

Теоремы Шеннона об исходном и канальном кодировании.

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

Прекрасный результат, основанный на теореме PCP, гласит, что вычислительно трудно (NP-трудно) удовлетворить более 7/8 пунктов формулы 3SAT даже для выполнимых.

Алгоритм Шорса для факторинга в BQP . на мой взгляд / память, квантовые вычисления были чем-то большим, чем просто теоретическое любопытство, до тех пор, пока этот результат не появился в 1994 г. это все еще возможно один из самых важных известных алгоритмов QM. награжден премией Геделя 1999 года. это также показывает, что факторинг в вычислениях QM на самом деле в некотором смысле лучше понимается, чем в классических вычислениях, где, например, вопрос о том, является ли факторинг NP завершенным, все еще остается открытым.

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

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

Присуждена премия Геделя 2006 года и премия Фулкерсона 2006 года

Я думаю, что теорема о графе минор Робертсона и Сеймура была самой замечательной теорией, которую я когда-либо видел (и частично читал). Прежде всего, это довольно сложно, но базовые предположения несложны, и, возможно, каждый, кто работает в TCS, может их угадать. Их чрезвычайное усилие доказать их было замечательно. На самом деле, после прочтения некоторых статей из этой серии я понимаю силу человеческого разума.

Также теорема о второстепенных графах имеет большое влияние на различные области TCS. Как теория графов, алгоритм приближения, параметризованные алгоритмы, логика, ...

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

1. Теория вещественных замкнутых полей первого порядка разрешима (автор Тарский). Евклидова геометрия также является моделью аксиом вещественно-замкнутых полей, поэтому, согласно Тарскому, утверждения первого порядка в этой модели разрешимы.
2. Пресбургерская арифметика разрешима.
3. Теория первого порядка алгебраически замкнутых полей (включая комплексные числа) разрешима.
4. Монадическая логика второго порядка над бесконечными (и конечными) словами разрешима. Доказательство элегантно и может быть преподано студентам.

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

Уловка фон Неймана для реализации честной монеты с предвзятой. Мы так привыкли к вероятностным алгоритмам сейчас, но с внешней точки зрения это невероятно круто. И алгоритм, и доказательство доступны каждому, кто знает вероятность старшей школы.

Результат Тима Гриффина о том, что управляющие операторы, такие как call/cc, связаны с классической логикой, расширяя соответствие Карри-Ховарда.

call/cc$E$$\neg\neg \tau$$\mathtt{call/cc}{(E)}$$\tau$$\neg\tau$$\tau\rightarrow\bot$$\tau$

Его статья «Формулы как понятие контроля» появляется в POPL 1990.

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

Тем не менее, CS все еще далек от достижения уровня элегантности, с которым мы сталкиваемся в математике (ну, у них было 5000 лет), от базовых определений / результатов в исчислении, топологии (теоремы о неподвижной точке), комбинаторике, геометрии (теорема Пифагора http : //en.wikipedia.org/wiki/File: Pythag_anim.gif ) и т. д.

Если вы ищете красоту, ищите ее везде ...

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

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

Обзор этого подающего надежды поля Стивом Аводи можно найти здесь .

Нулевое доказательство - очень интересная концепция. Это позволяет объекту, проверяющему, доказать (с высокой вероятностью) другому объекту, верификатору, что он знает «секрет» (решение некоторой NP-задачи, модульный квадратный корень из некоторого числа, дискретный запись некоторого числа и т. д.) без предоставления какой-либо информации о секрете (что сложно на первый взгляд, поскольку первая идея доказать, что вы знаете секрет, состоит в том, чтобы фактически рассказать секрет, и что любое общение, которое может привести к верификатор, считающий, что вы знаете секрет, может априори только увеличить знание верификатора о секрете).