De complexiteit van Buchbergers algoritme

Gr¨obnerbases vormen een van de centrale objecten van de algebra¨ısche meetkunde, als het gaat om het expliciet uitvoeren van berekeningen. Een Gr¨obnerbasis van een ideaal in een polynoomring is een stel voortbrengers met fijne algoritmische eigenschappen. Met behulp van een Gr¨obnerbasis kunnen veel problemen eenvoudig worden opgelost. We noemen het oplossen van een stelsel polynomiale vergelijkingen, het bepalen of een polynoom in een ideaal ligt en het bepalen of twee idealen gelijk zijn. Zie [8] of [11] voor meer toepassingen. Al deze problemen hebben een hoge algoritmische complexiteit. Bijvoorbeeld, zelfs als we ons beperken tot polynomen in 4 variabelen is het ideaallidmaatschapsprobleem (bepalen of een polynoom in een gegeven ideaal ligt) NP-moeilijk, wat betekent dat ieder NP-compleet probleem in polynomiale tijd te reduceren is tot dit probleem [24]. Het volgt meteen dat de constructie van een Gr¨obnerbasis uit een willekeurig stel voortbrengers van een ideaal niet...Show moreGr¨obnerbases vormen een van de centrale objecten van de algebra¨ısche meetkunde, als het gaat om het expliciet uitvoeren van berekeningen. Een Gr¨obnerbasis van een ideaal in een polynoomring is een stel voortbrengers met fijne algoritmische eigenschappen. Met behulp van een Gr¨obnerbasis kunnen veel problemen eenvoudig worden opgelost. We noemen het oplossen van een stelsel polynomiale vergelijkingen, het bepalen of een polynoom in een ideaal ligt en het bepalen of twee idealen gelijk zijn. Zie [8] of [11] voor meer toepassingen. Al deze problemen hebben een hoge algoritmische complexiteit. Bijvoorbeeld, zelfs als we ons beperken tot polynomen in 4 variabelen is het ideaallidmaatschapsprobleem (bepalen of een polynoom in een gegeven ideaal ligt) NP-moeilijk, wat betekent dat ieder NP-compleet probleem in polynomiale tijd te reduceren is tot dit probleem [24]. Het volgt meteen dat de constructie van een Gr¨obnerbasis uit een willekeurig stel voortbrengers van een ideaal niet eenvoudig kan zijn. Een algoritme dat deze constructie uitvoert is gegeven door Buchberger, en het is naar hem genoemd. Het principe van dit algoritme is om net zolang voortbrengers van het ideaal te blijven toevoegen totdat we een Gr¨obnerbasis hebben. Buchbergers algoritme termineert altijd, maar het bewijs daarvan is niet constructief. Daarom is het onbekend hoelang het algoritme bezig is, oftewel wat de complexiteit ervan is. Hier is veel onderzoek naar gedaan, maar sluitende onder- en bovengrenzen zijn er niet. Naast Buchbergers algoritme zijn er andere algoritmes die Gr¨obnerbases construeren [19, 28]. Deze zijn echter van meer theoretisch belang en in de praktijk werkt Buchbergers algoritme het beste. We gaan hier in deze scriptie niet verder op in. We beginnen deze scriptie met een behandeling van de onderliggende theorie. We defini¨eren Gr¨obnerbases, voeren Buchbergers algoritme in en formuleren de complexiteitsvragen. We eindigen dit hoofdstuk met een voorbeeld. De meeste stellingen bewijzen we niet: we verwijzen vaak naar het boek van Cox, Little en O’Shea [11]. De eerste twee hoofdstukken van dat boek zijn ook heel geschikt als een grondigere inleiding in Gr¨obnerbases dan we hier geven. In hoofdstuk 2 geven we ondergrenzen voor de complexiteit. We laten zien dat de grootte van een Gr¨obnerbasis dubbelexponentieel kan groeien in het aantal variabelen in de polynoomring. Aan de andere kant is er altijd een Gr¨obnerbasis met grootte begrensd door een vergelijkbare bovengrens: dat bewijzen we in hoofdstuk 3. Het is onbekend of deze bovengrens ook geldt voor de complexiteit van Buchbergers algoritme. In hoofdstuk 4, het belangrijkste deel van deze scriptie, leiden we een nieuwe bovengrens voor die complexiteit af, in termen van de Ackermannfunctie. We gebruiken daarbij alleen combinatorische argumenten. Tot dusver waren er vrijwel alleen bovengrenzen bekend onder beperkingen op de invoer (zoals het aantal variabelen of de gebruikte monoomordening), maar onze grens geldt algemeen. Kort geleden ontdekten we dat dit resultaat niet geheel nieuw is: vergelijkbare grenzen worden afgeleid in [13]. Toch zullen we op bladzijde 25 zien dat onze grenzen een nuttige toevoeging vormen. Het laatste hoofdstuk behandelt enkele onderwerpen uit de literatuur rond Buchbergers algoritme en de complexiteit daarvan. We bespreken aanpassingen van het algoritme die de complexiteit verlagen. Ook geven we complexiteitsgrenzen wanneer het aantal variabelen in de polynoomring klein is. Ten slotte bekijken we de invloed van monoomordeningen op het algoritme, en hoe we daar gebruik van kunnen maken. Ik wil mijn begeleiders Ronald van Luijk en Jeannette de Graaf, en ook Hendrik Lenstra, bedanken voor de tijd en moeite die ze hebben gestoken in de ondersteuning van dit bacheloronderzoek.Show less

Leiden University Student Repository

Documents

In Collections

De complexiteit van Buchbergers algoritme