标题： 热化不可解性的更多内容：(几乎)独立同分布的输入和有限晶格 显示英文标题

标题： More on Intractability of Thermalization: (almost) i.i.d. inputs and finite lattices

摘要： 这项工作是Shiraishi和Matsumoto [10]的扩展，讨论了一维晶格中具有平移不变最近邻相互作用的局部可观测量的长期平均值的计算复杂性，针对简单的初始状态。 如前一篇论文所示，这个问题通常是难以处理的。 在本文中，我们进一步细化了这一结论。 首先，我们考虑初始状态的限制，其中所有站点的状态都相同，只有一个站点除外。 我们证明了这个问题的这个版本也是不可判定的（RE完全）。 然后我们转向晶格大小有限的情况：根据输入大小的定义，这个问题的这个版本可能是EXPSPACE完全或PSPACE完全。 显示英文摘要

摘要： This work is an extention of Shiraishi and Matsumoto [10], and discusses the computational complexity of the long-term average of local observables in one-dimensional lattices with shift-invariant nearest-neighbor interactions for simple initial states. As shown in the previous paper, the problem is generally intractable. In this paper we refine the statement further. First, we consider restriction of the initial state, where the state of all the sites are the same except for a single site. We show this version of the problem is also undecidable (RE-complete). Then we turn to the case where the lattice size is finite: depening on the defitiniton of the input size, this version of problem is either EXPSPACE-complete or PSPACE-complete.