Scholarlink

We show that deciding simulation equivalence and simulation preorder have quadratic lower bounds assuming that the Strong Exponential Time Hypothesis holds. This result matches the best known quadratic upper bounds of simulation equivalence. This means that, assuming the Strong Exponential Time Hypothesis, deciding simulation is inherently quadratic. A consequence of our result is that computing simulation equivalence is fundamentally harder than computing bisimilarity.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Quadratic Lower Bound for Simulation

  • 章节

  • 发表日期：

    2026年

查看全文
  • Jan Friso Groote,
  • Jan Martens

摘要

We show that deciding simulation equivalence and simulation preorder have quadratic lower bounds assuming that the Strong Exponential Time Hypothesis holds. This result matches the best known quadratic upper bounds of simulation equivalence. This means that, assuming the Strong Exponential Time Hypothesis, deciding simulation is inherently quadratic. A consequence of our result is that computing simulation equivalence is fundamentally harder than computing bisimilarity.