At the end of the second world war II the world of mathematics was astonished as well.

During the war a new type of machines were developed, machines who had computational capacities that were unattainable for human being- machines which will be later known as computers.

 

Since the foundation process of the computers the following questions were raised: What can they really compute? Can they compute any mathematical problem?

 

Alongside with the physical development of the computers, the theme that there some problems can be computed very efficiently while others require intractable time (time that can vary from several years to a number which is greater than the total number of atoms in the universe).

 

In theory of computer science researchers are trying to classify mathematical problems into easy and hard tasks: In the lecture I will describe when will we classify problem as an easy one whereas other will be classified hard.

 

The lecture will require only a elementary math school background, no fear!