Source author record

Markus Steindl

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.GR Computational Complexity

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The subpower membership problem for bands

Fix a finite semigroup $S$ and let $a_1,\ldots,a_k, b$ be tuples in a direct power $S^n$ . The subpower membership problem (SMP) for $S$ asks whether $b$ can be generated by $a_1,\ldots,a_k$ . For bands (idempotent semigroups), we provide a dichotomy result: if a band $S$ belongs to a certain quasivariety, then $SMP(S)$ is in P; otherwise it is NP-complete. Furthermore we determine the greatest variety of bands all of whose finite members induce a tractable SMP. Finally we present the first example of two finite algebras that generate the same variety and have tractable and NP-complete SMPs, respectively.

preprint2016arXiv

The subpower membership problem for semigroups

Fix a finite semigroup $S$ and let $a_1,\ldots,a_k, b$ be tuples in a direct power $S^n$ . The subpower membership problem (SMP) asks whether $b$ can be generated by $a_1,\ldots,a_k$ . If $S$ is a finite group, then there is a folklore algorithm that decides this problem in time polynomial in $nk$ . For semigroups this problem always lies in PSPACE. We show that the SMP for a full transformation semigroup on 3 letters or more is actually PSPACE-complete, while on 2 letters it is in P. For commutative semigroups, we provide a dichotomy result: if a commutative semigroup $S$ embeds into a direct product of a Clifford semigroup and a nilpotent semigroup, then SMP(S) is in P; otherwise it is NP-complete.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.