Computing minimal distinguishing Hennessy-Milner formulas is NP-hard, but variants are tractable.
Jan MartensJan Friso GrootePublished in: CoRR (2023)
Keyphrases
- np hard
- np complete
- computational complexity
- tree decompositions
- special case
- approximation algorithms
- constraint satisfaction problems
- integer programming
- lower bound
- linear programming
- optimal solution
- worst case
- scheduling problem
- minimum cost
- np hardness
- branch and bound algorithm
- closely related
- computationally challenging
- upper bound
- approximation ratio
- remains np hard