Sherlock Holmes and Hard Problems

“With a few simple lines of computer code,” boasts Moriarty in BBC Sherlock, “I can crack any bank, open any door”. (Paraphrased from memory, shh.) Without any spoilers, I can tell you that Sherlock’s nemesis is portrayed as controlling every detail, forseeing every possibility, and manipulating a web of individuals through blackmail, bribery, snipers, and sowing distrust. And, he makes vague claims of having the ultimate computer hack, stronger than any security system.

What kind of software would this be? Most of computer security relies on mathematics that is computationally hard. Consider a traditional padlock. If you know the combination, it takes almost no time to open the lock. If you don’t know the combination, you have to try every possible code. The combination is easy to check, but difficult to discover.

A completely general computer hack of the sorts Moriarty claims to have would be like being able to open a padlock without the combination as fast as you could with the combination. Sherlock operates in much the same way. Anyone can verify his string of deductions after he’s made them; his genius is to devise them in the first place.

So that’s what separates fact from fiction. These portrayals of genius are unrealistic because they take the same amount of time to produce a solution as it takes to verify one. Right?

Not quite. “Can any answer than can be checked quickly also be created quickly?” is one of the great unsolved problems of computer science. We don’t know.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: