非确定性限制逻辑及其在计算复杂度中的应用

摘要

过去几十年,有许多组合谜题的计算复杂度被确定了。本文介绍了非确定性限制逻辑,并用归约为非确定性限制逻辑的方法,证明了一种类似于推箱子的种豆游戏的计算复杂度为多项式空间完全的。