letters to the editor
DOI: 10.1145/1897816.1897818
shine the Light of computational complexity

Regarding Moshe Y. Vardi’s view of computational complexity in his Edi- tor’s Letter “On P, NP, and Computational Complexity” (Nov. 2010), I’d like to add that the goal of computational complexity is to explore the potential and limitation of efficient computation. While P vs. NP

is a central pivot in that direction, computational complexity is not reduced to it exclusively; nevertheless, my comments are limited to P vs. NP.

P vs. NP refers to the relative difficulty of finding solutions to computational problems in comparison to checking the correctness of solutions to these problems. Common sense suggests that finding solutions is more difficult than checking their correctness, and it is widely believed that P is different from NP. Vardi advocated the study of P vs. NP, saying that knowing is different from believing and warning that beliefs are sometimes wrong.

The ability to prove a central result is connected to obtaining a much-deeper understanding of the main issues 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 efficient computation, and such a theoretical understanding is bound to have a significant effect on computer practice. Furthermore, even ideas developed along the way, attempting to address P vs. NP, influence computer practice; see, for example, SAT solvers.

This does not dispute the claim that there is a gap between theory and practice; theory is not supposed to replace but rather inform practice. One should not underestimate the value of good advice or good theory; neither should one overestimate it. Real-life problems are solved in practice, but good practice benefits greatly from good theory.

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

Hold manufacturers Liable

In his Viewpoint “Why Isn’t Cyberspace More Secure?” (Nov. 2010), Joel F. Brenner erroneously dismissed the value of making software manufacturers liable for defects, with this misdirected statement: “Deciding what level of imperfection is acceptable is not a task you want your Congressional representative to perform.” But Congress doesn’t generally make such decisions for non-software goods. The general concept of “merchantability and fitness for a given application” applies to all other goods sold and likewise should be applied to software; the courts are available to resolve any dispute over whether an acceptable level of fitness has indeed been met.

In no other commercial realm do
we tolerate the incredible level of un-
reliability and insecurity character-
istic of today’s consumer software;

Author’s Response:

The challenge is in writing standards that would improve security without destroying creativity. “Basic good engineering” is not a standard. A “merchantability and fitness” standard works for, say, lawnmowers, where everyone knows what a defect looks like. It doesn’t work for software because defining “defect” is so difficult, and the stuff being written is flying off the shelves; that is, it’s merchantable. It’s also sold pursuant to enforceable contracts. So while courts are indeed available to resolve disputes, they usually decide them in favor of the manufacturer. Deutsch and I both want to see more secure and reliable software, but, like it or not, progress in that direction won’t be coming from Congress.

Joel f. Brenner, Washington, D.C.

 

code syntax is understanding In his article “Sir, Please Step Away from the ASR- 33!” (Nov. 2010), Pohl-Henning Kamp was deliberately provocative regarding programming language syntax, but his arguments were confused and off the mark. To call attention to new directions available to language designers, he focused on syntax, and surprisingly, complained about the “straightjacket” imposed by ASCII but also made a good point regarding the importance of “ expressing our intentions clearly.” Still, he distorted the role of “syntax,” which involves critical goals beside “ expressivity,” including machine interpretation, amenability to formal analysis, efficiency (in many dimensions), and