How much can you achieve in a century?!

I’ve always wondered how bad could an exponential-time algorithm be? Why are polynomial-time algorithms usually considered tractable compared to exponential- and factorial-time ones? I was recently reviewing Introduction to Algorithms when I came across the only problem in Chapter 1. It asks for the largest size n of a problem that can be solved in unit time by an algorithm that takes f(n) microseconds to run, where a unit of time could be a second, a minute, and so on. Here are the numbers I got:

1 second 1 minute 1 hour 1 day 1 month
lg~n 2^{10^6} 2^{6\times10^7} 2^{3.6\times10^9} 2^{8.64\times10^{10}} 2^{2.592\times10^{12}}
\sqrt{n} 10^{12} 3.6\times10^{15} 1.296\times10^{19} 7.46496\times10^{21} 6.718464\times10^{24}
n 10^6 6\times10^7 3.6\times10^9 8.64\times10^{10} 2.592\times10^{12}
n~lg~n 62746 2801417 133378058 2755147513 71870856404
n^2 1000 7745 60000 293938 1609968
n^3 100 391 1532 4420 13736
2^n 19 25 31 36 41
n! 9 11 12 13 15
1 year 1 century
lg~n 2^{3.1104\times10^{13}} 2^{3.1104\times10^{15}}
\sqrt{n} 9.67458816\times10^{26} 9.67458816\times10^{30}
n 3.1104\times10^{13} 3.1104\times10^{15}
n~lg~n 787089606198 67699498463641
n^2 5577096 55770960
n^3 31448 145972
2^n 44 51
n! 16 17

A picture is worth a thousand words! It’s always useful seeing the numbers than hearing stories about how slow an exponential-time algorithm could be.

This also illustrates how interesting NP-complete problems are. The fact that these seemingly simple problems are exponentially hard and that finding an efficient solution to one of them gives a solution to them all, makes them the most exciting riddles in the history of computer science. What’s more exciting is that while many researchers believe no efficient solution exists for this class of problems, no one has ever been able to prove it! This also reveals why P vs. NP was chosen to be the first of Clay Institue’s seven problems of the millennium.


Leave a Reply

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

You are commenting using your 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