Complexity problems in computational theory
A. O. Slisenko · Russian Mathematical Surveys · 1981
CONTENTS Introduction Chapter I. Methods of general computability theory in complexity bounds § 1. Complexity hierarchies. Complexity in finite domains § 2. Exponential and high lower bounds § 3. Complexity classes. Universal problems Chapter II. Methods and techniques for constructing fast algorithms § 1. Identification of subwords of a given word § 2. Computation of collections of arithmetical expressions § 3. Solution of equations and inequalities. Decomposition into irreducibles § 4. Problems on graphs and geometrical problems § 5. Searching for information. Syntactic analysis Chapter III. Lower complexity bounds for restricted models § 1. Computational models § 2. Lower time bounds § 3. Lower bounds for algebraic complexity References