Deciding bisimilarity is<Emphasis Type="Italic">P</Emphasis>-complete

In finite labelled transition systems the problems of deciding strong bisimilarity, observation equivalence and observation congruence areP-complete under many—oneNC-reducibility. As a consequence, algorithms for automated analysis of finite state systems based on bisimulation seem to be inherently sequential in the following sense: the design of anNC algorithm to solve any of these problems will require an algorithmic breakthrough, which is exceedingly hard to achieve.