论文标题
小组问题的动态复杂性
Dynamic Complexity of Group Problems
论文作者
论文摘要
Immerman和Patnaik PI97在90年代引入了动态复杂性，并通过对Dynfo dkmsz18的定向可达性的积极分辨率进行了兴趣的复兴。从那时起，许多与可达到性和匹配有关的自然问题已在Dynfo和相关类别DMVZ18，DKMTVZ20，DTV21中放置。在这项工作中，我们从Dynfo中提出了一些动态问题。 特别是，假设我们在代表非结构化二进制操作的n个元素上给我们一个任意乘法表（代表称为岩浆的结构）。假设该表通过其一个步骤中的一个N^2条目之一的变化演变。对于一个岩浆元素的集合也一次更改一个元素，我们可以维护足够的辅助信息，以便当岩浆是一个组时，我们能够回答S和目标t的Cayley组成员资格（CGM）问题（即，t是S的产物？ ”）在每个步骤中使用FO查询。这将动态的CGM问题（对于组）当通过Dynfo中的表指定环境岩浆时。相反，相反，对于表设置，已知CGM在类logspace barringtonm06中。构建基于CGM的构建，我们可以在两个魔法下保持两个魔法，而两者都依靠两种魔法。 我们的技术包括一种使用左括号内括号内岩浆在Dynfo中维持岩浆元素的能力的方法，Cube独立性对立方体的概念产生了一个由集合产生的亚组，一种与McKenziecook一起可从McKenzeiecook中获得的一些组理论的方法，以维持岩浆中最大的立方体独立序列。据我们所知，立方体独立序列的概念是新的，并且可能具有独立感兴趣。这些技术与迄今为止在动态复杂性中使用的技术有很大不同。
Dynamic Complexity was introduced by Immerman and Patnaik PI97 in the nineties and has seen a resurgence of interest with the positive resolution of their conjecture on directed reachability in DynFO DKMSZ18. Since then many natural problems related to reachability and matching have been placed in DynFO and related classes DMVZ18,DKMTVZ20,DTV21. In this work, we place some dynamic problems from group theory in DynFO. In particular, suppose we are given an arbitrary multiplication table over n elements representing an unstructured binary operation (representing a structure called a magma). Suppose the table evolves through a change in one of its n^2 entries in one step. For a set S of magma elements which also changes one element at a time, we can maintain enough auxiliary information so that when the magma is a group, we are able to answer the Cayley Group Membership (CGM) problem for S and a target t (i.e. "Is t a product of elements from S? ") using an FO query at every step. This places the dynamic CGM problem (for groups) when the ambient magma is specified via a table in DynFO. In contrast, for the table setting, statically CGM was known to be in the class Logspace BarringtonM06. Building on the dynamic CGM result, we can maintain the isomorphism of of two magmas, whenever both are Abelian groups, in DynFO. Our techniques include a way to maintain the powers of the elements of a magma in DynFO using left associative parenthesisation, the notion of cube independence to cube generate a subgroup generated by a set, a way to maintain maximal cube independent sequences in a magma along with some group theoretic machinery available from McKenzieCook. The notion of cube independent sequences is new as far as we know and may be of independent interest. These techniques are very different from the ones employed in Dynamic Complexity so far.
