NP-complexity for Dummies (like me)

Despite all the computational theory that I have studied over the years, the definitions of P, NP, NP-hard, and NP-complete have always been fuzzy in my mind. But I think I’m finally getting the hang of it, and I want to write it out (in overly-simplistic language) before I forget (again)!

P-problems are those that can be solved in Polynomial time. That doesn’t mean they’re easy, necessarily – they may be O(n^2), or even O(n^Googol), but they’re do-able.

Then there are the other problems. The hard ones. The ones (for example) that take an exponential amount of time to solve – like cracking passwords with brute force.

There are a lot of these hard problems that nobody has ever found a polynomial-time algorithm for. Doesn’t mean one doesn’t exist, it just hasn’t yet been discovered. Now some of these problems have a particular characteristic that, although they can’t be solved quickly (yet), they can at least be verified quickly. That means that if some wizard said, “Here’s the answer to this particular problem”, you could quickly do some math and say, “Yep. He’s correct. That’s the answer all right.” (It might take magic to solve your password, but I can check one of my guesses instantaneously.)

Problems of this sort (with easy-to-test answers) are known as NP. (Important note: “NP” does not stand for “Non-Polynomial”. As a matter of fact, all P problems are by necessity also NP – they have easy-to-test answers. NP actually stands for Non-deterministic Polynomial, for reasons that aren’t really necessary to understand.)

OK, so now we have this set of NP problems (which includes all the P problems, and many others that may or may not be in P, but appear so hard that we doubt they are in P). Now it just so happens that some brainy dudes started studying all these NP problems that seemed outside of P, and they noticed a curious detail about them: They all turn out to be “equivalently” hard. (That statement is not precisely accurate, but I’ll clarify shortly.) So, for all of these problems (even the really-really hard ones that would take a billion eons to solve with current algorithms), it turns out that if you can find a way to solve any one of them quickly, you could solve all of them quickly! If you find a key that unlocks one of them, that key can be used to unlock all of them! So, the brainiacs have given this quirky set of quasi-equivalent problems a special name: they call them NP-complete. Technically put: any problem in NP can be “reduced” to any problem in NP-Complete; therefore, this set is equivalent to the hardest problems in NP.

There is another class of problems that are even “harder” than NP-complete. They are the ones that are outside of NP altogether (in other words, even their answers are not easily verifiable). However, even some of these (or perhaps all of them; I’m not clear on this part yet) can be mapped or “reduced” to the NP-complete problems. These are called the NP-hard problems. That is: they’re not in NP, but they are technically no harder than the ones that are.

SOOO, if someone wakes up tomorrow and discovers an efficient (polynomial time) solution to just one of the NP-complete problems, the entire fortress of NP-complete problems will collapse and they will all be “solved” (or, rather, “solvable”). So you say, “well of course, that’s impossible; that could never happen.” And you’d probably be right. But here’s the thing: NO ONE HAS EVERY PROVEN THAT TO BE TRUE! Despite decades of trying by the brightest of the bright, and a $1 million dollar reward. You could also win the $1million by proving that even ONE of the NP-complete problems is for sure NOT in P, but nobody has been able to do that either.

So what are you waiting for? Get busy! Go out there and win a million dollars!

Posted in Uncategorized | Leave a comment

Using Outlook Emails for ToDo lists

Here’s a simple productivity tip that I came up with recently…

At work I basically live in Outlook, so I’m not interested in introducing another application to handle my “ToDo” list. However, I’ve never been particularly fond of the Task List that Outlook provides. So I’ve come up with a simpler approach: On Friday afternoons, I email myself a list of the things I want to accomplish the following week.

One thing that this approach misses, however, is a convenient way to “check off” the individual tasks. So I set up a simple way to do this with a few easy clicks, using built-in features in Outlook. My customization makes use of the AutoCorrect feature.

1. First, I entered the following two AutoCorrect entries:

  – Two square brackets (“[]”) get replaced with an empty box.

  – Right-bracket + backslash (“]\”) get replaced with a “checked” box.

2. So now, if I type brackets+tab, I get a checkbox. (By pressing tab rather than spacebar, the checkbox is transformed into a list bullet, so subsequent lines automatically get added to the checklist with their own checkbox.)

3. To check off an item, click on the item, hit Home twice, then type R-Bracket + slash + tab (which sounds complicated, but it only requires a simple roll of the fingers; you don’t even have to hit Delete). Note: Since the items are now list items, hitting Home twice will display formatting that makes it look like your change will apply to the whole list, but only the box with the cursor will get “checked off”.


If you haven’t used customized Autocorrect entries before, here’s the step-by-step instructions for setting one up in Outlook 2013 (instructions work in earlier versions too):

1. In an email, use Insert->Symbol, to select and enter the symbol you want to use. (I chose Wingdings, character 168 for the empty box.)

2. Now in the email, select the symbol you just added. Then open the Autocorrect feature by navigating here:

         FILE -> Options -> Spelling and AutoCorrect… (button) -> AutoCorrect Options… (button)

3. Now notice that the symbol you selected in step 2, has been automatically placed in the “With” field, and the radio button should default to “Formatted Text”. In the “Replace” field, type the characters that you want to use to trigger the action (open & close square brackets, in my case). Hit the “Add” button, and then OK.

4. Repeat these steps for the marked checkbox. (I use Wingdings, character 254.)

5. One last thing I have to do before using this method: Since I have emailed this list to myself, it is not automatically editable. To make it so I can check the boxes off, I must open the email in its own window (not in the Reading Pane), then in the MESSAGE tab I click Actions -> “Edit Message”.

And now, voilà! you have a very convenient way of making and using ToDo list checkboxes in emails. Here’s a snippet from my morning list:

Now I can go check off that second box. (I love checking off boxes!)

Posted in Uncategorized | Leave a comment

Resume Tips (Not that I am Preparing One at the Moment)

Just read this helpful suggestion from Yvan Rodrigues over in CodeProject. I particularly like his description of a “skills grid”:

My resume is 13 pages. As ridiculous as that sounds, I get a very high interview rate and usually before I show up they know if they want me or not. I did it that way because I have been a hiring manager for many positions and you have so little to go on from a 1 page resume and cover letter. With mine, what they see is what they get. I use a skills grid to indicate my level of knowledge for various technologies using this key:

Basic knowledge: I have researched this topic; or I haven’t used this technology, but I’d like an opportunity to; or I have used this for less than 6 months; or I could discuss it at a cocktail party.
Applied knowledge: I have used this in one or more projects; or I have used this for less than 2 years.
Advanced knowledge: I use this regularly in projects; or I have been using this for 2–5 years; or with some preparation, I would feel comfortable speaking about this topic to a general audience.
Expert knowledge: This is a core technology in my projects; or I have been using this for 5+ years; or I have written or spoken to this topic; or with some preparation, I would feel comfortable speaking about this to an audience of my peers.

While I think a thirteen page resume is excessive*, Yvan’s Skills’ Key seems useful. I have used used a Skills Grid myself for years, but I just liked his wording, so I am preserving it here as a reference, in case I need to re-do my resume someday.

*Personally, I pride myself on maintaining a dense ONE-page resume. It requires exacting discipline to strip out every un-necessary word in order to keep it short and concise. But I try to treat my resume exactly like an elevator speech: Make every syllable count. (Unlike my blog, which conforms more to the Pascalian adage, “I would have written a shorter post, but I didn’t have the time.”)

Posted in Uncategorized | Leave a comment

Visual Studio 2014: A Taste of Things to Come…

While I’m not ready to jump ship from VS2012 just yet, the just-released VS2014 CTP3 has some pretty cool features (Expand the DetailsgTechnology Improvements items on that page). Some highlights*:

· Custom Layouts to make it easy for you to save custom layouts. In CTP 3, these Custom Layouts roam: any custom layouts you create will synchronize across machines that have the CTP 3 installed when you sign into the IDE with the same account.

· “PerfTips” – now see how long code took to execute directly in the editor when code execution exceeds a threshold. (More details here).

· “Lightbulbs” – If you have an issue in your code, placing your editor caret on the line where the issue is shown or hovering over the issue will present a light bulb that shows helpful actions you can take to resolve the problem together with a preview of the results of each action.

· C# refactoring support has been completely revamped. There are two new core refactorings: Inline Temporary Variable and Introduce Explaining Variable. Additionally, refactoring support for Visual Basic has been added for the first time.

* Note: Some of these features are from earlier releases of VS2014 (i.e., CTP1 & CTP2).

Posted in Uncategorized | Leave a comment

Forecasting for IEEE


IEEE Spectrum invited me to contribute to their “Survey of the Future”, prognosticating what I expect the future will look like technologically over the next two decades. For the record, here are my predictions:

In 10 years:

Ubiquitous computing: internet of Things + cloud + wearables = SMOG. (“sensory manipulation overload grief”)

In 20 years:

Implantables: digital tatoos; optic-/aural-nerve interfaces; natural language interfaces


Over the next 10-20 years:

  1. Desktop workstations will be disappear, along with:
  2. The “internet” (as we now know it). It will no longer refer to a collection of websites; websites will no longer be monolithic, static “destinations”; the data (images, text, media) currently housed in individual websites will coalesce into an amorphous “Sea” of information (navigated, perhaps, by semi-intelligent virtual-guides). We will access this Sea via:
  3. Wearables: glasses/contacts will provide hi-def 3D VR screens; nano-sized wireless ear-buds will be “tatooed” in the ear canal. We will interact with these interfaces via:
  4. Natural language (i.e., conversational interfaces; including inaudible voice recognition through direct vocal muscle detection). People won’t be talking to “the computer”; they will be conversing directly with the Sea. Early adopters will be experimenting with:
  5. Implantables: digital tattoos and neural implants allowing thought-driven interfaces (primitive at first), and direct-sensory stimulators (“sharable emotions”). All of these innovations will give rise to:
  6. Virtual Presence: the ability to interact with anybody instantaneously, in 3D VR environments.

Other changes to expect by 2040:

  1. Drones will be as ubiquitous as cars.
  2. Passwords will be obsolete, along with email, Facebook, and Google.
  3. Shopping centers will vanish, replaced by holographic VR-shopping, automated drone delivery, and nano-scale 3D printers.
  4. Offices and school buildings will empty out, deemed unnecessary with the rise of “virtual presence”.
  5. Clubs, gyms, churches, and bars will increase in popularity, satisfying people’s continuing need to connect, exercise and fellowship.
Posted in Uncategorized | Leave a comment

Hidden Brain Stuff

In a recent Vanderbilt study, researchers determined that we might not know what we think we know. Or perhaps we know what we don’t really know. Or something like that. Anyways, here’s the case in point: even though you may be a skilled typist, you probably can’t label more than about 17 keys on a blank keyboard in under 80 seconds. Here’s a blank keyboard to test yourself with. Print it out and give it a try:

(Personally, I got 19 correct, and my bottom row was basically all off by one letter. BUT, I could only do it by actually fake-typing on the page; I’m not sure if that’s cheating.)

Try it and tell me how you did!

Posted in Uncategorized | Leave a comment

Just A Little Visual Studio Time Saver

If you use the Visual Studio wizard for the UnitTest framework, you’ll find your test code littered with these helpful reminders:

// TODO: Initialize to an appropriate value

And by “littered” I mean there are hundreds, if not thousands, of these comments cluttering your code – several on every test method. I quickly tired of manually removing them one by one, but they are useful reminders so I don’t want to do a global search-and-delete. Instead, I wrote a macro to to make it a one-click job. Unfortunately, this will only work on VS2010 or earlier, since the Microsoft boys decided to remove macros from 2012 & 2013. :(

Here’s the script:

Sub Delete_TODO_Text()
  'save the current location, to return here if text not found
  Dim objActive As VirtualPoint = DTE.ActiveDocument.Selection.ActivePoint
  Dim iCol As Integer = objActive.DisplayColumn
  Dim iLine As Integer = objActive.Line

  'search for text on current line only
  DTE.Find.FindWhat = "// TODO: Initialize to an appropriate value"
  DTE.Find.Action = vsFindAction.vsFindActionFind
  DTE.Find.Target = vsFindTarget.vsFindTargetCurrentDocumentSelection
  If (DTE.Find.Execute() = vsFindResult.vsFindResultNotFound) Then
    DTE.ActiveDocument.Selection.MoveTo(iLine, iCol, False) 'return to original position
  End If
End Sub

After adding the script to a module in MyMacros, I assigned it to a keyboard shortcut. Now all I have to do is navigate to each line on which the comment appears, initialize the corresponding object appropriately, then click my keyboard shortcut to activate the macro, deleting the comment from the end of the line. (The macro has some additional logic to avoid any side-effects if I accidentally activate it while on a line that doesn’t contain the comment. I had to do some selection trickery to search for the comment text only on the current line.)

Posted in Uncategorized | Leave a comment