Существуют ли законы сохранения в теории сложности?

46

Позвольте мне начать с нескольких примеров. Почему так просто показать, что CVP в P, а так сложно показать, что LP в P; в то время как оба являются P-полными проблемами.

Или взять первичность. Композиты проще показывать в NP, чем простые числа в NP (что требовало Pratt) и, в конечном итоге, в P. Почему вообще должна была отображаться эта асимметрия?

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

Существует ли поддающееся количественному определению понятие «работа» и существует ли «закон сохранения» в теории сложности? Это показывает, например, что, хотя CVP и LP оба являются P-полными, они скрывают свои сложности в «разных местах» - один в сокращении (Является ли CVP простым, потому что вся работа выполняется в сокращении?) И Другое в выразительности языка.

Кто-нибудь еще тошнит и с некоторыми соображениями? Или мы пожимаем плечами и говорим / принимаем, что это природа вычислений?

Это мой первый вопрос к форуму: пальцы скрещены.

Редактировать: CVP - это проблема значения схемы, а LP - линейное программирование. Спасибо Sadeq, за указание на путаницу.

V Vinay
источник
7
Сначала я принял CVP за проблему ближайшего вектора (которая является NP-сложной). Тогда я заметил, что это проблема стоимости схемы . Я думал, что было бы полезно упомянуть об этом.
MS Dousti
5
интересный вопрос. Не уверен, что есть интересный ответ, хотя :)
Суреш Венкат
7
Просто наблюдение: сложность доказательства членства в NP (скажем) не является свойством языка, но является свойством описания языка. Например, требуется некоторое усилие, чтобы доказать, что множество простых чисел находится в NP, но тривиально, что множество целых чисел, имеющих сертификат Pratt, находится в NP.
Цуёси Ито
2
Разве пространственно-временные ограничения не применимы в качестве закона сохранения в смысле формулировки этого вопроса?
Маверик Ву
1
Представление Чарльза Беннета о глубине вычислений (изначально «логическая глубина») может охватить часть интуиции «работы, необходимой для демонстрации факта сложности».
Аарон Стерлинг

Ответы:

13

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

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

Есть одна связанная вещь, которую я хотел выяснить. В некоторых NP-полных задачах вы можете найти ограниченную версию в P; с гамильтоновым путем, если вы укажете, что граф является DAG, то существует алгоритм p-времени для его решения. С другими проблемами, такими как TSP, часто бывают алгоритмы p-времени, которые приближаются к оптимальным. Мне кажется, что для алгоритмов с ограниченным p-временем должна быть некоторая пропорциональная связь между предполагаемой информацией о сложении и снижением сложности во время выполнения. В случае TSP мы не принимаем дополнительную информацию, мы снижаем точность, которая, как я ожидаю, окажет аналогичное влияние на любой вид алгоритмического получения информации.

Примечание о законах сохранения

В начале 1900-х годов был малоизвестный немецко-американский математик по имени Эмили Нетер. Среди прочего, Эйнштейн и Гильберт назвали ее самой важной женщиной в истории математики. В 1915 году она опубликовала то, что сейчас известно как первая теорема Нетера . Теорема была о физических законах сохранения, и сказал, что все законы сохранения имеют соответствующую дифференциальную симметрию в физической системе. Сохранение углового момента происходит из вращательной симметрии в пространстве, сохранение линейного импульса - это перемещение в пространстве, сохранение энергии - это перемещение во времени. Учитывая, что для существования какого-либо закона сохранения сложности в формальном смысле, должна быть некоторая соответствующая дифференциальная симметрия в функции Ланграга.

MattRS
источник
2
+1 Отличный ответ! У меня часто были подобные размышления (@MattRS: отправьте мне письмо). Между прочим, я не думаю, что Эмми Нетер "малоизвестна", но на самом деле она совершенно противоположна, хотя, возможно, она мало известна в TCS. Первая теорема Нётера хорошо известна физикам, и нётеровы кольца являются центральным объектом изучения коммутативной алгебры и алгебраической геометрии. Несколько других важных теорем, в основном в этих областях, также носят ее имя.
Джошуа Грохов
Да, это то, что я имел в виду; не очень известный для комп. Я всегда считал, что абстрактная алгебра должна более широко преподаваться в CS.
MattRS
Хотя этот аргумент убедителен, мне интересно, совместим ли он со многими проблемами, имеющими резкий порог приближаемости. (Под этим я подразумеваю проблему, заключающуюся в том, что достижение коэффициента аппроксимации легко, но трудно для всех ) Почему существует связь между требуемой точностью и алгоритмическим получением информации так резко прерывистым? α - ϵ ϵ > 0α>1αϵϵ>0
Шриватсан Нараянан
6

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

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

Длительность доказательства теоремы, если она решаема в логической системе, полностью зависит от множеств аксиом и правил вывода .

Например, рассмотрим логику высказываний, для которой существует несколько характеристик: Фреге (1879), Никод (1917) и Мендельсон (1979). (См. Этот короткий опрос для получения дополнительной информации.)

Последняя система (Мендельсон) имеет три аксиомы и одно правило вывода (modus ponens). Учитывая эту короткую характеристику, действительно трудно доказать даже самые тривиальные теоремы, скажем, . Здесь, трудно , я имею в виду минимальная длина доказательства высока.φφ

Эта проблема называется доказательством сложности . Чтобы процитировать Beame & Pitassi :

Один из самых основных вопросов логики заключается в следующем: учитывая универсально верное утверждение (тавтология), какова длина кратчайшего доказательства утверждения в некоторой стандартной аксиоматической системе доказательств? Логическая версия этого вопроса с точки зрения высказываний особенно важна в информатике как для доказательства теорем, так и для теории сложности. Важными смежными алгоритмическими вопросами являются: Есть ли эффективный алгоритм, который даст доказательство какой-либо тавтологии? Существует ли эффективный алгоритм для кратчайшего доказательства какой-либо тавтологии? Такие вопросы доказательства теоремы и сложности вдохновили основополагающую статью Кука о NP-полноте, в частности, озаглавленную «Сложность процедур доказательства теорем», и были рассмотрены еще раньше Гёделем в его теперь известном письме фон Нейману.

М.С. Дусти
источник
6

Я думал об этом же вопросе на днях, когда я повторял несколько лекций Фейнмана по физике и пришел к уроку 4 по сохранению энергии. В лекции Фейнман использует пример простой машины, которая (посредством некоторой системы рычагов или шкивов или чего-либо еще) снижает вес одной единицы на некоторое расстояние х, и использует ее для поднятия второго веса в 3 единицы. Как высоко можно поднять вес? Фейнман отмечает, что если машина обратима, нам не нужно ничего знать о механизме машины - мы можем обращаться с ней как с черным ящиком - и она всегда поднимает вес на максимально возможное расстояние ( х / 3 в данном случае).

Есть ли у этого аналога в вычислениях? Идея обратимых вычислений напоминает работу Ландауэра и Беннетта, но я не уверен, что это смысл термина, в котором мы заинтересованы. Интуитивно понятно, что если у нас есть алгоритм для какой-то задачи, который является оптимальным, тогда не будет потрачена впустую «работа», выполняющая перемешивание битов; в то время как подход грубой силы к той же проблеме будет отбрасывать циклы процессора влево и вправо. Однако я полагаю, что можно построить физически обратимую схему для любого алгоритма.

Я думаю, что первый шаг в приближении закона сохранения к вычислительной сложности - это выяснить, что именно должно быть сохранено. Пространство и время являются важными метриками, но из наличия компромиссов между пространством и временем ясно, что ни один из них сам по себе не будет адекватным показателем того, сколько «работы» выполняется алгоритмом. Существуют и другие метрики, такие как разворот головы TM или пересечение ленточных ячеек. Кажется, что ни один из них на самом деле не близок нашему пониманию объема «работы», необходимой для выполнения вычислений.

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

Kurt
источник
3

Некоторые наблюдения, предполагающие существование закона сохранения:

<pPNP

P={L|L<pHornSAT}

NP={L|L<p3SAT}

CoNP={L|L¯<p3SAT}

NPC={L|L<p3SAT,3SAT<pL}

PC={L|L<pHornSAT,HornSAT<pL}

PP={L|L<pHornSAT,L¯<pHornSAT}PNPP=NP

Мухаммед Аль-Туркистани
источник
1

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

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

Мухаммед Аль-Туркистани
источник