Математическое значение гипотез теории сложности вне TCS

25

Знаете ли вы интересные последствия (стандартных) гипотез в теории сложности в других областях математики (т.е. вне теоретической информатики)?

Я бы предпочел ответы где:

  • гипотеза теории сложности является как можно более общей и стандартной; Я также согласен с последствиями сложности конкретных проблем, но было бы неплохо, если бы общепризнанно, что проблемы трудны (или, по крайней мере, они были изучены более чем в нескольких статьях)

  • Подразумевается, что утверждение, безусловно, не является истинным, или другие известные доказательства значительно сложнее.

  • чем удивительнее связь, тем лучше; в частности, подразумевается, что это не должно быть явным утверждением об алгоритмах

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

Этот вопрос в некотором смысле является «обратным» к нашему вопросу об удивительном использовании математики в информатике. У Дика Липтона был пост в блоге именно такого рода: он пишет о последствиях предположения о том, что факторинг имеет большую сложность схем. Следствием этого является то, что некоторые диофантовы уравнения не имеют решений, своего рода утверждение, которое очень трудно доказать безоговорочно. Пост основан на работе с Дэном Бонэ, но я не могу найти статью.

РЕДАКТИРОВАТЬ: Как отмечает Джош Грохов в комментариях, его вопрос о приложениях TCS к классической математике тесно связаны. Мой вопрос, с одной стороны, более разрешающий, потому что я не настаиваю на ограничении "классической математики". Я думаю, что более важным отличием является то, что я настаиваю на доказанном следствии от гипотезы сложности до утверждения в области математики вне TCS. Большинство ответов на вопрос Джоша не относятся к этому типу, но вместо этого дают методы и концепции, полезные в классической математике, которые были разработаны или вдохновлены TCS. Тем не менее, по крайней мере, один ответ на вопрос Джоша является идеальным ответом на мой вопрос: статья Майкла Фридманакоторое мотивировано вопросом идентичного мой, и доказывает теорему в теории узлов, обусловливающие . Он утверждает, что теорема кажется недосягаемой для современных методов теории узлов. По теореме Тоды, если P # P = N P, то иерархия полиномов разрушается, поэтому предположение вполне правдоподобно. Я заинтересован в других подобных результатах.P#PNPP#P=NP

Сашо Николов
источник
Связанный: значения, не для математики, но для "физической реальности"
Остин Бьюкенен
Это то же самое, что cstheory.stackexchange.com/questions/149/… ? Или этот вопрос должен быть более широким, чем этот?
Джошуа Грохов
3
@ Джошуа, есть некоторые совпадения, но я думаю, что они несопоставимы. С одной стороны, я не сильно настаиваю на «классической» математике, то есть нетрудно получить результаты в квантовой механике. С другой стороны, я хотел бы, чтобы гипотезы CC напрямую влияли на математические теоремы вне TCS, в то время как многие ответы на ваш вопрос касаются методов, разработанных в TCS, которые стали полезными в классической математике. Тем не менее, cstheory.stackexchange.com/a/163/4896 является одним из прекрасных ответов на мой вопрос. Слишком много совпадений?
Сашо Николов
1
Я должен , возможно , отправил свой ответ на вопрос Джоша здесь: Bürgisser в -гипотеза означает результаты на эллиптических кривыхL .
Бруно
1
@ Сашо: Я думаю, что все в порядке. Спасибо за разъяснение. (Кстати, когда я сказал «классический» по своему другому вопросу, я не хотел исключать квантовую механику - действительно, квантовая теория поля и квантовая алгебра в настоящее время являются основными математическими темами, изучаемыми в большом количестве (даже высших) математических факультетов. .)
Джошуа Грохов

Ответы:

14

Вот еще один пример из теории графов. Теорема о второстепенных графах говорит нам, что для каждого класса неориентированных графов, замкнутого относительно миноров, существует конечное множество препятствий O b s ( G ), такое что графGObs(G) тогда и только тогда, когда он не содержит граф в O b s ( G ) в качестве несовершеннолетнего. Однако теорема графа минор неотъемлемо неконструктивно и не говорит нам ничего о томкак большой эти наборы непроходимости, то есть, сколько графов содержит для конкретного выбора G .GObs(G)G

В книге «Слишком много препятствий младшего порядка» Майкл Дж. Диннин показал, что при вероятной гипотезе теории сложности размеры нескольких таких наборов препятствий могут быть показаны как большие. Например, рассмотрим параметризованный класс графов не более k . При увеличении k можно ожидать, что множества препятствий O b s G k ) ограничены p ( k ) . Так как количество второстепенных препятствий для того, чтобы иметь нулевой род (то есть быть плоским), равно двум ( O b s ( G 0 ) = {Gkkk будут становиться все более и более сложными, но насколько это так? Диннеен показал, что если полиномиальная иерархия не разрушается до своего третьего уровня, то не существует такого полинома p , который быпозволял определитьколичество препятствий в O b s (Obs(Gk)pObs(Gk)p(k) ), этот суперполиномиальный рост не сразу очевиден (хотя я полагаю, что это может быть доказано безоговорочно). Хорошая вещь о результате Диннина состоит в том, что он применяется к размерам наборов препятствий, соответствующимлюбомупараметризованному набору второстепенных идеалов G k, для которого выбирается наименьшее kObs(G0)={K5,K3,3}Gkkдля которого NP-труден; во всех таких параметризованных второстепенных идеалах размеры набора препятствий должны расти суперполиномиально. GGk

Барт Янсен
источник
Спасибо, Барт! Это очень интересно Я принимаю ваш ответ как наиболее высоко оцененный. Спасибо всем за ответы!
Сашо Николов
6

Вот пример: вычислительная сложность и информационная асимметрия в финансовых продуктах Arora, Barak и Ge показывают, что вычислительно трудно (например, NP-hard) правильно оценить производные - они используют плотный подграф как сложную сложную задачу.

В том же духе и намного раньше известная статья Бартольди, Тови и Трика о сложности манипулирования выборами.

Суреш Венкат
источник
2
Суреш, в некоторой степени это все еще результаты сложности (с социальными последствиями). Я имел в виду результаты, которые не об алгоритмах. Тем не менее, оба великолепны!
Сашо Николов
Я не был полностью уверен, что вы искали. Я предполагаю, что вы хотите что-то вроде обращения "замкнутых кривых, похожих на время, квантовых и классических"?
Суреш Венкат
1
На самом деле результат CTC является прекрасным примером. Я имею в виду даже не обратное, а само утверждение в противоположность: если квантовые и классические не разрушаются, то (полиномиальных) ЦОК не существует.
Сашо Николов
1
так вы говорите, я должен опубликовать новый ответ :)?
Суреш Венкат
Я думаю, что говорю это :)
Сашо Николов
5

S2КS2К2δК

Это очень в духе статьи Майка Фридмана, упомянутой ранее.

Исаак Меклер
источник
-6

похоже, что многие вопросы разделения классов сложности TCS имеют серьезные последствия в математике. вопрос P =? NP, в частности, кажется, имеет очень глубокие связи во многих областях, и это включает в себя математику. некоторые известные случаи в этой области:

  • Показано, что проблема Нильбертса Нуллстелленсаца, сформулированная в начале 20-го века, обладает способностью к тяготению, тесно связанной со сложностью P vs NP, например, в статье «О неразрушимости нульштелленсатса Гильберта и алгебраической версии« NP ̸ = P? » Шуба / Смейла. это постоянная область изучения, например, в области компьютерной алгебры, комбинаторики и сложности: Nullstellensatz Гильберта и NP-полные задачи Маргулиса.

  • Теорема Фагинса (Википедия):

    Теорема Фейгина является результатом описательной теории сложности, которая утверждает, что множество всех свойств, выражаемых в экзистенциальной логике второго порядка, является в точности классом сложности NP. Это замечательно, поскольку это характеристика класса NP, которая не вызывает модель вычислений, такую ​​как машина Тьюринга.

    главное / неожиданное значение P = NP здесь будет означать, что все логические утверждения второго порядка могут быть эффективно вычислены.

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

    a,б,сИкссИкс2a(модификацияб)

ВЗН
источник
3
Вы не поняли вопрос: все результаты, которые вы упоминаете, касаются сложности. я хочу, чтобы не сложность была следствием утверждения в теории сложности
Сашо Николов