<p>This <a href="http://people.csail.mit.edu/costis/reconstruct.pdf">2009 survey by Daskalakis</a> surveys the complexity of computing Nash equilibria. His previous work with Goldberg and Papadimitriou demonstrated that exactly computing such equilibria is PPAD-complete. This is not as strong a statement as if the problem were NP-hard, but still provides evidence that computing Nash equilibria is intractable, throwing into doubt the predictive power of Nash equilibria. One salvation would be to demonstrate a PTAS for $\epsilon$-Nash equilibria for desired accuracy $\epsilon$. But the current best is an non-oblivious approximation algorithm that runs in time quasipolynomial in $1/\epsilon$.</p>

CC BY-SA 2.5
2010-11-15T11:51:15.697Z
An aside: Cryptography is obviously a *positive* application of a computationally hard problem. This would be an example of an application of a complexity theorem outside of the complexity field that is *negative*. Are you particularly interested in one over the other, @rphv?
Daniel Apon
CC BY-SA 2.5
2010-11-16T05:59:02.807Z
I'm interested in both positive and negative applications. If the existence of computationally hard problems is analogous to 2LOT or C, then I feel like we should be bumping in to examples/consequences of it often, much as we often encounter real-world objects that 'embody' those properties (car engines, electricity, etc.) Even if we don't "get anything" (like crypto) out of the fact that hard problems exist, I think it might be useful to consider the existence of hard problems when thinking about the world.  In other words, "How does the existence of hard problems affect our lives?"
rphv
CC BY-SA 2.5
2010-11-15T08:59:59.337Z
2010-11-15T08:59:59.337Z
Daniel Apon
<p>To add to Dana's answer which basically says hardness can be converted into randomness. The existence of hard functions with exponential circuit complexity lower bound can be used to efficiently derandomize every probabilistic algorithm in $BPP$. This would imply $P=BPP$. </p>

CC BY-SA 2.5
2010-11-15T18:36:27.980Z
2010-11-15T18:36:27.980Z
Mohammad Al-Turkistany
<p>Assuming "hard" functions exist (for a variety of definitions of "hard"), we can construct pseudorandom generators.</p>

CC BY-SA 2.5
2010-11-15T17:04:56.703Z
2010-11-15T17:04:56.703Z
Dana Moshkovitz
<p>The most recent issue of the CACM has an <a href="http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext">article by Faliszewski, Hemaspaandra and Hemaspaandra</a> on the use of complexity theory in the realm of social choice theory and election design in particular. One example of such a result is that while Arrow's theorem guarantees that any election system is 'hackable', it might be NP-hard to do so. </p>

CC BY-SA 2.5
2010-11-15T10:13:32.083Z
I did not read that paper, but it seems that the author are designing secure e-voting systems. Isn't that an application of **cryptography** to security systems? Note that the OP asks for applications of hard problems to fields **other** than cryptography.
Sadeq Dousti
CC BY-SA 2.5
2010-11-15T17:50:42.247Z
No that's not quite right. They are looking at the mathematics of voting systems and trying to understand how the perspective of complexity theory changes design choices. For example, among three schemes that look similar, one is NP-hard to hack and the others aren't. It's a **computational** view on social choice theory, much like modern crypto gives a **computational** perspective on encoding secrets.
Suresh Venkat
CC BY-SA 2.5
2010-11-15T04:01:00.487Z
2010-11-15T04:01:00.487Z
Suresh Venkat
<p>Complexity theory seems to capture something fundamental about the
structure of the universe, in that it formalizes the intuitive notion
that some problems are harder than others.</p>

<p>Scott Aaronson <a href="http://www.scottaaronson.com/talks/colloq2.ppt">predicted</a>, "The NP Hardness Assumption will eventually be
seen as analogous to the Second Law of Thermodynamics or impossibility
of superluminal signaling."</p>

<p>So-called "hard problems" are the basis of modern cryptography.</p>

<p>Are there any <strong>other</strong> applications that utilize, depend on, or exemplify the
existence of computationally hard problems?</p>

<cc.complexity-theory><soft-question><big-picture>
Applications of Complexity Theory
rphv
# Applications of Complexity Theory

(Asked by: username_0 on 2010-11-15)

Complexity theory seems to capture something fundamental about the
structure of the universe, in that it formalizes the intuitive notion
that some problems are harder than others.

Scott Aaronson [predicted](http://www.scottaaronson.com/talks/colloq2.ppt), "The NP Hardness Assumption will eventually be
seen as analogous to the Second Law of Thermodynamics or impossibility
of superluminal signaling."

So-called "hard problems" are the basis of modern cryptography.

Are there any **other** applications that utilize, depend on, or exemplify the
existence of computationally hard problems?

**Tags:** cc.complexity-theory, soft-question, big-picture

---

## 4 answers

### Answer by username_4 on 2010-11-15. Score: 15 | Accepted answer

The most recent issue of the CACM has an [article by Faliszewski, Hemaspaandra and Hemaspaandra](http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext) on the use of complexity theory in the realm of social choice theory and election design in particular. One example of such a result is that while Arrow's theorem guarantees that any election system is 'hackable', it might be NP-hard to do so.

> **Comments:**
> **username_5**: I did not read that paper, but it seems that the author are designing secure e-voting systems. Isn't that an application of **cryptography** to security systems? Note that the OP asks for applications of hard problems to fields **other** than cryptography.  
> **username_4**: No that's not quite right. They are looking at the mathematics of voting systems and trying to understand how the perspective of complexity theory changes design choices. For example, among three schemes that look similar, one is NP-hard to hack and the others aren't. It's a **computational** view on social choice theory, much like modern crypto gives a **computational** perspective on encoding secrets.  

---

### Answer by username_1 on 2010-11-15. Score: 8

This [2009 survey by Daskalakis](http://people.csail.mit.edu/costis/reconstruct.pdf) surveys the complexity of computing Nash equilibria. His previous work with Goldberg and Papadimitriou demonstrated that exactly computing such equilibria is PPAD-complete. This is not as strong a statement as if the problem were NP-hard, but still provides evidence that computing Nash equilibria is intractable, throwing into doubt the predictive power of Nash equilibria. One salvation would be to demonstrate a PTAS for $\epsilon$-Nash equilibria for desired accuracy $\epsilon$. But the current best is an non-oblivious approximation algorithm that runs in time quasipolynomial in $1/\epsilon$.

> **Comments:**
> **username_1**: An aside: Cryptography is obviously a *positive* application of a computationally hard problem. This would be an example of an application of a complexity theorem outside of the complexity field that is *negative*. Are you particularly interested in one over the other, @rphv?  
> **username_0**: I'm interested in both positive and negative applications. If the existence of computationally hard problems is analogous to 2LOT or C, then I feel like we should be bumping in to examples/consequences of it often, much as we often encounter real-world objects that 'embody' those properties (car engines, electricity, etc.) Even if we don't "get anything" (like crypto) out of the fact that hard problems exist, I think it might be useful to consider the existence of hard problems when thinking about the world.  In other words, "How does the existence of hard problems affect our lives?"  

---

### Answer by username_2 on 2010-11-15. Score: 4

To add to Dana's answer which basically says hardness can be converted into randomness. The existence of hard functions with exponential circuit complexity lower bound can be used to efficiently derandomize every probabilistic algorithm in $BPP$. This would imply $P=BPP$.


---

### Answer by username_3 on 2010-11-15. Score: 2

Assuming "hard" functions exist (for a variety of definitions of "hard"), we can construct pseudorandom generators.


---

