Computability and Complexity/Complexity/Time Complexity/P

P

We can classify all the computational problems into 2 categories, that can be solved by algorithms and that cannot be solved. Although some problems can be solved, we may not be able to solve them in reasonable amount of time. The problems which can be solved are classified in to P and NP. There are other classifications also, but we shall concentrate on P and NP. These classifications are known as complexity classes. Generally speaking, the class P contains problems which can be solved in a reasonable amount of time and NP contains those which cannot be.

The complexity class P

${\text{P}}=\bigcup _{k}{\text{TIME}}(n^{k})$

The complexity class P contains problems that can be solved in a bounded time. The algorithms for solving such problems are bounded by a polynomial function of the input size. The complexity has two parts, a fixed part and a variable part. The fixed part will not depend on any thing else, it is a constant for a given algorithm, but the variable part varies across different instances of the same problem, for e.g. we know that the time taken by a sorting algorithm to sort ten numbers is not the same as the time taken for sorting hundred numbers. Usually the time/space taken by an algorithm will depend on the size of the input to a problem. We can express the time/space taken by an algorithm as the sum of a constant and a polynomial function of the input size. The problems, whose algorithms to solve them, has a complexity that can be expressed as a polynomial, belong to class P. Obviously P stands for polynomial.

Previous | Next