<p>Here's an example: <a href="http://www.cs.princeton.edu/~rongge/derivative.pdf">Computational complexity and informational asymmetry in financial products</a> 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. </p>

<p>Along the same lines and much earlier is the famous paper by <a href="http://link.springer.com/article/10.1007/BF00295861#page-1">Bartholdi, Tovey, and Trick</a> on the hardness of manipulating an election. </p>

CC BY-SA 3.0
2014-01-10T21:14:57.087Z
Suresh, to some extent these are still complexity results (with social implications). I had in mind results that are not about algorithms. Still, both are great!
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T21:21:22.323Z
I wasn't entirely sure what you were looking for tbh. I'm guessing you want something like the converse of "closed timelike curves collapse quantum and classical" ?
Suresh Venkat
CC BY-SA 3.0
2014-01-10T23:45:56.083Z
Actually the CTC result is a perfect example. I mean not even the converse, but the statement itself in contrapositive: if quantum and classical do not collapse, then (polynomial) CTCs do not exist.
Sasho Nikolov
CC BY-SA 3.0
2014-01-11T05:14:32.373Z
so you're saying I should post a new answer :) ?
Suresh Venkat
CC BY-SA 3.0
2014-01-11T15:07:37.970Z
I think I am saying that :)
Sasho Nikolov
CC BY-SA 3.0
2014-01-12T07:12:54.457Z
Hmm. I'm not sure the contrapositive even makes sense. the result is a kind of oracle computation: you can collapse quantum and classical with a poly-sized CTC "oracle" and they equal PSPACE. There isn't a natural contrapositive that says that a specific complexity conjecture implies non-existence of a physical object.
Suresh Venkat
CC BY-SA 3.0
2014-01-12T13:25:13.983Z
This paper is also fertile ground for asking [social and ethical questions about mathematics in finance](http://egtheory.wordpress.com/2013/10/13/finance-and-mathematics/).
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-12T18:38:28.647Z
Suresh, I see, fair enough.
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T21:08:15.547Z
2014-01-10T21:08:15.547Z
Suresh Venkat
<p>As suggested by Sasho, my <a href="https://cstheory.stackexchange.com/a/20554/976">answer</a> to the question "<a href="https://cstheory.stackexchange.com/q/149/976">Applications of TCS to classical mathematics?</a>" follows:</p>

<blockquote>
  <p>In his paper <a href="http://www.cs.ou.edu/~qcheng/paper/BSS.pdf" rel="nofollow noreferrer"><strong>Straight Line Programs and Torsion Points on Elliptic Curves</strong></a>, 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. </p>
  
  <p>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.</p>
  
  <p>¹ 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$.</p>
</blockquote>

CC BY-SA 3.0
2014-01-11T13:14:57.553Z
2014-01-11T13:14:57.553Z
2017-04-13T12:32:28.077Z
Bruno
<p>You can use complexity theoretic conjectures to prove things about, e.g., the representation theory of the symmetric group (see <a href="https://parametricity.com/posts/rep-theory-round-two.html" rel="noreferrer">this blog post</a>). 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.</p>

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

CC BY-SA 3.0
2017-02-26T06:49:54.813Z
2017-02-26T06:49:54.813Z
Izaak Meckler
<p>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:</p>

<ul>
<li><p>Hilberts <a href="http://en.wikipedia.org/wiki/Hilbert&#39;s_Nullstellensatz" rel="nofollow noreferrer">Nullstellensatz problem</a> formulated in the early 20th century has been shown to have a tractability closely relating to the P vs NP complexity eg in <a href="http://www.cs.technion.ac.il/~janos/COURSES/238900-13/Papers-1/ShubSmale-pap97.pdf" rel="nofollow noreferrer">ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP ̸= P?”</a> by Shub/Smale. this is a continuing area of study eg in <a href="http://www.math.psu.edu/margulies/papers/thesis.pdf" rel="nofollow noreferrer">Computer Algebra, Combinatorics, and Complexity: Hilbert’s Nullstellensatz and NP-complete Problems</a> by Margulies.</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Fagin&#39;s_theorem" rel="nofollow noreferrer">Fagins theorem</a> (wikipedia):</p>

<blockquote>
  <p>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.  </p>
</blockquote>

<p>the major/surprising implication of P=NP here would mean that all second-order logic assertions could be efficiently computed.</p></li>
<li><p>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.</p>

<blockquote>
  <p>As proved by <a href="http://dx.doi.org/10.1145/800113.803627" rel="nofollow noreferrer">Manders and Adleman</a>, 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$.</p>
</blockquote>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/14124/is-there-a-natural-problem-on-the-naturals-that-is-np-complete">Is there a natural problem on the naturals that is NP-complete?</a> tcs.se</li>
<li><a href="https://mathoverflow.net/questions/72628/number-theory-and-np-complete">number theory and NP complete</a> mathoverflow</li>
</ul></li>
</ul>

CC BY-SA 3.0
2014-01-13T16:34:26.997Z
you did not understand the question: all the results you mention are about complexity. i want a non-complexity consequence of a a statement in complexity theory
Sasho Nikolov
CC BY-SA 3.0
2014-01-13T02:37:57.257Z
2014-01-13T02:37:57.257Z
2017-04-13T12:57:54.777Z
vzn
<p>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}$. </p>

<p>In <a href="http://www.jucs.org/jucs_3_11/too_many_minor_order">Too Many Minor Order Obstructions</a>, 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 <em>any</em> 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.  </p>

CC BY-SA 3.0
2014-01-15T22:04:17.920Z
Thanks Bart! This is very interesting. I am accepting your answer as the most highly upvoted one. Thanks to everyone for the answers!
Sasho Nikolov
CC BY-SA 3.0
2014-01-12T10:23:00.627Z
2014-01-12T10:23:00.627Z
Bart Jansen
<blockquote>
  <p>Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)?</p>
</blockquote>

<p>I would prefer answers where:</p>

<ul>
<li><p>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)</p></li>
<li><p>the implication is a statement that is not known to be true unconditionally, or other known proofs are considerably more difficult</p></li>
<li><p>the more surprising the connection the better; in particular, the implication should not be a statement explicitly about algorithms</p></li>
</ul>

<p>"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.</p>

<p>This question is in some sense "the converse" of a <a href="https://cstheory.stackexchange.com/q/1920/4896">question</a> we had about surprising uses of mathematics in computer science. Dick Lipton had a <a href="http://rjlipton.wordpress.com/2009/03/11/factoring-could-be-easy/" rel="nofollow noreferrer">blog post</a> 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. </p>

<p><strong>EDIT:</strong> As Josh Grochow notes in the comments, <a href="https://cstheory.stackexchange.com/a/163/4896">his question</a> 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 <a href="https://cstheory.stackexchange.com/a/163/4896">one answer</a> to Josh's question is a perfect answer to my question: <a href="http://arxiv.org/abs/0810.0033" rel="nofollow noreferrer">Michael Freedman's paper</a> 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.</p>

CC BY-SA 3.0
2014-01-10T21:32:23.773Z
Related: implications, not for math, but [for "physical reality"](http://www.scottaaronson.com/papers/npcomplete.pdf)
Austin Buchanan
CC BY-SA 3.0
2014-01-10T22:15:16.593Z
Is this the same as http://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics? Or is this question meant to be more broad than that one?
Joshua Grochow
CC BY-SA 3.0
2014-01-10T23:01:09.350Z
isnt P=?NP the canonical/epitomizing example?
vzn
CC BY-SA 3.0
2014-01-10T23:55:22.220Z
@Joshua, there is some overlap, but I think they are incomparable. On one hand I do not strongly insist on "classical" mathematics, i.e. non-complexity results in quantum mechanics are ok. On the other hand, I'd like direct implications from CC conjectures to math theorems outside TCS, while a lot of the answers to your question are about *techniques* developed in TCS that turned our useful in classical math. Still, http://cstheory.stackexchange.com/a/163/4896 is one perfect answer to my question. Too much overlap?
Sasho Nikolov
CC BY-SA 3.0
2014-01-11T08:25:58.553Z
I should maybe have posted my answer to Josh's question here: [Bürgisser's $L$-conjecture implies results on elliptic curves](http://cstheory.stackexchange.com/a/20554/976).
Bruno
CC BY-SA 3.0
2014-01-11T12:53:44.487Z
@Bruno I believe you can still post an answer, with a link to the old one
Sasho Nikolov
CC BY-SA 3.0
2014-01-12T19:58:58.020Z
@Sasho: I think it's okay. Thanks for clarifying. (BTW, when I said "classical" on my other question I didn't mean to exclude quantum mechanics - indeed, quantum field theory and quantum algebra are both major mathematical topics nowadays, studied in a large number of (even top) math departments.)
Joshua Grochow
CC BY-SA 3.0
2014-01-12T22:07:56.330Z
there are some unstated/unstandardized/"floating around" conjectures relating to undecidability boundaries that could have major implications for mathematics. the basic idea is that by attacking the boundary of undecidable problems in TCS, this may eventually yield techniques that resolve difficult open mathematical problems. but this angle so far doesnt seem to strictly fit the tight critieria/preferences listed.
vzn
CC BY-SA 3.0
2014-01-17T13:15:00.540Z
Do "P vs NP issues" having an impact on applied math (and somehow engineering) count ?
IgorCarron
CC BY-SA 3.0
2014-01-17T22:00:06.583Z
@IgorCarron maybe, if the impact is surprising. Things like "if P = NP then we can optimize some practically important function fast" are not surprising.
Sasho Nikolov
CC BY-SA 3.0
2014-01-23T16:32:41.823Z
@SashoNikolov I was more thinking the converse to that statement really. Something like the sharp phase transition observed empirically (dividing P and NP regions of the phase space) that have a direct bearing on whether or not some applied math inverse problem is OK, which eventually has a bearing as to whether sensing hardware can be built... or not.
IgorCarron
<cc.complexity-theory><conditional-results>
Mathematical implications of complexity theory conjectures outside TCS
Sasho Nikolov
# Mathematical implications of complexity theory conjectures outside TCS

(Asked by: username_0 on 2014-01-10)

> 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](https://cstheory.stackexchange.com/q/1920/4896) we had about surprising uses of mathematics in computer science. Dick Lipton had a [blog post](http://rjlipton.wordpress.com/2009/03/11/factoring-could-be-easy/) 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](https://cstheory.stackexchange.com/a/163/4896) 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](https://cstheory.stackexchange.com/a/163/4896) to Josh's question is a perfect answer to my question: [Michael Freedman's paper](http://arxiv.org/abs/0810.0033) 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.

**Tags:** cc.complexity-theory, conditional-results

> **Comments:**
> **username_1**: Related: implications, not for math, but [for "physical reality"](http://www.scottaaronson.com/papers/npcomplete.pdf)  
> **username_2**: Is this the same as http://cstheory.stackexchange.com/questions/149/applications-of-tcs-to-classical-mathematics? Or is this question meant to be more broad than that one?  
> **username_3**: isnt P=?NP the canonical/epitomizing example?  
> **username_0**: @Joshua, there is some overlap, but I think they are incomparable. On one hand I do not strongly insist on "classical" mathematics, i.e. non-complexity results in quantum mechanics are ok. On the other hand, I'd like direct implications from CC conjectures to math theorems outside TCS, while a lot of the answers to your question are about *techniques* developed in TCS that turned our useful in classical math. Still, http://cstheory.stackexchange.com/a/163/4896 is one perfect answer to my question. Too much overlap?  
> **username_4**: I should maybe have posted my answer to Josh's question here: [Bürgisser's $L$-conjecture implies results on elliptic curves](http://cstheory.stackexchange.com/a/20554/976).  
> **username_0**: @username_4 I believe you can still post an answer, with a link to the old one  
> **username_2**: @Sasho: I think it's okay. Thanks for clarifying. (BTW, when I said "classical" on my other question I didn't mean to exclude quantum mechanics - indeed, quantum field theory and quantum algebra are both major mathematical topics nowadays, studied in a large number of (even top) math departments.)  
> **username_3**: there are some unstated/unstandardized/"floating around" conjectures relating to undecidability boundaries that could have major implications for mathematics. the basic idea is that by attacking the boundary of undecidable problems in TCS, this may eventually yield techniques that resolve difficult open mathematical problems. but this angle so far doesnt seem to strictly fit the tight critieria/preferences listed.  
> **username_5**: Do "P vs NP issues" having an impact on applied math (and somehow engineering) count ?  
> **username_0**: @username_5 maybe, if the impact is surprising. Things like "if P = NP then we can optimize some practically important function fast" are not surprising.  
> **username_5**: @SashoNikolov I was more thinking the converse to that statement really. Something like the sharp phase transition observed empirically (dividing P and NP regions of the phase space) that have a direct bearing on whether or not some applied math inverse problem is OK, which eventually has a bearing as to whether sensing hardware can be built... or not.  

---

## 5 answers

### Answer by username_9 on 2014-01-12. Score: 14 | Accepted answer

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](http://www.jucs.org/jucs_3_11/too_many_minor_order), 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.

> **Comments:**
> **username_0**: Thanks Bart! This is very interesting. I am accepting your answer as the most highly upvoted one. Thanks to everyone for the answers!  

---

### Answer by username_6 on 2014-01-10. Score: 6

Here's an example: [Computational complexity and informational asymmetry in financial products](http://www.cs.princeton.edu/~rongge/derivative.pdf) 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](http://link.springer.com/article/10.1007/BF00295861#page-1) on the hardness of manipulating an election.

> **Comments:**
> **username_0**: Suresh, to some extent these are still complexity results (with social implications). I had in mind results that are not about algorithms. Still, both are great!  
> **username_6**: I wasn't entirely sure what you were looking for tbh. I'm guessing you want something like the converse of "closed timelike curves collapse quantum and classical" ?  
> **username_0**: Actually the CTC result is a perfect example. I mean not even the converse, but the statement itself in contrapositive: if quantum and classical do not collapse, then (polynomial) CTCs do not exist.  
> **username_6**: so you're saying I should post a new answer :) ?  
> **username_0**: I think I am saying that :)  
> **username_6**: Hmm. I'm not sure the contrapositive even makes sense. the result is a kind of oracle computation: you can collapse quantum and classical with a poly-sized CTC "oracle" and they equal PSPACE. There isn't a natural contrapositive that says that a specific complexity conjecture implies non-existence of a physical object.  
> **username_7**: This paper is also fertile ground for asking [social and ethical questions about mathematics in finance](http://egtheory.wordpress.com/2013/10/13/finance-and-mathematics/).  
> **username_0**: Suresh, I see, fair enough.  

---

### Answer by username_4 on 2014-01-11. Score: 6

As suggested by Sasho, my [answer](https://cstheory.stackexchange.com/a/20554/976) to the question "[Applications of TCS to classical mathematics?](https://cstheory.stackexchange.com/q/149/976)" follows:

> In his paper [**Straight Line Programs and Torsion Points on Elliptic Curves**](http://www.cs.ou.edu/~qcheng/paper/BSS.pdf), 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 by username_8 on 2017-02-26. Score: 5

You can use complexity theoretic conjectures to prove things about, e.g., the representation theory of the symmetric group (see [this blog post](https://parametricity.com/posts/rep-theory-round-two.html)). 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 by username_3 on 2014-01-13. Score: -6

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](http://en.wikipedia.org/wiki/Hilbert's_Nullstellensatz) 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?”](http://www.cs.technion.ac.il/~janos/COURSES/238900-13/Papers-1/ShubSmale-pap97.pdf) by Shub/Smale. this is a continuing area of study eg in [Computer Algebra, Combinatorics, and Complexity: Hilbert’s Nullstellensatz and NP-complete Problems](http://www.math.psu.edu/margulies/papers/thesis.pdf) by Margulies.
* [Fagins theorem](http://en.wikipedia.org/wiki/Fagin's_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](http://dx.doi.org/10.1145/800113.803627), 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?](https://cstheory.stackexchange.com/questions/14124/is-there-a-natural-problem-on-the-naturals-that-is-np-complete) tcs.se
  + [number theory and NP complete](https://mathoverflow.net/questions/72628/number-theory-and-np-complete) mathoverflow

> **Comments:**
> **username_0**: you did not understand the question: all the results you mention are about complexity. i want a non-complexity consequence of a a statement in complexity theory  

---

