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

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

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

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

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

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

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

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

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

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

В книге «Слишком много препятствий младшего порядка» Майкл Дж. Диннин показал, что при вероятной гипотезе теории сложности размеры нескольких таких наборов препятствий могут быть показаны как большие. Например, рассмотрим параметризованный класс графов не более k . При увеличении k можно ожидать, что множества препятствий O b s G k ) ограничены p ( k ) . Так как количество второстепенных препятствий для того, чтобы иметь нулевой род (то есть быть плоским), равно двум ( O b s ( G 0 ) = $\mathcal{G}_k$$k$$k$ будут становиться все более и более сложными, но насколько это так? Диннеен показал, что если полиномиальная иерархия не разрушается до своего третьего уровня, то не существует такого полинома p , который быпозволял определитьколичество препятствий в O b s$\mathcal{Obs}(\mathcal{G}_k)$$p$$\mathcal{Obs}(\mathcal{G}_k)$$p(k)$ ), этот суперполиномиальный рост не сразу очевиден (хотя я полагаю, что это может быть доказано безоговорочно). Хорошая вещь о результате Диннина состоит в том, что он применяется к размерам наборов препятствий, соответствующимлюбомупараметризованному набору второстепенных идеалов G k, для которого выбирается наименьшее$\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$$\mathcal{G}_k$$k$для которого NP-труден; во всех таких параметризованных второстепенных идеалах размеры набора препятствий должны расти суперполиномиально. $G \in \mathcal{G}_k$

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

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

Как предположил Сашо, мой ответ на вопрос « Применения ТКС к классической математике? » Следующий:

$L$$\tau$

$L$

$\tau$$p$$\tau$$(1+\tau)^c$$c$

$S_{2^k}$$S_{2^k}$$2^{\delta k}$

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

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

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

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

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

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

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

  $a,b,c$$x\le c$$x^2\equiv a\pmod b$

  • Есть ли естественная проблема на натуральных объектах, которая является NP-полной? tcs.se
  • теория чисел и NP полный Mathoverflow