On Computational Complexity (letter to CACM editor)

by Oded Goldreich

Following is a draft of my letter to the CACM editor, written in respond to a CACM editorial (November 2010).

I welcome any attempt to explain the contents of computational complexity to the general readership of CACM. Yet I fear that Moshe Vardi's last editorial (November 2010) provides a somewhat partial perspective, and I wish to augment it with a few comments.

In general, the goal of computational complexity is to explore the potential and limitation of efficient computation. While the P-vs-NP Question is a central pivot of that attempt, computational complexity is not reduced to it. Nevertheless, I'll confine my comments to the P-vs-NP Question.

As Moshe explained, the P-vs-NP Question refers to the relative difficulty of finding solutions to computational problems in comparison to checking the correctness of solutions to these very problems. Moshe mentions that common sense suggests that finding solutions is harder than verifying their correctness, and that it is indeed widely believed that P is different from NP. He advocates the study of the P-vs-NP Question by saying that knowing is different from believing, and warning that it is sometimes the case that beliefs are wrong.

All this is indeed true, but one should add that the ability to prove a central result (like P is different from NP) is connected to obtaining a much deeper understanding of the main issues that are at the core of a field. Thus, a proof that P is different from NP is most likely to lead to a better understanding of the possibilities and limitations of efficient computations, whereas such a theoretical understanding is bound to have a huge impact on computer practice: It will guide practical problem solving by suggesting ways to formulate (and possibly relax) practical problems such that they can be solved efficiently. Furthermore, even ideas developed along the way (i.e., in attempt to address the P-vs-NP Question) have had an impact on computer practice (e.g., see SAT-solvers).

The foregoing discussion does not dispute the claim that there is a gap between theory and practice: Theory is not supposed to replace practice but rather inform it. One should not underestimate the value of good advice (i.e., good theory), neither should one overestimate it. Real life problems are solved in practice, but good practice benefits a great deal from a good theory.

One should also realize that the specific formulation of the P-vs-NP Question (in terms of polynomial running time) is merely the simplest formulation of a more abstract question. Ditto with respect to the focus on worst-case complexity. In both cases, the current formulation should be viewed as a first approximation, and it makes sense to study and understand this first approximation before moving forward.

Unfortunately, we currently lack good theoretical answers to most natural questions regarding efficient computation. This is the case not becuase we ask the wrong questions, but rather because these questions are very hard. We will never get answers if we do not start studying these questions, as we have done for the last few decades. While our current understanding is very limited in comparison to the aforementioned questions, we made a significant progress in comparison to what we knew 3-4 decades ago. Furthermore, this theoretical progress has had an impact on computer practice (e.g., see Cryptography).

It makes sense that most of Computer Science deals with actually doing the best we can do right now (i.e., develop the best computational tools given our current understanding of efficient computation), rather than waiting for sufficient progress on the aforementioned ambitious project. It also makes sense that part of Theoretical Computer Science will help in meeting today's challenges (which it does!). But it crucial for part of TCS (i.e., complexity theory) to devote itself to the project of understanding the possibilities and limitations of efficient computation.

Back to Oded's page of essays and opinions or to Oded's homepage.