Graph three-coloring has been shown to be in a class of problems known as NP-Complete. In a nutshell, NP-Complete problems are considered the hardest problems in the class of non-deterministically solvable problems given the constraint of polynomial time. [1] In essence, these problems cannot be solved by a deterministic computer (such as all current computer models based on a Turing-machine) in less than exponential time. Another interesting fact about all NP-Complete problems is that every problem in this class can be mapped to any other in polynomial time. This implies that if a polynomial time algorithm were found for a single problem in this class, we could then find a polynomial time algorithm for all problems in this class. As of current research, there is no proof showing that a polynomial time algorithm does or does not exist for these problems. [1]


Some Examples of NP-Complete Problems:

  • Integer partitioning
    • Partition N integers into two subsets such that the sum of each subset is equal.
  • Bin packing
    • How many bins of a given size are needed to hold N items of variable size.
  • Chromatic number
    • Find the minimum number of colors needed to properly vertex-color a graph.


What is Grid Computing?



1. Garey, Michael A. and Johnson, David S. Computers and Intractability. 1979.