Let's consider another example.

For example, we have two integers,

two, maybe, natural numbers,

a which has n digits,

and b which also has n digits.

Now, we're going to add these numbers,

a and b, using the column addition method we learned at school.

This method will require at most two n of elementary additions,

and elementary addition is just the addition

of one digit to another digit.

So, we see that the complexity,

the number of steps we need to perform to accomplish the result,

depends on this n,

the number of digits.

We can say that the complexity of the problem is O of n. So,

it's linear regarding the number

of digits in the numbers we have to add.

Now, imagine that we have to multiply these numbers.

So, instead of summing them,

we have to multiply them.

This will require approximately n square

of elementary or table multiplications which

means that the complexity of

the multiplication problem is O of n squared.

We can see now that if when n grows,

the complexity of multiplication grows

faster than the complexity of addition.

Anyway, we don't consider multiplication problem to be very hot.

Actually, any infinite power

here tells us that the problem is not so bad.

All the problems for which we have

a polynomial complexity algorithm,

we consider them to be tractable.

All such problems form the infinite class called b.

So, all these problems for which we know or for which can

exist an algorithm with polynomial complexity defined like this.

A set of this class of tractable problems which we call

P. There is another interesting class

of problems which is called NP.

Here, P stands for polynomial,

and NP for non-deterministic polynomial.

The problems from the class in P are those problems or

those functions for which we can

easily or polynomially check and answer.

The ability to check the answer is important.

Imagine one day, one of your friends come to you and says

that he or she developed a computer program,

a chess player computer program which cannot lose.

Now, can you easily check this statement?

I believe that, no, you cannot because, actually,

you will have to play all possible chess games with

this program to understand if it can loose or it cannot.

Now, imagine another situation that

this friend came to you and tells you

that he or she found a Hamilton path on some graph.

Now, can you check this statement? Yes, you can.

You can just follow this path provided to you by

this friend and see if it visits every edge exactly once.

So, the complexity of this check will be O of n

where n is the number of vertices in this graph.

So, this statement is easily checkable,

and the finding of Hamilton path in some graph is,

thus, an NP problem,

because maybe it's hard to find this path,

but if somebody finds it,

it is easy to check if it is correct.

Out of those that P belongs to NP, because,

for any problem from P,

we can easily check the answer just

by solving this problem with polynomial algorithm.

But the stronger assertion,

if P is less than NP,

is one of the most famous,

most important unproven theorems in modern complexity theory.

Because this theorem is not proven,

we still have to consider these two options on the slide here,

if P is not equal to NP,

here, and if P equals to NP.

So, you see class P here, class NP.