Title: On the Complexity of Probabilistic Bisimilarity

Speaker: Di Chen, University of Oxford

Time/Date: Friday, Sep 30, 2:30pm - 3:30pm
Location: Room 3530

Abstract:

Probabilistic bisimilarity is a notion of equivalence for probabilistic labelled transition systems.
A system and its bisimulation quotient can be considered indistinguishable, and quotienting by 
bisimilarity is a widely-used compression technique in verification and performance analysis.

Metric bisimilarity introduces a measure of distance between states. It is more robust than bisimilarity,
which does not take advantage of small behavioural differences, regardless how minimal they are. 

Bisimilarity is known to be in PTime. This paper further shows it is complete for PTime.

On the other hand, only approximation algorithms are known for the metrics. The paper reveals that any
member of the family of metrics can be computed exactly, even in polynomial time. This is a vast improvement
from the previous upperbound of 2-EXPTIME for the decision problem.

The results are most surprising as one notes that the spectrum of problems studied in this paper are all
PTime-complete, and hence complexity theoretically equivalent.