We now turn to defining Hamiltonian Cycles.

Today I define similar Eulerian Cycles.

But now, our goal is to traverse all the nodes of the graph,

but not all the edges as in Eulerian Cycles.

For example, this graph is actually Hamiltonian.

Meaning that there is a Hamiltonian Cycle in this graph.

And if you already tried to construct the Hamiltonian Cycle for this graph by hand,

you probably noticed that it is not so easy.

So this isn't it.

This is a Hamiltonian Cycle in this graph.

And it is not so difficult to check that it is, indeed, a Hamiltonian Cycle.

So, it always traverses some edge on one hand,

and it goes through all vertices of this graph exactly once.

Okay. So, the dramatic difference between Hamiltonian Cycles and Eulerian Cycles,

is that for Hamiltonian Cycles,

we have no simple criteria known that will

allow us to check whether a graph has a Hamiltonian Cycle or not.

So, nothing like checking whether all the vertices are balanced or not,

is known for determining whether it has a Hamiltonian Cycle or not.

And more generally, there is no polynomial time algorithm

known for finding a Hamiltonian Cycle in a graph.

Or even for checking whether there exists a Hamiltonian Cycle in this graph.

So, recall that for the Eulerian Cycle problem,

we had a very efficient algorithm.

So, we try and time this proportional to

the number of nodes plus the number of edges, of the graph.

For Hamiltonian's Cycle, nothing like this is known.

We don't even know how to solve this problem

in the number of steps proportional to something like,

the number of nodes plus the number of edges through the power of 100, for example.

We don't know how to do this.

And in fact, this is the essence- I mean the question of existence

of such a polynomial time algorithm.

For the Hamiltonian Cycle problem, is the essence of the famous P versus NP problem.

Which is the most important problem in computer science.

Open problem in computer science.

It is one of the so-called millennium prize open problem.

For resolving this open problem,

Clay Mathematical institute provides a bounty of $1 million.

So, very roughly, to state this problem in one or two minutes.

Let me try to state it as follows.

So, P is the class of all computational problems that can be solved efficiently,

that is in polynomial time.

For example, Eulerian Cycle problem is in the class P.

Because we do have efficient algorithms for this problem.

On the other hand, NP is the class of all computational problems,

for which we can find a solution efficiently.

What does it mean? Well, if I give you a graph,

then it is not so clear how to find a Hamiltonian Cycle.

But if I give you a graph,

together with the Hamiltonian Cycle,

then you can easily check whether the given Cycle is indeed,

a valid Hamiltonian Cycle in this graph or not.

So, a solution can be easily verified.

Both for a Hamiltonian Cycle problem,

and for Eulerian Cycle problem.

So, we know that Eulerian Cycle problem and Hamiltonian Cycle problem,

lie in the Class NP.

But it is only for Eulerian Cycle problems,

that we know that it lies inside the class P. So,

the question is whether the Hamiltonian Cycle problem

belongs to the class P of all computational problems,

that can be solved efficiently.

We still don't know the answer to this question,

and there is a bounty of $1 million.

Let me repeat, for resolving this important open problem in computer science.