Titlebook: Structural Complexity II; José Luis Balcázar,Josep Díaz,Joaquim Gabarró Book 1990 Springer-Verlag Berlin Heidelberg 1990 Kolmogorov comple

进取心

anaerobic

漂泊

Resource-Bounded Kolmogorov Complexity,a can be formalized as we do in this chapter, giving rise to a different concept of complexity, known as ., which has been succesfully used for proving lower bounds in a more concrete approach to complexity theory.

faddish

Probability Classes and Proof-Systems,alizations of results from Chapters 6 and 8 in Volume I. Finally, in the last section, we prove that for a bounded number of interactions, interactive proof-systems classes and Arthur-Merlin classes coincide.

成绩上升

知道

Certainty

Misgiving

Uniform Circuit Complexity,n modelling parallel computation, we wish to model the situation in which the number of processors is greater than the length of the input; however it is clear that any “real world” parallel computer should have a feasible number of processors. For this reason most of the theoretical research on par

禁止,切断

jeopardize

Bi-Immunity and Complexity Cores,y several different properties. A stronger notion is defined, and a construction of a set having this property is presented. Then it is shown that several properties of polynomial time .-reducibility and of the sets complete for this reducibility can be deduced from the existence of bi-immune sets.