Go to page
 

Bibliographic Metadata

Title
Computational complexity of the subpower membership problem for semigroups / eingereicht von: Dipl.-Ing. Markus Steindl, BSc
AuthorSteindl, Markus
CensorMayr, Peter ; Szendrei, Agnes
PublishedLinz, November 2015
Description83 Seiten
Institutional NoteUniversität Linz, Univ., Dissertation, 2015
Annotation
Zusammenfassung in deutscher Sprache
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Halbgruppe / Band / direktes Produkt / direkte Potenz / Membership-Problem / Algorithmus / Komplexität / NP-vollständig / PSPACE-vollständig
Keywords (EN)semigroup / band / direct product / direct power / membership problem / algorithm / complexity / NP-complete / PSPACE-complete
Keywords (GND)Halbgruppe / Direktes Produkt / Algorithmus / Komplexität / NP-vollständiges Problem / PSPACE
URNurn:nbn:at:at-ubl:1-6506 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Computational complexity of the subpower membership problem for semigroups [0.96 mb]
Links
Reference
Classification
Abstract (German)

Eine grundlegende Problemklasse in der Computeralgebra sind Membership- Probleme. Darin gilt es zu entscheiden, ob eine gegebene Struktur ein bestimmtes Element enthält. Wenn wir beispielsweise einen Körper F fixieren, und Vektoren a1 [a tief 1],...,ak [a tief k],b in einem Vektorraum Fn [F hoch n] gegeben sind, so wollen wir oft entscheiden, ob b in der linearen Hülle von a1 [a tief 1],...,ak [a tief k] liegt. Das lässt sich mit Hilfe des Gaußschen Eliminationsverfahrens mit einem Zeitaufwand, der polynomial in n und k ist, beantworten. In der vorliegenden Arbeit studieren wir eine besondere Variante des Member"- ship-Problems, die von Willard im Zusammenhang mit Constraint- Satisfaction-Problemen (CSP) formuliert wurde [10, 21]. Sei S eine endliche Halbgruppe, und seien a1 [a tief 1],...,ak [a tief k],b Tupel in einer direkten Potenz Sn [S hoch n]. Im Subpower-Membership-Problem SMP(S) gilt es zu entscheiden, ob b in der von a1 [a tief 1],...,ak [a tief k] erzeugten Unterhalbgruppe von Sn [S hoch n] liegt. Man entscheidet also, ob b als ein Produkt aus a1 [a tief 1],...,ak [a tief k] darstellbar ist. Die Größe des Inputs von SMP(S) ist proportional zu (k+1)n. Ob b in der von a1 [a tief 1],...,ak [a tief k] erzeugten Unterhalbgruppe liegt, können wir durch einen simplen Abschlussalgorithmus entscheiden. Der Zeitaufwand dafür ist höchstens exponentiell in n. Unser Ziel ist, folgende Fragen zu beantworten: (1) Wie wirkt sich die Halbgruppe S auf die Komplexität von SMP(S) aus? (2) Für welche Halbgruppen S kann man SMP(S) in einem Zeitaufwand, der polynomial in n und k ist, beantworten? (3) Für welche S ist SMP(S) NP- vollständig bzw. PSPACE-vollständig? Diese Begriffe sind folgendermaßen definiert: Ein Problem ist in P, wenn es in polynomialer Zeit (polynomial in der Größe des Inputs) beantwortet werden kann; es ist in NP, wenn es durch eine nichtdeterministische Turingmaschine in polynomialer Zeit beantwortet werden kann; und es ist in PSPACE, wenn der für die Beantwortung erforderliche Speicherbedarf polynomial in der Größe des Inputs ist. P ist in NP enthalten, was wiederum in PSPACE enthalten ist. Obwohl es dafür keinen Beweis gibt, wird weitgehend angenommen, dass die Klassen P, NP und PSPACE voneinander verschieden sind. Man nennt ein Problem vollständig in einer Klasse, wenn es in dieser Klasse enthalten ist, und es in einem gewissen Sinne mindestens so schwierig wie jedes andere Problem in dieser Klasse ist. Das SMP für endliche Gruppen ist laut einer Arbeit von Furst et al. [5] in der Komplexitätsklasse P. In [2] haben Bulatov, Mayr und der Autor bewiesen, dass das SMP für jede endliche Halbgruppe in PSPACE ist. Wir haben außerdem Halbgruppen angegeben, für die das SMP NP-vollständig bzw. PSPACE-vollständig ist. Das waren gleichzeitig die ersten bekannten algebraischen Strukturen, für die das SMP eine dieser Komplexitäten annimmt. Darüber hinaus haben wir eine Dichotomie für kommutative Halbgruppen bewiesen: Das SMP einer kommutativen Halbgruppe ist entweder in P oder NP-vollständig. Die Ergebnisse aus [2] bilden das vierte Kapitel dieser Arbeit. Wir beweisen außerdem eine P/NP-vollständig- Dichotomie for idempotente Halbgruppen. Für einfache Halbgruppen zeigen wir, dass das SMP in P liegt. Eine vielfach studierte Halbgruppe ist die 5-elementige Brandt-Halbgruppe. Sie wird von allen 2-mal-2-Matrizen gebildet, die höchstens eine Eins und sonst nur Nullen enthalten. Wir zeigen, dass das SMP der Brandt-Halbgruppe NP-vollständig ist. Wenn wir die Einheitsmatrix zu dieser Halbgruppe hinzunehmen, erhalten wir das Brandt-Monoid. Dessen SMP stellt sich als PSPACE-vollständig heraus. Daraus folgt, dass viele natürlich auftretende Halbgruppen ein PSPACE- vollständiges SMP haben. Darunter sind die vollen Transformationshalbgruppen auf mindestens 3 Elementen, und Halbgruppen von n-mal-n-Matrizen über Körpern für n größer gleich 2.

Abstract (English)

Deciding membership is a basic problem in computer algebra. For instance if F is a fixed field and we are given vectors a1 [a tief 1],...,ak [a tief k],b in a vector space Fn [F hoch n], we often want to decide whether b is in the linear span of a1 [a tief 1],...,ak [a tief k]. This question can be answered using Gaussian elimination in polynomial time in n and k. In the present thesis we study a particular variation of the membership problem proposed by Willard in connection with the study of constraint satisfaction problems [10, 21]: Fix a finite semigroup S and let a1 [a tief 1],...,ak [a tief k],b be tuples in a direct power Sn [S hoch n]. The subpower membership problem SMP(S) asks whether b is in the subsemigroup generated by a1 [a tief 1],...,ak [a tief k]. In other words, SMP(S) asks whether b can be written as some product in a1 [a tief 1],...,ak [a tief k]. The input size of SMP(S) is essentially (k+1)n. We can decide the membership of b in the subsemigroup generated by a1 [a tief 1],...,ak [a tief k] in exponential time in n using a straightforward closure algorithm. Our goal is to answer the following questions: (1) How does the semigroup S affect the computational complexity of SMP(S)? (2) For which semigroups S can SMP(S) be solved in polynomial time in k and n? (3) For which S is SMP(S) NP-complete or PSPACE-complete? Note that a problem is in P if it is solvable in polynomial time (polynomial in the input size), in NP if it is solvable in polynomial time by a nondeterministic Turing machine, and in PSPACE if it is solvable in polynomial space. P is contained in NP, which is contained in PSPACE. It is widely assumed but not proved that the complexity classes P, NP, and PSPACE are distinct. A problem is complete in a complexity class if it belongs to this class and is, in a sense, at least as hard as any other problem in this class. The SMP for finite groups is in the complexity class P by a result of Furst et al. [5]. In [2] Bulatov, Mayr, and the author of the present thesis showed that the SMP for every finite semigroup is in PSPACE. We gave examples of semigroups whose SMP is NP-complete and PSPACE-complete, respectively. These were also the first algebraic structures known to have a SMP with one of these complexities. We also established a dichotomy result for commutative semigroups: The SMP of a commutative semigroup is either in P or NP-complete. The results from [2] form the fourth chapter of this thesis. We will also establish a P/NP-complete dichotomy for idempotent semigroups. For simple semigroups the SMP is shown to be in P. A frequently studied semigroup is the 5-element Brandt semigroup. It is formed by all 2 by 2 matrices with at most one entry 1 and the rest 0. We prove that its SMP is NP-complete. If we add the identity matrix, then the resulting Brandt monoid has a PSPACE-complete SMP. It follows that the SMP for a number of semigroups is PSPACE-complete. This includes the full transformation semigroup on at least 3 letters, and semigroups of n by n matrices over fields for n at least 2.