A taxonomy of problems with fast parallel algorithms. (English) Zbl 0575.68045

Cook, Stephen A.

Inf. Control 64, 2-22 (1985).

This is a revised and expanded version of the author’s paper in Lect. Notes Comput. Sci. 158, 78-93 (1983; Zbl 0529.68014).

MSC:

68W99	Algorithms in computer science
68Q25	Analysis of algorithms and problem complexity
03D60	Computability and recursion theory on ordinals, admissible sets, etc.

Keywords:

uniform Boolean circuit families; reducibility; parallel greedy algorithm