Introduction to Complexity Theory/Time Complexity

Time complexity is the number of steps that it takes to solve a problem in relationship to the size of the input, and is represented using big O notation.

Complexity Classes

The concept of complexity classes helps us group problems according to the way in which the are solved. Complexity classes have a complex and ill-understood relationship amongst each other.

One type of time complexity class is DTIME (sometimes refered to as TIME), a complexity class that describes the computational time of a problem on a deterministic Turing machine. All complexity classes that are based around the concept of time complexity on a deterministic Turing machine may be defined in terms of this class.

Another type of time complexity class is the non-deterministic analogue of DTIME, NTIME. The relationship between these two classes is not fully understood.

Polynomial Time

The computational time of a problem that is solvable in polynomial time on a given Turing machine is referred to as polynomial time.

The time complexity on a given Turing machine is polynomial if it is $O\left(n^{k}\right)$ for any $k\in \mathbb {N}$.

Stated in terms of a Turing machine $V$, and a polynomial function $P(n)$ with input of size $n$, $V$ is said to be of a polynomial time complexity if it halts after at most $P(n)$ steps.

On a deterministic Turing machine this class is P and on a non-deterministic Turing machine it is NP. This means that if the previously defined Turing machine $V$ is a deterministic Turing machine of time complexity $P(n)$, then any language $L$ is said to be in P if it is equal to $L(V)$.

P and NP

P is a class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. It is some times referred to as PTIME, standing for Polynomial (D)TIME.

We can define P in terms of DTIME as such:

${\mathcal {P}}=\bigcup _{k\in \mathbb {N} }{\mathcal {DTIME}}\left(n^{k}\right)$

NP, on the other hand, is a class of languages that are decidable in polynomial time on a non-deterministic Turing machine.

NP is usually defined in terms of deterministic turing machines as being the class of problems that are verifiable in deterministic polynomial time. This basically means that assuming that we know the correct path of states that the non-deterministic Turing machine takes, we can use a deterministic Turing machine to verify the answer in polynomial-time.

We can define NP in terms of NTIME as such:

${\mathcal {NP}}=\bigcup _{k\in \mathbb {N} }{\mathcal {NTIME}}\left(n^{k}\right)$

Because we know that deterministic Turing machines are restricted types of non-deterministic Turing machines, we can say the P is a subset of NP. It is still not known whether it is a strict subset, but is assumed by many in the field.