Труднопроходимость NP-полных задач как принцип физики?

Я всегда заинтригован отсутствием численных доказательств в экспериментальной математике за или против вопроса P против NP. В то время как гипотеза Римана имеет некоторые подтверждающие данные из численной проверки, я не знаю аналогичных доказательств для вопроса P против NP.

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

Принимая допущение твердости NP, почему трудно разработать научный эксперимент, который решает, уважает ли наша вселенная допущение твердости NP или нет?

Кроме того, есть ли какие-либо известные численные доказательства из экспериментальной математики за или против ?$P\ne NP$

РЕДАКТИРОВАТЬ: Вот хорошая презентация Скотт Ааронсон под названием вычислительной сложности как закон физики

Я не думаю, что тот факт, что является асимптотическим утверждением, является автоматическим «нарушителем». Можно сделать конкретные предположения, которые согласуются с нашими знаниями, но сильнее, чем P против NP, такие как «Требуется по крайней мере 2 n / 10 шагов, чтобы найти удовлетворительное назначение для случайной формулы переменной 10SAT с переменной n» (где «случайным» является, например, посаженная модель Ахлиоптас Кожа-Оглан$P\neq NP$$2^{n/10}$ , это всего лишь пример - я не знаю, каковы разумные конкретные цифры ).

Такая гипотеза может привести к опровержимому прогнозу, что любая естественная система, которая попытается решить эту проблему, потерпит неудачу (например, застрянет в локальных минимумах), что можно проверить с помощью экспериментов. На самом деле, я не эксперт в этом, но, насколько мне известно, как отметил Джо Фицсимонс, такие прогнозы были подтверждены адиабатическими вычислениями. (Скотт Ааронсон также провел несколько занимательных экспериментов с мыльными пузырями.)

Конечно, вы также можете увидеть некоторые «эмпирические доказательства» в том факте, что люди пытались решить проблемы оптимизации, криптоанализировать шифрование и т. Д. И до сих пор не добились успеха ...$P \neq NP$

Реальный мир - это объект постоянного размера, поэтому нет способа исключить процедуру реального мира за полиномиальное время для решения NP-завершенных задач, в которых огромная константа скрыта в большой O-записи.

В любом случае, помимо этого пункта, предположение является утверждением вида «нет процедуры реального мира, которая делает ...». Как можно спроектировать эксперимент, чтобы опровергнуть такое утверждение? Если предположение было что-то вроде «Если мы делаем X в реальном мире, Y случается», то это можно опровергнуть, выполнив X. Утверждение, которое мы хотим, утверждает несуществование чего-либо, поэтому я не вижу эксперимента решая это. Это может быть показано как физическое следствие законов физики, но это даже сложнее, чем P против NP, потому что машина Тьюринга действительно следует законам физики. Поскольку нам не удалось даже показать, что ТМ не могут решать задачи, полные NP, за полиномиальное время, кажется совершенно безнадежным показывать, что ни один физический процесс не может решить проблемы, полные NP, за полиномиальное время.

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

1) Программа кажется практически "ортогональной" как экспериментальной, так и теоретической физике. Так что это не дает (пока) полезного понимания физики.

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

(Аналогичный комментарий относится и к «Тезису о церковном чтении».)

2) Хотя физический NP, не равный P, является более широкой гипотезой, чем математический NP, не равный P, мы также можем рассматривать его как более ограниченный, поскольку алгоритмы, встречающиеся в природе (и даже созданные человеком алгоритмы), кажутся очень ограниченный класс всех теоретически возможных алгоритмов. Будет очень интересно понять такие ограничения формально, но в любом случае любое экспериментальное «доказательство», предложенное в вопросе, будет применяться только к этому ограниченному классу.

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

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

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

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

С. Попеску и Д. Рорлих, Квантовая нелокальность как аксиома, Найдено. Phys. 24, 379–385 (1994).

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

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

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

Г. Брассард, Х. Бурман, Н. Линден, А. А. Метот, А. Тапп и Ф. Унгер. Ограничение нелокальности в любом мире, в котором сложность общения не является тривиальной, Phys. Преподобный Летт. 96, 250401 (2006).

Обратите внимание, что более слабый результат был уже доказан в Ph.D. тезис Вим ван Дам. Что Brassard et al. Доказательством является то, что наличие доступа к блокам связи с общественностью, даже если они неисправны и иногда дают правильную корреляцию, позволяет полностью упростить коммуникационную сложность. В этом мире каждая булева функция с двумя переменными может быть совместно вычислена путем передачи только одного бита. Это кажется довольно абсурдным, поэтому давайте посмотрим на это наоборот. Мы можем принять нетривиальность сложности общения как аксиому, и это позволяет нам вывести тот факт, что в наших экспериментах мы не наблюдаем некоторые более сильные, чем квантовые корреляции.

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

H. Buhrman, R. Cleve, S. Massar и R. de Wolf, Нелокальность и сложность коммуникации, Rev. Mod. Phys. 82, 665–698 (2010).

или прямой поиск литературы из двух других работ, которые я цитировал.

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

(1) Возьмем, к примеру, эксперименты, измеряющие нечто, известное как неравенство CHSH (тип неравенства Белла ), где физическая система состоит из двух запутанных фотонов, а измерения представляют собой измерения поляризации отдельных фотонов в двух пространственно удаленных местах.

(2) Этот единственный бит необходим всякий раз, когда f (x, y) фактически зависит как от x, так и от y, поскольку отправка нулевых битов не будет нарушать сигнализацию.

Кроме того, есть ли какие-либо известные численные доказательства из экспериментальной математики за или против P ≠ N P$P \neq NP$

$NP \subseteq P/poly$ аналогичного вида, найденного для гипотезы Римана или гипотезы Гольдбаха, используя явные вычисления, чтобы показать, что, скажем, SAT до длины 10 не имеет схемы размером 20 (где вы позволяете значениям 10 и 20 изменяться). Это все еще сталкивается с той же проблемой, поднятой в других ответах - конечное доказательство не может дать нам асимптотический ответ. Но по существу та же самая проблема верна для текущих «доказательств» гипотезы Римана.

Теперь найти минимальную цепь для SAT до длины 10 в настоящее время очень сложно. Однако некоторые идеи в теории геометрической сложности позволяют получить аналогичные результаты с более эффективным (я думаю, только экспоненциальным, а не двукратно-экспоненциальным) вычислительным поиском. Одна из гипотез Малмули заключается в том, что на самом деле этот поиск может быть выполнен за полиномиальное время, но мы далеки от доказательства чего-либо близкого к этому.

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

Или другими словами: что сказал Робин.

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

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

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

Я написал резюме по статье Ааронсона по этому вопросу, однако это не на английском языке. Смотрите оригинал статьи .

Лично я слышал о другом примере реальной проблемы, смоделированной в вычислениях. В статье рассказывается о моделях систем управления, основанных на стаях птиц. Оказывается, что для птиц в реальной жизни требуется короткое время, они трудно поддаются решению («башня 2 с»), если их анализировать как вычислительную задачу. Смотрите статью Бернара Шазеля для деталей.

[Редактировать: Разъяснил часть о бумаге Chazelle. Спасибо за предоставление точной информации.]

Я до сих пор голосую за проблему n-тела в качестве примера неразрешимости NP. Господа, которые ссылаются на числовые решения, забывают, что числовое решение - это рекурсивная модель, а не принципиальное решение, как аналитическое решение. Аналитическое решение Куи Донга Вана неразрешимо. Белки, которые могут складываться, и планеты, которые могут вращаться в системах более чем двух тел, являются физическими системами, а не алгоритмическими решениями того типа, который решает проблема P-NP.

Я также должен оценить трудности Чазизопа с решениями в непрерывном времени. Если время или пространство непрерывны, потенциальные пространства состояний становятся неисчислимыми (aleph one).

$n$