Hard Problem - What exactly is a Hard Problem?

Imagine the following statements hold true:

• There exist 10¹¹⁰ molecules in the universe.

• The fastest single core computer can perform 1 trillion (10¹²) operations per second.

• The universe has been in existence for 1 trillion (10¹²) years.

To most scientists, these are extreme overestimates. But we overestimate for a reason! Let every single molecule in the universe be capable of acting as a computer that can perform 1 trillion operations per second. In addition, let us run these computers on a single problem for the life of the universe.

• (10¹¹⁰) molecules * (10¹²) ops per second * 3.2 * (10⁷) seconds per year * (10¹²) years = 3.2 * (10¹⁴¹) computer operations.

So, it is pretty safe to say that any problem that requires more than (10¹⁴¹) operations to solve is a Hard Problem. Hard problems are also NP-complete.

Hard Problem - Example
There are many Hard Problems, believe it or not! Check out the Wikipedia entry for NP-complete - you'll find a lot! A couple of the easiest to understand are as follows:

Traveling Salesperson
Imagine a salesman has to visit 5 cities to sell stuff. He wants to visit each city only once, and he desires the shortest possible route through all 5 cities and back to the first. There are 5! = 5 * 4 * 3 * 2 * 1 = 120 possible combinations. It would be fairly trivial to write a program to search through all 120 possible routes for the quickest route, but things get complicated fast as we increase the number of cities. At 92 cities, the Traveling Salesperson (TS-92) problem becomes Hard: 92! = 1.24 * (10¹⁴²). So, a brute force search algorithm would have to examine an impossible amount of routes in the TS-92 problem.... what about TS-920, or TS-20,000? Any algorithm even remotely resembling brute force won't ever come close.

Hard Problem - Example

Bin Packing Algorithm
In this problem we have containers and some objects that need to be placed in the containers. In the problem's simplest form, each object has an integer that represents its size. The goal is to place every object in a container - but to use the fewest number of containers possible. For example, let's say the container size is 5, and the first two objects placed within it have sizes of 1 and 3... so the container has only 1 left. That doesn't bode well if we have no more objects of size one! If that's the case, then we just wasted 20% of the first container. This problem becomes Hard very quickly as the number of objects to be placed increases!

Real Life Examples:
Fed-Ex & UPS Package Routing
Airline Scheduling
Grocery Store Distribution
Newspaper Delivery