The Algorithms versus Complexity Duality



The Algorithms versus Complexity Duality

Algorithms Research: design new approaches to solve computing problems.

Computational Complexity Theory: prove no good algorithms exist.

The two efforts complement and inform each other.


As computing architectures evolve, or applications and data models change, both areas adapt to them. Thus they are living sciences.

Classical examples: NP-completeness and PSPACE-completeness (explain difficulty of combinatorial search and the difficulty of finding good strategies in games).

But algorithms and complexity have evolved to meet challenges in every aspect of computing: data streaming, algorithms that compute approximate solutions (and its associated complexity theory), online computation, strategic interactions, etc.

Trying to prove that algorithms for certain tasks (in whatever model) do not exist is an important complement to design of algorithms, and often provides valuable insights into the problem. For instance, the potentially exponential speedup of quantum computing over standard computing (Shor’s algorithm) was discovered as part of the process of trying to prove lowerbounds.

Another area with close connection between algorithms and complexity is the study of approximability of NP-hard optimization problems. The process of discovering new algorithms and that of showing (assuming P \neq NP) the nonexistence of algorithms has gone hand in hand in the past 15 years.

Contributors and Credits

Luca Trevisan, Valentine Kabanets,  Avi Wigderson, Leonid Levin, Sanjeev Arora.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: