# 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.

## Contents

## Complexity Classes[edit]

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[edit]

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 for any .

Stated in terms of a Turing machine , and a polynomial function with input of size , is said to be of a polynomial time complexity if it halts after *at most* 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 is a deterministic Turing machine of time complexity , then any language is said to be in **P** if it is equal to .

**P** and **NP**[edit]

**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 **P**olynomial (**D**)**TIME**.

We can define **P** in terms of **DTIME** as such:

**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:

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.