Subscribe / Unsubscribe Enewsletters | Login | Register

Pencil Banner

The 7 most vexing problems in programming

Peter Wayner | Nov. 8, 2016
Here be dragons: These gnarly corners of the coding world can be formidable foes, even for seasoned pros


Anyone with a university education in computer science knows of the mysterious problems wrapped in an acronym that’s rarely spelled out: nondeterministic polynomial complete, aka NP-complete. The details often take an entire semester to learn, and even then, many CS students come out with a foggy notion that no one can solve these problems because they’re too hard.

The NP-complete problems often are quite difficult—if you attack them simply with brute force. The “traveling salesman problem,” for example, can take an exponentially long time as the sales route includes more and more cities. Solving a “knapsack problem” by finding a subset of numbers that come the closest to some value N are solved by trying all possible subsets, which is a very big number. Everyone runs with fear from these problems because they’re the perfect example of one of the biggest bogeymen in Silicon Valley: algorithms that won’t scale.

The tricky part is that some NP-complete problems are easy to solve with an approximation. The algorithms don’t promise the exact solution, but they come pretty close. They may not find the perfect route for the traveling salesman, but they can come within a few percentage points of the right answer.

The existence of these pretty good solutions only make the dragons more mysterious. No one can be sure if the problems are truly hard or easy enough if you’re willing to be satisfied by an answer that’s just good enough.


“There are known knowns; there are things we know we know,” Donald Rumsfeld, the Secretary of Defense during the second Bush administration, once said at a press conference. “We also know there are known unknowns; that is to say we know there are some things we do not know. But there are also unknown unknowns—the ones we don’t know we don’t know.”

Rumsfeld was talking about the war in Iraq, but the same holds true for computer security. The biggest problems are holes that we don’t even know are possible. Everyone understands that you should make your password hard to guess—that’s a known known. But who has ever been told that your networking hardware has its own software layer buried inside? The possibility that someone could skip hacking your OS and instead target this secret layer is an unknown unknown.

The possibility of that kind of hack may not be unknown to you now, but what if there are others? We have no clue if we can harden the holes we don’t even know exist. You can batten down the passwords, but there are cracks you can’t even imagine. That’s the fun of working with computer security. And when it comes to programming, security-minded thinking is becoming ever more important. You can’t leave it to the security pros to clean up your mess.


Previous Page  1  2  3  4  Next Page 

Sign up for CIO Asia eNewsletters.