This problem is among the class of notoriously difficult problems that are called NP-complete and that are believed to be intractable.
- Time complexities such as
are called exponential. O(2n), O(3n), O(n!)
- Actually, n! is asymptotically larger than any cn, where c >1 is a constant.
- Exponential time algorithms are very inefficient.
- We do not know any algorithm that is not exponential time for the Hamiltonian circuit problem.
NP = "Nondeterministic Polynomial"
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000