19

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, "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?

rphv
  • 583
  • 3
  • 11

4 Answers4

15

The most recent issue of the CACM has an article by Faliszewski, Hemaspaandra and Hemaspaandra 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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 1
    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 Nov 15 '10 at 10:13
  • 2
    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 Nov 15 '10 at 17:50
8

This 2009 survey by Daskalakis 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$.

Daniel Apon
  • 6,001
  • 1
  • 37
  • 53
  • 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 Nov 15 '10 at 11:51
  • 1
    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 Nov 16 '10 at 05:59
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$.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
2

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

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77