Choiceless Computation and Symmetry
Choiceless Computation and Symmetry
复制标题
无选择计算和对称性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Benjamin Rossman
中科院分区：
文献类型：
--
作者：
Benjamin Rossman
计算机科学中的许多自然问题都涉及像图这样的结构，其中元素不是天生有序的。相比之下，图灵机和其他常见的计算模型对字符串进行操作。虽然图可以被编码为字符串（通过邻接矩阵），但编码对顶点施加线性顺序。这使得图灵机能够在编码图时以低成本从任何非空的顶点集中选择任意元素（BIPARTITE MATCHING的增广路径算法就是选择能力的一个例子）。然而，计算的结果倾向于依赖于外部线性阶（即，编码的选择）。此外，同构不变性/编码独立性是图灵机的不可判定性质。这种编码的麻烦导致Blass，Gurevich和Shelah [3]提出了一种称为BGS机器的计算模型，直接在结构上操作。BGS机器在计算的每一步都保持对称性，牺牲了在输入结构的不可区分元素之间做出任意选择的能力（因此是“无选择计算”）。Blass等人还引入了一个复杂度类CPT+C（Choiceless Polynomial Time with Counting），它是根据多项式有界的BGS机器定义的。虽然CPT+C中的有限结构的每个性质在通常意义下都是多项式时间可计算的，但反过来P中的每个同构不变性质是否属于CPT+C是开放的。在本文中，我们给出的证据CPT+C P通过证明相应的函数问题类的分离。具体来说，我们证明了有限向量空间上存在一个同构不变的多项式时间可计算函数问题（“给定一个有限向量空间V，输出V中的超平面集”），这是任何CPT+C程序都不可计算的。另外，我们给出了支撑定理的一个新的简化证明，它是文[3]中关于弱形式的CPT+C不计数不能决定集合奇偶性的结果的关键步骤。
Many natural problems in computer science concern structures like graphs where elements are not inherently ordered. In contrast, Turing machines and other common models of computation operate on strings. While graphs may be encoded as strings (via an adjacency matrix), the encoding imposes a linear order on vertices. This enables a Turing machine operating on encodings of graphs to choose an arbitrary element from any nonempty set of vertices at low cost (the Augmenting Paths algorithm for BIPARTITE MATCHING being an example of the power of choice). However, the outcome of a computation is liable to depend on the external linear order (i.e., the choice of encoding). Moreover, isomorphism-invariance/encoding-independence is an undecidable property of Turing machines. This trouble with encodings led Blass, Gurevich and Shelah [3] to propose a model of computation known as BGS machines that operate directly on structures. BGS machines preserve symmetry at every step in a computation, sacrificing the ability to make arbitrary choices between indistinguishable elements of the input structure (hence "choiceless computation"). Blass et al. also introduced a complexity class CPT+C (Choiceless Polynomial Time with Counting) defined in terms of polynomially bounded BGS machines. While every property finite structures in CPT+C is polynomial-time computable in the usual sense, it is open whether conversely every isomorphism-invariant property in P belongs to CPT+C. In this paper we give evidence that CPT+C ≠ P by proving the separation of the corresponding classes of function problems. Specifically, we show that there is an isomorphism-invariant polynomial-time computable function problem on finite vector spaces ("given a finite vector space V, output the set of hyperplanes in V" ) that is not computable by any CPT+C program. In addition, we give a new simplified proof of the Support Theorem, which is a key step in the result of [3] that a weak version of CPT+C absent counting cannot decide the parity of sets.