It is known that deciding bisimilarity is a P-complete problem. This means it is thought of as a problem that is inherently sequential and hard to solve in parallel. Despite this fact efforts have been made to construct increasingly efficient parallel algorithms. In a previous colloquium I presented a parallel algorithm that decides bisimilarity in O(n) time on n+m parallel processors that are allowed to concurrently read and write. In this talk I will discuss what the parallel intractability of P-complete problems means, and what this means for further improvements of the algorithm.