We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness of N C , and we observe that it has surprising consequences. Note also that the choice of super-quasi-polynomial blowup is the smallest bound that avoids the circuit class collapse of [Vol98].

In this proposal we put our assumption in perspective, discuss its relation to the existing literature, and show that it has two important consequences. The first consequence is N C = S C , where N C is the class characterized by uniform circuits of poly-logarithmic depth and polynomial size, and S C is characterized by algorithms that run in poly-logarithmic space and polynomial time. For the second consequence we use an additional but mild complexity assumption to obtain a strong separation between the graph isomorphism GraphIso and the group isomorphism GroupIso problem. In particular, we show that GraphIso is not reducible to GroupIso using circuits of O ( log n ) depth.