Mathematical implications of complexity theory conjectures outside TCS

Question

Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)?

I would prefer answers where:

• the complexity theory conjecture is as general and standard as possible; I am ok with consequences of the hardness of specific problems too, but it would be nice if the problems are widely believed to be hard (or at least have been studied in more than a couple of papers)

• the implication is a statement that is not known to be true unconditionally, or other known proofs are considerably more difficult

• the more surprising the connection the better; in particular, the implication should not be a statement explicitly about algorithms

"If pigs could fly, horses would sing" type of connections are ok, too, as long as the flying pigs come from complexity theory, and the singing horses from some field of math outside of computer science.

This question is in some sense "the converse" of a question we had about surprising uses of mathematics in computer science. Dick Lipton had a blog post exactly along these lines: he writes about consequences of the conjecture that factoring has large circuit complexity. The consequences are that certain diophantine equations have no solutions, a kind of statement that can very hard to prove unconditionally. The post is based on work with Dan Boneh, but I cannot locate a paper.

EDIT: As Josh Grochow notes in the comments, his question about applications of TCS to classical math is closely related. My question is, on one hand, more permissive, because I do not insist on the "classical math" restriction. I think the more important difference is that I insist on a proven implication from a complexity conjecture to a statement in a field of math outside TCS. Most of the answers to Josh's question are not of this type, but instead give techniques and concepts useful in classical math that were developed or inspired by TCS. Nevertheless, at least one answer to Josh's question is a perfect answer to my question: Michael Freedman's paper which is motivated by a question identical to mine, and proves a theorem in knot theory, conditional on $\mathsf{P}^{\#P} \ne \mathsf{NP}$. He argues the theorem seems out of reach of current techniques in knot theory. By Toda's theorem, if $\mathsf{P}^{\#P} = \mathsf{NP}$ then the polynomial hierarchy collapses, so the assumption is quite plausible. I am interested in other similar results.

Answer 1

Here's another example from graph theory. The graph minor theorem tells us that, for every class $\mathcal{G}$ of undirected graphs that is closed under minors, there is a finite obstruction set $\mathcal{Obs(G)}$ such that a graph is in $\mathcal{G}$ if and only if it does not contain a graph in $\mathcal{Obs(G)}$ as a minor. However, the graph minor theorem is inherently nonconstructive and does not tell us anything about how big these obstruction sets are, i.e., how many graphs it contains for a particular choice of $\mathcal{G}$.

In Too Many Minor Order Obstructions, Michael J. Dinneen showed that under a plausible complexity-theoretic conjecture, the sizes of several of such obstruction sets can be shown to be large. For example, consider the parameterized class $\mathcal{G}_k$ of graphs of genus at most $k$. As $k$ increases, we can expect the obstruction sets $\mathcal{Obs}(\mathcal{G}_k)$ to become more and more complicated, but how much so? Dinneen showed that if the polynomial hierarchy does not collapse to its third level then there is no polynomial $p$ such that the number of obstructions in $\mathcal{Obs}(\mathcal{G}_k)$ is bounded by $p(k)$. Since the number of minor obstructions for having genus zero (i.e. being planar) is just two ($\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$), this superpolynomial growth is not immediately obvious (although I believe it can be proven unconditionally). The nice thing about Dinneen's result is that it applies to the sizes of obstruction sets corresponding to any parameterized set of minor ideals $\mathcal{G}_k$ for which deciding the smallest $k$ for which $G \in \mathcal{G}_k$ is NP-hard; in all of such parameterized minor ideals the obstruction set sizes must grow superpolynomially.

Answer 2

Here's an example: Computational complexity and informational asymmetry in financial products by Arora, Barak and Ge shows that it can be computationally intractable (ie NP-hard) to price derivatives correctly - they use densest subgraph as an embedded hard problem.

Along the same lines and much earlier is the famous paper by Bartholdi, Tovey, and Trick on the hardness of manipulating an election.

Answer 3

As suggested by Sasho, my answer to the question "Applications of TCS to classical mathematics?" follows:

In his paper Straight Line Programs and Torsion Points on Elliptic Curves, Qi Cheng relates Bürgisser's $L$-conjecture (a variant of Shub and Smale's $\tau$-conjecture¹) to the Torsion Theorem and to Masser's Theorem in the field of elliptic curves.

Very roughly, if the $L$-conjecture is true (or a weaker version of it), then one can "easily" deduce these both theorems. Their original proofs are much harder.

¹ The $\tau$-conjecture asserts that if a polynomial $p$ has a constant-free straight-line program (or arithmetic circuit) of size $\tau$, its number of integer roots is at most $(1+\tau)^c$ for some absolute constant $c$.

Answer 4

You can use complexity theoretic conjectures to prove things about, e.g., the representation theory of the symmetric group (see this blog post). Roughly speaking, since the word problem of the symmetric group $S_{2^k}$ is coNP hard, $S_{2^k}$ cannot have a faithful (i.e., injective) representation of dimension any smaller than $2^{\delta k}$ unless SAT has sub-exponential size circuits.

It is very much in the spirit of Mike Freedman's paper mentioned earlier.

Answer 5

it appears that many TCS complexity class separation questions have major implications in mathematics. the P=?NP question in particular seems to have very deep connections across many fields and this includes mathematics. some notable cases in this area:

• Hilberts Nullstellensatz problem formulated in the early 20th century has been shown to have a tractability closely relating to the P vs NP complexity eg in ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP ̸= P?” by Shub/Smale. this is a continuing area of study eg in Computer Algebra, Combinatorics, and Complexity: Hilbert’s Nullstellensatz and NP-complete Problems by Margulies.

• Fagins theorem (wikipedia):

  Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine.

  the major/surprising implication of P=NP here would mean that all second-order logic assertions could be efficiently computed.

• another case is that there are various NP complete problems stated mostly only in mathematical terms (eg no reference to TCS concepts like TMs, nondeterminism etc). this list could be very large if graph theory is (quite reasonably) regarded as mathematical. however even narrow interpretations of "mathematical" lead to cases, for example in number theory.

  As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

  • Is there a natural problem on the naturals that is NP-complete? tcs.se
  • number theory and NP complete mathoverflow