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

15

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

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

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

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

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

Мухаммед Аль-Туркистани
источник
Вот связанное наблюдение, согласно квантовой теории, каждая физическая величина дискретна, включая время, длину, массу и энергию (чрезвычайно мала). Итак, правильно ли рассматривать эволюцию квантовой системы как проблему дискретной оптимизации, управляемую принципом наименьшего действия по всем возможным траекториям пространства состояний?
Мухаммед Аль-Туркистани
8
Тот факт, что белки хорошо складываются in vivo, не следует воспринимать как доказательство того, что вселенная решает NP-полные проблемы. Белки эволюционировали, чтобы эффективно складываться. Есть даже некоторые белки, которые хорошо складываются в клеточной среде, которые не складываются должным образом in vitro . Это связано с тем, что в клетке есть другие белки, называемые шаперонинами, которые помогают в процессе складывания (эти шаперонины предположительно совместно эволюционируют с белками, которые помогают складываться).
Питер Шор

Ответы:

17

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

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

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

Боаз Барак
источник
2
@Jeff - я думаю, что это доказательство того, что P не равен NP, так же как тот факт, что все числа, которые мы до сих пор пытались выполнить, следовали гипотезе Гольдбаха, свидетельствует в пользу гипотезы Гольдбаха, а не только в пользу того, что мы выбрали неправильные номера.
Винаяк Патхак
3
Боаз: Я мог бы принять это как доказательство для более слабой гипотезы «Этому алгоритму нужно как минимум шагов», но не для более сильной гипотезы «ЛЮБОМУ алгоритму нужно как минимум 2 n / 10 шагов». Существует слишком много (на самом деле, бесконечно много) неопробованных алгоритмов или даже классов алгоритмов, чтобы я мог признать, что любой экспериментатор пробовал репрезентативную выборку. 2N/102N/10
Джефф
6
Если бы вы могли как-то показать, что универсальному алгоритму поиска Левина нужно шагов, то вы показали бы, что любой алгоритм нуждается в таком эффективном количестве ... конечно, учитывая наши текущие знания, это было бы безумно непрактично для реализации и тестирования. 2N/10
Райан Уильямс
3
Райан - на практике вы сможете перечислять только программы с очень маленьким размером описания. (См. Также статью Луки Тревизана - eccc.hpi-web.de/report/2010/034/download )
Вооз Барак
2
Джефф - предположим, что некоторые данные из какой-то другой научной области предполагают, что естественная система может быстро достичь своего глобального минимума, в то время как (усиленное) предположение предсказывает, что она застревает на локальном минимуме, и оказывается, что последнее верно. Это , мне кажется, что по крайней мере некоторые доказательства P N P . Это не убедительное доказательство, но, по мере того, как эти вещи накапливаются, если оказывается (усилено), что P N P обладает положительной предсказательной силой, это является аргументом для превращения его в «закон природы». (Это относится, по крайней мере, ко всем алгоритмам / естественным системам, с которыми мы до сих пор сталкивались ...)пNппNппNп
Боаз Барак
15

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

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

Робин Котари
источник
1
Если реальный мир представляет собой объект постоянного размера, то все компьютеры, созданные на сегодняшний день, являются конечными автоматами.
Питер Шор
12

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

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

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

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

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

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

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

Гил Калай
источник
11

Если вы позволите мне немного обобщить ... Давайте расширим вопрос и попросим другие теоретические предположения о сложности и их последствия для научных экспериментов. (Я сосредоточусь на физике.) Недавно была довольно успешная программа, чтобы попытаться понять набор допустимых корреляций между двумя измерительными устройствами, которые, будучи пространственно разделенными, выполняют измерения в (возможно, не локально коррелированных) физических системах ( 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, поскольку отправка нулевых битов не будет нарушать сигнализацию.

Стив Фламмия
источник
7

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

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

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

Джошуа Грохов
источник
Не могли бы вы подробнее рассказать о том, как вы можете использовать GCT для улучшения поиска методом перебора?
Арнаб
граммLNграммLN
Nпп/поLY
@ Райан: Отличное разъяснение. Это заставило меня задуматься над этим вопросом: cstheory.stackexchange.com/questions/1514/…
Джошуа
6

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

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

Jeffε
источник
Предположим, что проведено несколько экспериментов, которые каким-то образом кодируют NP-полные задачи в реальные проблемы и позволяют природе их решать. И предположим, что во всех этих экспериментах было обнаружено, что существует достаточно большой размер входных данных, для которого природа тратит много времени на решение проблемы, тогда это будет свидетельством в пользу утверждения, что природа не может решить NP-полные проблемы эффективно?
Винаяк Патхак
1
Точно нет. Даже если бы вы смогли убедить Природу решить задачи оптимально (в отличие, например, от мыльных пузырей для деревьев Штейнера), и даже если бы вы могли отличить асимптотику от конечного эксперимента, возможно, в Природе используется неэффективный алгоритм.
Джефф
1
(С философской точки зрения я просто не вижу никакой разницы между «убедить природу решить проблему» и «внедрить и запустить алгоритм для решения проблемы». С одной стороны, «надежный метод создания физической системы»). решить проблему »- это работоспособное определение алгоритма; с другой стороны, люди и компьютеры являются частью природы.)
Джефф
5

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

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

Джо Фитцсимонс
источник
Поправьте меня, если я ошибаюсь. Вы подразумеваете, что допущение твердости NP должно иметь физически наблюдаемые последствия?
Мухаммед Аль-Туркистани
Я говорю, что если BQP не содержит NP (что, безусловно, имеет место), то NP, будучи твердым, безусловно, имеет физические последствия. Для очень шумных систем может показаться, что мы могли бы избавиться от стадии BQP и получить результат непосредственно из NP, что сложно, но это требует некоторых физических предположений.
Джо Фицсимонс
пNппзнак равноNп
4

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

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

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

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

chazisop
источник
2
не просто экспоненциальный. на самом деле это башня 2-х.
Суреш Венкат
1
Суреш, конечно, правильно. Кроме того, статья Chazelle - это не анализ скопления птиц, а анализ известных моделей систем управления, основанных на скоплении птиц. В частности, его анализ требует использования «правила гистерезиса», согласно которому птицы не подчиняются себе. См. Комментарий № 3 Chazelle здесь для получения дополнительной информации об этой исследовательской программе.
Аарон Стерлинг
0

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

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

Джеймс Макинтош
источник
2
Точная / аналоговая проблема с 3 телами не просто NP-сложная; это неразрешимо . С другой стороны, настоящие физические системы не являются действительно аналогами; Вы только что заменили одну математическую абстракцию другой.
Джеффс
-1

N


источник
2
Это не правда. Мы действительно можем эффективно решить проблему n-тела, просто нет аналитического решения. Численные методы работают просто отлично.
Джо Фицсимонс
6
Точно. Я никогда не видел, чтобы планета демонстрировала аналитическое решение проблемы n-тела, поэтому сравнение несправедливо.
Робин Котари