This problem is among the class of notoriously difficult problems that are called

- Time complexities such as

are called ~~O~~(2^{n}),~~O~~(3^{n}),~~O~~(n!)exponential.

- Actually,
n!is asymptotically larger than anyc, where^{n}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-completeand that are believed to beintractable.NP = "Nondeterministic Polynomial"

CS1104 Main Page

Last Updated 01/05/2000

© L.Heath, 2000