That's the first question popped up in my mind when I first heard the word. It was kind of scary a bit that I didn't know the meaning of the word and thought that all other students knew.
To understand it let's take the word apart.
It all starts with a "P" . Any problem that is solvable in worst case polynomial time (n, n^2, n^3,..., where n is the size of input) is called "P" or "Polynomial." So you might guess - Aha, NP must be non-polynomial time. If you do (I did), I am sorry to disappoint you that "NP" is actually "Nondeterministically Polynomial."
Why nondeterministic?
NP is a superset of P. Sometimes NP problem can be solved very quickly. But sometimes it can't. If there is even one case that requires exponential time, it falls from P into NP. How do we know if there is a case that requires exponential time? Well..., we don't - unless we stumble into one. If we don't but we can prove that we are able to verify a solution within polynomial time, then in this case we can't be sure if we can solve the problem in polynomial time or exponential time.
What about NPC then?
What's the deal with it anyway?
It is important to know that NPC problems usually looks like very simple problems that could be solved quickly. For NPC problems, they are not as simple as they look. Normally when we try to optimize our algorithm, we check the upper bound on running time first. Try to lower the upper bound. But if after a while and we cannot lower the upper bound, you might consider finding the lower bound and check if the problem is NPC or not. If it is, sorry folks! No can do in polynomial time (at least not yet).
| Size n | ||||||
| Complexity | 10 | 20 | 30 | 40 | 50 | 60 |
| n | .00001 s | .00002 s | .00003 s | .00004 s | .00005 s | .00006 s |
| n2 | .0001 s | .0004 s | .0009 s | .0016 s | .0025 s | .0036 s |
| n3 | .001 s | .008 s | .027 s | .064 s | .125 s | .216 s |
| n5 | .1 s | 3.2 s | 24.3 s | 1.7 min | 5.2 min | 13.0 min |
| 2n | .001 s | 1.0 s | 17.9 min | 12.7 days | 35.7 years | 366 centuries |
| 3n | .059 s | 58 min | 6.5 years | 3855 centuries | 2x108 centuries | |
3-Coloring problem
3-Coloring problem is one of the NPC problems. It can be solved only by bruteforce which requires exponential time. The problem looks very simple. We are given a graph which has nodes and edges. Any two nodes that has an edge connected to each other cannot have the same color. Try to find the right color for each node.
I wrote a simple program to solve the problem that I got. I am quite certain that if there is a technique to solve NPC in polynomial time. It won't be an algorithm but Math.