chap limits to computation slowbut perhaps there are better ones waiting to be discovered of coursewhile having problem with high running time is badit is even worse to have problem that cannot be solved at allproblems of the later type do existand some are presented in section this presents brief introduction to the theory of expensive and impossible problems section presents the concept of reductionwhich is the central tool used for analyzing the difficulty of problem (as opposed to analyzing the cost of an algorithmreductions allow us to relate the difficulty of various problemswhich is often much easier than doing the analysis for problem from first principles section discusses "hardproblemsby which we mean problems that requireor at least appear to requiretime exponential on the input size finallysection considers various problems thatwhile often simple to define and comprehendare in fact impossible to solve using computer program the classic example of such problem is deciding whether an arbitrary computer program will go into an infinite loop when processing specified input this is known as the halting problem reductions we begin with an important concept for understanding the relationships between problemscalled reduction reduction allows us to solve one problem in terms of another equally importantlywhen we wish to understand the difficulty of problemreduction allows us to make relative statements about upper and lower bounds on the cost of problem (as opposed to an algorithm or programbecause the concept of problem is discussed extensively in this we want notation to simplify problem descriptions throughout this problem will be defined in terms of mapping between inputs and outputsand the name of the problem will be given in all capital letters thusa complete definition of the sorting problem could appear as followssortinginputa sequence of integers xn- outputa permutation yn- of the sequence such that yi <yj whenever once you have bought or written program to solve one problemsuch as sortingyou might be able to use it as tool to solve different problem this is