Физика результатов в ТКС?

42

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

  1. Квантовые вычисления
  2. Результаты статистической механики, используемые в анализе сложности / эвристических алгоритмах.

Итак, мой вопрос: есть ли какие-то основные области, по которым я скучаю?

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

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

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

Ответы:

26

Методика поиска имитации отжига вдохновлена ​​физическим процессом отжига в металлургии.

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

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

Дэйв Кларк
источник
supercooldave: мое ограниченное понимание состояло в том, что моделируемый отжиг избегает только локальных минимумов, которые являются «достаточно мелкими». Это верно?
Джошуа Грохов
1
@ Джошуа: в общем, имитируемый отжиг не всегда удается избежать локального минимума. Это всегда может застрять в неправильном месте. Некоторые эксперименты необходимы, чтобы найти хорошую отправную точку и так далее.
Дэйв Кларк
1
Конечно, стоит отметить, что «настоящий» отжиг не всегда позволяет избежать локальных минимумов! Дефекты (в математически-физическом смысле) не являются неслыханными.
Стивен Стадницкий
Если снижение температуры происходит экспоненциально медленно, то моделируемый отжиг приобретает много желательных глобальных оптимизационных свойств. Конечно, он также получает экспоненциальное время выполнения.
Эллиот Джей Джей
23

С другой стороны (от TCS к физике), состояния матричных продуктов, PEPS (спроецированные запутанные парные состояния), MERA (ансат многоуровневой реномализации переплетения) были в значительной степени основаны на идеях TCS, которые были адаптированы в квантовой теории информации. Все эти аббревиатуры представляют собой методы аппроксимации состояний квантовых спиновых систем, которые используются теоретиками конденсированного состояния, и во многих случаях эти методы, похоже, работают лучше, чем любые ранее известные инструменты.

Питер Шор
источник
2
Одна вещь, которая поразила меня в этой области, заключается в том, что, похоже, что больше похоже на сообщество теоретической физики в квантовой информации, чем на сообщество TCS (если мы действительно можем провести такое различие), которое, кажется, заинтересовано этими методами.
Джо Фицсимонс
5
Я бы определенно согласился. Я пытался заинтересовать их в аспирантуре на ранней стадии, но его реакция была "блеф ... это всего лишь эвристические методы приближения, и вы не можете сказать о них что-либо строгое". Конечно, это оказалось неправильно.
Питер Шор
1
(@Shor) Мне очень понравился этот ответ, и я предоставил сопутствующий ответ с еще несколькими ссылками - по крайней мере, одна из которых (обзор Геометрии Джозефа Лэндсбурга в 2008 году и сложность умножения матриц ) наиболее определенно находится в конце TCS. спектр. cstheory.stackexchange.com/questions/2074/…
Джон Сидлес
20

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

Суреш Венкат
источник
Я очень заинтересован в анализе сетей и социальных сетей. У вас есть какие-либо ссылки?
Дэйв Кларк
2
хмм. Лучше всего начать с книги Кляйнберга / Исли (это хороший текст на уровне старшекурсника). Тогда вы могли бы работать вперед и назад от работы Аарона Клосета и Марка Ньюмана
Суреш Венкат
19

Результат Pour-El и Richards Adv. Математика 39 215 (1981) дает существование невычислимых решений трехмерного волнового уравнения для вычислимых начальных условий, используя волну для моделирования универсальной машины Тьюринга.

S Охотник
источник
Я также упомянул бы вычисления ДНК как область перекрытия, хотя и с более слабыми связями с теоретической физикой как таковой.
S Huntsman
Я больше имел в виду области, в которых TCS извлекал выгоду из результатов по физике, а не наоборот.
Джо Фицсимонс
7
Что ж, тогда (хотя это может считаться неявным или связанным с некоторыми другими вещами, упомянутыми на этой странице), я был бы упущен, если бы не упомянул теорию обратимых вычислений, в особенности круг идей, порожденных работой Ландауэра, который повлиял на многие другие области помимо квантовых вычислений.
S Huntsman
Чтобы прокомментировать ответ Суреша (недостаточно представителя, чтобы комментировать там): было много плодотворных применений идей в физике для анализа динамики в сетях. В качестве одного примера я приведу документ, в котором обсуждаются доказательства того, что трафик TCP проявляет самоорганизованную критичность. В качестве другого примера, несколько исследователей (включая меня) работали над применением идей физики (а не только энтропии) для характеристики сетевого трафика для обнаружения аномалий. Конечно, это оставляет T вне TCS.
S Huntsman
17

Связь идет и наоборот. Некоторое время назад ученые-теоретики, работающие в области теории, заинтересовались относительностью. Они доказали результаты о том, как восстановить структуру пространства-времени из структуры причинности. Это что-то довольно знакомое теоретикам предметной области, где представляющие интерес beasic-объекты представляют собой частичные порядки, топология которых определяется порядком. Вы можете взглянуть на http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf

Андрей Бауэр
источник
3
Да, на самом деле я слышал, как Пракаш говорил об этом на своей мастерской в ​​Барбадосе. Действительно интересная работа. Однако у меня сложилось впечатление, что он также имеет физическое образование. Помимо этого, безусловно, есть вклад в обоих направлениях. Просто так получилось, что мне было особенно интересно узнать об одном конкретном направлении. Предположительно, вопрос о влиянии TCS на физику лучше подходит для веб-сайта по физике, поскольку люди, работающие в области, которая адаптирует идеи из второй области, могут лучше определить, какие из них оказали значительное влияние на первую.
Джо Фицсимонс
13

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

RJK
источник
11

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

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

Нил Кришнасвами
источник
2
А как насчет аналитической комбинаторики (Флажолет и Седжвик)?
RJK
11

Калибровочная теория для эвристических приближений к целочисленному программированию (несколько работ Миши Черткова ). Методы ренормгруппы для комбинаторного счета, гл. 10-12 Рудника / Гаспари «Элементы случайного блуждания». Применение интегрального разложения по Фейману (т. Е. Раздел 9.5.1) для подсчета самоходных прогулок. Что касается подключения к TCS, обратите внимание, что режим управляемости для приближенного подсчета на графиках зависит от скорости роста избегающих прогулок.

Ярослав Булатов
источник
9

Статистическая физика дала ученым-программистам новый взгляд на SAT, как показано здесь . Идея состоит в том, что по мере того, как отношение предложений к переменным, включенным в формулу 3-SAT, увеличивается примерно с 4 до 5, мы переходим от способности решать подавляющее большинство примеров 3-SAT к возможности решать очень мало. Этот переход рассматривается как «фазовый переход» в САТ.

Эта идея приобрела особую известность прошлым летом из предполагаемой статьи Деолаликара «P против NP».

Гек Беннетт
источник
Да, я только что понял, что Джо ссылался на это в своем первоначальном вопросе. Надеюсь, это немного проработано.
Гек Беннетт
9

Ранняя теория распределенных систем, особенно статьи Лесли Лэмпорта и др., Оказала определенное влияние от Специальной теории относительности, чтобы получить правильную картину относительно (отказоустойчивого) соглашения о состоянии глобальной системы. См. Запись 27. ( Время, часы и порядок событий в распределенной системе , сообщения ACM 21, 7 (июль 1978 г.), 558-565) в сочинениях Лесли Лампорта , где Лампорт дает следующую справочную информацию о своем бумага:

Источником этой статьи была заметка Пола Джонсона и Боба Томаса «Ведение дублирующих баз данных». Я полагаю, что их заметка ввела идею использования меток времени сообщений в распределенном алгоритме. У меня есть твердое, интуитивное понимание специальной теории относительности (см. [5]). Это позволило мне сразу понять суть того, что они пытались сделать. Специальная теория относительности учит нас тому, что нет инвариантного полного упорядочения событий в пространстве-времени; разные наблюдатели могут не согласиться с тем, какое из двух событий произошло первым. Существует только частичный порядок, в котором событие e1 предшествует событию e2, если e1 может причинно влиять на e2. Я понял, что сущность Джонсона и Томаса Алгоритм s заключался в использовании временных меток для обеспечения полного упорядочения событий, которое соответствовало причинному порядку. Эта реализация, возможно, была блестящей. Осознав это, все остальное было тривиально. Поскольку Томас и Джонсон не совсем понимали, что они делают, они не совсем поняли алгоритм; их алгоритм допускает аномальное поведение, которое существенно нарушает причинность. Я быстро написал короткую заметку, указывающую на это и исправляющую алгоритм.

Мартин Шварц
источник
9

Я уточнил этот ответ расширенным ответом на MathOverflow на вики-вопрос сообщества Гила Калаи «[Что такое] книга, которую вы хотели бы написать » ».

Расширенный ответ стремится связать фундаментальные проблемы в TCS и QIT с практическими вопросами в области лечения и регенеративной медицины.


Этот ответ расширяет ответ Питера Шора , в котором рассматриваются роли состояний матричных произведений в TCS и физике. Два недавних опроса в Бюллетене AMS имеют отношение к матричным состояниям продуктов, и оба опроса написаны хорошо, не имеют ограничений по оплате и достаточно доступны для неспециалистов:

Математическая арена для исследования Ландсберга - это секущиеся разновидности сортов Сегре , в то время как арена для исследования Пелайо и Нгока - это четырехмерные симплектические многообразия ... требуется некоторое время, чтобы понять, что обе эти арены являются состояниями матричных произведений, если рассматривать их соответственно с вычислительной точки зрения (Ландсбург) и геометрическая перспектива (Палайо и Нгок). Кроме того, Палайо и Нгок включают в свой обзор обсуждение Бабелона, Кантини и Дюшо полуклассического исследования модели Джейнса-Каммингса (отмечая, что модель Джейнса-Каммингса часто встречается в литературе по физике конденсированных сред и квантовым вычислениям ).

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

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

Квантовые симуляторы в настоящее время наслаждаются загадочным обстоятельством, что большие численные квантовые симуляции очень часто работают намного лучше, чем мы можем ожидать. Когда математики и физики придут к общему пониманию, эта озадаченность, несомненно, уменьшится, и удовольствие, несомненно, останется. Хорошо! :)

Джон Сидлес
источник
8

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

Дэйв Кларк
источник
Я бы не подумал об этом, особенно о TCS, но это такая крутая техника, что вы получаете +1 от меня. В конце концов, некоторые области информатики очень сильно зависят от физики (например, SIGGRAPH).
Джо Фицсимонс
Графики, безусловно, TCS. И их нужно рисовать. А Дэвид Эппштейн делает графику. (Это мой убедительный аргумент.)
Дейв Кларк
Хорошо, я приму этот аргумент.
Джо Фицсимонс
Эта техника является основным игроком в графике. Обязательно стоит упомянуть
Суреш Венкат
Отличный пример! +1 от меня
Джордж
2

Большая часть математики, которую мы используем, была изначально придумана для решения физических задач. Примеры включают исчисление (гравитация Ньютона) и ряд Фурье (уравнение теплопроводности).

Уоррен Шуди
источник
6
Аналогичным образом Белкин, Нараянан и Нийоги (FOCS '06, dx.doi.org/10.1109/FOCS.2006.34 ) использовали математический анализ из исследования теплового потока и диффузии, чтобы дать быстрый рандомизированный алгоритм для вычисления площади поверхности выпуклое тело в n измерениях.
Арнаб
2
хороший пример. хотя это пример физики или математики? :)
Суреш Венкат
1

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

Nate
источник
-1

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

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

Теория квантовой механики все чаще рассматривает пространство и время, вселенную, как своего рода вычислительную систему. Похоже, у него есть «минимальные вычислительные единицы», свойственные его природе, вероятно, связанные с длиной Планка. поэтому проверка минимальных машин Тьюринга на наличие проблем также подразумевает и относится к минимальным физическим / энергетическим системам или даже требуемым объемам пространства. [3]

Кроме того, ключевая концепция энтропии неоднократно проявляется в TCS и физике / термодинамике и может быть объединяющим принципом с еще более активными исследованиями, раскрывающими ее основную природу. [1,2]

[1] энтропия в теории информации , википедия

[2] Что такое CS энтропия , стековый поток

[3] Что такое объем информации? tcs.se

ВЗН
источник
1
Вы понимаете, что я ответил на вопрос tcs.se, верно?
Джо Фицсимонс
Я хотел бы понять, почему этот вопрос был отклонен. Понижающее голосование без объяснения причин никому не помогает, так как причины могут быть не техническими. Я понимаю, что ОП знал о некоторых или всех ответах, но так как он не упомянул об этом в вопросе ... cc @JoeFitzsimons
babou