Heading

Complexity theory is a central topic in theoretical computer science. It has direct applications to computability theory and uses computation models such as Turing machines to help test complexity. Complexity theory helps computer scientists relate and group problems together into complexity classes. Sometimes, if one problem can be solved, it opens a way to solve other problems in its complexity class. Complexity helps determine the difficulty of a problem, often measured by how much time and space (memory) it takes to solve a particular problem. For example, some problems can be solved in polynomial amounts of time and others take exponential amounts of time, with respect to the input size.

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected)

Class P If a problem can be solved by a deterministic Turing machine in polynomial time, the problem belongs to the complexity class P. All problems in this class have a solution whose time requirement is a polynom on the input size n. i.e. f(n) is of form akn k +ak−1n k−1 +...+a2n 2 +a1n+a0 where ak, ..., a0 are contant factors (possibly 0). The order of polynom is the largest exponent k such that ak = 0 (if ak = 0, then the polynom is ak−1n k−1+...+a0 and the order is k − 1, unless ak−1 = 0. If ak−1 = 0, too, then the polynom is ak−2n k−2 + ... + a0 etc.).

Class NP contains all computational problems such that the corresponding decision problem can be solved in a polynomial time by a nondeterministic Turing machine.

NP-complete problems

NP-complete problems are special problems in class NP. I.e. they are a subset of class NP. An problem p is NP-complete, if

1. p ∈ NP (you can solve it in polynomial time by a non-deterministic Turing machine) and

2. All other problems in class NP can be reduced to problem p in polynomial time.