关于热化难解性的进一步探讨:(接近)独立同分布输入与有限格点问题

该工作是对Shiraishi和Matsumoto [10]研究的拓展,主要探讨了具有平移不变近邻相互作用的一维晶格中局部可观测量长期平均值的计算复杂度问题(针对简单初始态)。如前期论文所示,该问题在一般情况下难以处理。本文进一步细化了相关论述。首先,研究人员考察了初始态受限的情况(即所有格点状态相同,仅存在单一格点例外),证明该版本问题同样不可判定(属于RE完全类)。随后转向有限晶格尺寸情形:根据输入规模定义方式的不同,该版本问题要么属于EXPSPACE完全类,要么属于PSPACE完全类。

量科快讯