No label defined (Q3801066)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4068272
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4068272 |
Statements
1987
0 references
commutative transformation semigroups
0 references
threshold
0 references
index
0 references
parallel complexity
0 references
NP-complete
0 references
0.8102569580078125
0 references
0.7829664945602417
0 references
0.7690742015838623
0 references
0.7593920826911926
0 references
0.7575085759162903
0 references
[For the entire collection see Zbl 0616.00013.] Let \(\tau_ X\) denote the full transformation semigroup on a finite set X. For \(f\in \tau_ X\), let \(t\geq 0\) and \(p>0\) be the least integers such that \(f^{t+p}=f\) t. The integer t is called the threshold of f (some authors use the term index) and, of course, p is the period of f. The threshold of a subsemigroup S of \(\tau_ X\) is defined to be the largest of the thresholds of the transformations which belong to S. Suppose S is commutative and \(f\in \tau_ X\). \textit{P. McKenzie} and \textit{S. A. Cook} had previously shown [The parallel complexity of the abelian permutation group membership problem, Proc. 24th IEEE FOCS Symposium, 154-161 (1983); cf. SIAM J. Comput. 16, 880-909 (1987; Zbl 0647.68045)] that the problem of testing if \(f\in S\) can be done in parallel in depth \(O(\log \quad 3 n)\quad (NC\quad 3)\) if the threshold of S is zero, that is, if S is an abelian group. The present author shows that testing can be done in polynomial time, NC 3 in parallel, if the threshold of S is one and it is NP-complete if the threshold is greater than one.
0 references