Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
复制标题
半群词问题的时间复杂度和希格曼嵌入定理
DOI：
10.1142/s0218196798000132
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
J. Birget
中科院分区：
文献类型：
--
作者：
J. Birget
以Higman嵌入定理的一个改进形式证明了S生成半群的字问题的计算复杂性的如下代数特征：设S是S生成半群，其字问题具有非确定时间复杂性T（其中T是正整数上的超可加函数，即T（n+m）≥T（n）+T（m））.则S可以嵌入到一个半群H中，其中任意两个等价字x和y之间的导子距离（以及等周函数）是O（T（T（x <$+ y <$）2））。此外，从H的字问题到S的字问题存在合取线性时间约简，因此S和H的字问题具有相同的非确定性时间复杂度（也具有相同的确定性时间复杂度）。因此，一个双生成半群S在NTIME（T）（或DTIME（To））中有一个字问题当且仅当S可嵌入一个双表示半群H，其字问题在NTIME（T）（或DTIME（To））中。另一方面，如果一个生成半群S可嵌入到一个等周函数≤ D（其中D（n）≥ n）的表示半群H中，则S的字问题具有非确定时间复杂度O（D）.一个N-生成半群S的字问题是NP（或更一般地说，是NTIME（（T）O（1）当且仅当S可以嵌入一个N-表示半群H中，其多项式（分别为（T）O（1））为等周函数.一个算法问题L在NP中（或更一般地，在NTIME（（T）O（1））中）当且仅当L可约化为（通过线性时间一对一约化）具有多项式（分别为（T）O（1））等周函数的半群的字问题。从本质上讲，这表明：（1）寻找嵌入到可表示的半群或群中是非确定性算法设计的代数模拟;（2）等周函数是非确定性时间复杂度的代数模拟。
The following algebraic characterization of the computational complexity of the word problem for finitely generated semigroups is proved, in the form of a refinement of the Higman Embedding Theorem: Let S be a finitely generated semigroup whose word problem has nondeterministic time complexity T (where T is a function on the positive integers which is superadditive, i.e. T(n+m) ≥T(n)+T(m)). Then S can be embedded in a finitely presented semigroup H in which the derivation distance between any two equivalent words x and y (and hence the isoperimetric function) is O(T(∣x∣+∣y∣)2). Moreover, there is a conjunctive linear-time reduction from the word problem of H to the word problem of S, so the word problems of S and H have the same nondeterministic time complexity (and also the same deterministic time complexity). Thus, a finitely generated semigroup S has a word problem in NTIME(T) (or in DTIME(To)) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (respectively in DTIME(To)). In the other direction, if a finitely generated semigroup S is embeddable in a finitely presented semigroup H with isoperimetric function ≤ D (where D(n) ≥ n), then the word problem of S has nondeterministic time complexity O(D). The word problem of a finitely generated semigroup S is in NP (or more generally, in NTIME((T)O(1))) iff S can be embedded in a finitely presented semigroup H with polynomial (respectively (T)O(1)) isoperimetric function. An algorithmic problem L is in NP (or more generally, in NTIME((T)O(1))) iff L is reducible (via a linear-time one-to-one reduction) to the word problem of a finitely presented semigroup with polynomial (respectively (T)O(1)) isoperimetric function. In essence, this shows: (1) Finding embeddings into finitely presented semigroups or groups is an algebraic analogue of nondeterministic algorithm design; (2) the isoperimetric function is an algebraic analogue of nondeterministic time complexity.