;7

1 Introduction Computational complexity theory studies the quantitative laws which govern computing. It seeks a comprehensive classification of problems by their intrinsic difficulty and an understanding of what makes these problems hard to compute. The key concept in classifying the computational complexity of problems is the complexity class which consists of all the problems solvable on a given computational model and within a given resource bound