If NC = P, then every problem with a polynomial-time sequential algorithm could be sped up to a polylogarithmic parallel algorithm

3 Parallel, probabilistic, and quantum complexity Even taking into account our current inability to resolve Open Questions 1–3, the hierarchy of complexity classes depicted in Figure 2 ranging from \(\textbf{P}\) to \(\textbf{EXP}\) represent the most robust benchmarks of computational difficulty now available. Beyond this hierarchy a wide array of additional classes are also studied which are believed to demarcate additional structure either inside \(\textbf{P}\) or between \(\textbf{P}\) and \