Titlebook: Structural Complexity I; José Luis Balcázar,Josep Díaz,Joaquim Gabarró Textbook 1995Latest edition Springer-Verlag Berlin Heidelberg 1995

联合

978-3-642-79237-3Springer-Verlag Berlin Heidelberg 1995

Vo2-Max

Structural Complexity I978-3-642-79235-9Series ISSN 1862-4499 Series E-ISSN 1862-4502

Conjuction

Texts in Theoretical Computer Science. An EATCS Serieshttp://image.papertrans.cn/s/image/879874.jpg

Discrete

Allodynia

Basic Notions About Models of Computation,pts of formal languages, set theoretic operations and relations, boolean formulas, and several models of computation, such as finite automata and the different versions of Turing machines: deterministic, nondeterministic, and oracle Turing machines.

Reservation

大包裹

Nonuniform Complexity,thms solving the problems. But any finite set can be recognized in constant time and zero work space by a deterministic finite automaton; therefore, measuring the amount of resources is meaningless when considering only finite sets. The “intrinsically algorithmic” approach makes sense only when dealing with infinite sets.

Cupping

chandel

Introduction,In its most general sense, Complexity Theory encompasses several quite different approaches. All of them have in common two characteristics, which can be considered as a general definition of the field: first, they study algorithms and the problems solved by them; second, they focus on the computational resources required by these algorithms.

farewell

Time Bounded Turing Reducibilities,After introducing the polynomial time .-reducibility and the logarithmic space .-reducibility in Chapter 3, in this chapter we shall introduce other types of reducibilities and related considerations, like the properties of sets of low density and the concept of self-reducible set.