12. Géométries Multiples II – Roger Vilder

Roger Vilder (FR)

Géométries multiples II

Teksten door Samuel Fiorini

We nemen twee grafen. De vraag of die al dan niet isomorf zijn, noemen we een vraagstelling of ‘probleem’ en kan helaas niet gemakkelijk beantwoord worden. Sinds de begindagen van de grafentheorie heeft dit probleem immers al heel wat inkt doen vloeien. In 2015 ontdekte de Hongaarse wiskundige László Babai een nieuw algoritme om het probleem aanzienlijk sneller op te lossen dan voorheen (vanuit theoretisch standpunt, weliswaar).

Een erg interessant artikel hierover lees je hier.

En zoals het elke grote vraagstelling betaamt, heeft ook ons probleem van het isomorfisme van grafen een eigen Wikipedia-pagina (al is die helaas niet beschikbaar in het Nederlands).

Het probleem van het isomorfisme van grafen speelt een bijzondere rol in de theoretische informatica, een tak van de informatica die erg nauw aanleunt bij de wiskunde. Al meer dan vijftig jaar trachten informaticatheoretici inzichten te verwerven in de complexiteit van uiteenlopende vraagstellingen, waaronder het isomorfisme van grafen.

Voor bepaalde problemen werden inmiddels snelle algoritmes bedacht. Voor andere problemen lijkt er daarentegen geen enkel snel algoritme te bestaan.

(Binnen de complexiteitstheorie wordt een algoritme ‘snel’ genoemd wanneer zijn functie een berekeningstijd oplevert met polynomiale groei en de grootte van de instantie als variabele heeft.)

Om het wat duidelijker voor te stellen, trachten informaticatheoretici de problemen in klassen onder te brengen naargelang hun complexiteit. Voor beslissingsproblemen, zoals datgene waar we ons hier over buigen, zijn de twee grootste complexiteitsklassen \(P\) en \(NP\):

  • Klasse \(P\) is de klasse van problemen waarvoor een snel algoritme bestaat (P staat voor Polynomiaal).
  • Klasse \(NP\) omsluit klasse \(P\), aangevuld met de vraagstellingen waarop het antwoord JA ‘snel’ gegeven kan worden.

Een voorbeeld: als twee grafen isomorf zijn, bestaat er een isomorfisme dat toelaat van de ene graaf naar de andere over te gaan, en valt het eenvoudig na te gaan of de gegeven bijectie wel degelijk een isomorfisme is. (Bepalen of er sprake is van isomorfisme, is daarentegen verre van evident. En laat dat nu precies ons probleem zijn!)

Het probleem van isomorfisme bevindt zich dus onder complexiteitsklasse NP, net als vele andere interessante vraagstellingen, waarvan vele op een graaf geformuleerd worden.

Onder de klasse \(NP\) vinden we een deelverzameling van problemen. We kunnen die deelverzameling haast vergelijken met “het dorp van onverzettelijke Galliërs“. Het gaat immers om de complexiteitsklasse ‘\(NP\)-volledig’, ook ‘\(NP\)-compleet’ genoemd, oftewel de moeilijkste vraagstellingen binnen \(NP\). Al die problemen zijn gelijkwaardig in die zin dat, als voor één ervan een snel algoritme bestaat, er bijgevolg voor elk ervan één bestaat. 

Voor de overgrote meerderheid van vraagstukken in \(NP\) weten we met zekerheid dat ze tot \(P\) behoren, dan wel tot \(NP\)-volledig. Het probleem van de kortste weg behoort bijvoorbeeld tot \(P\). Het kan samengevat worden in de volgende vraag:

We beschikken over een graaf \(G\), twee knopen \(x\) en \(y\), en een getal \(D\).
 Bestaat er een weg van \(x\) naar \(y\) die korter of gelijk is aan \(D\)?

Vreemd genoeg behoort het probleem van de langste weg daarentegen tot \(NP\)-volledig:

We beschikken over een graaf \(G\), twee knopen \(x\) en \(y\), en een getal \(D\).
 Bestaat er een weg van \(x\) naar \(y\) die langer is dan \(D\)?

In het dagelijkse leven is dit laatste probleem niet meteen van groot belang, aangezien de meesten onder ons efficiëntie wensen. Het probleem kan echter wél interessant zijn voor handelsvertegenwoordigers of politici op ronde. Via deze link kom je hier meer over te weten.

Het probleem van het isomorfisme van grafen is bijzonder, in die zin dat men niet weet of het tot \(P\) behoort, dan wel tot \(NP\)-volledig. Het lijkt erg aannemelijk dat het om een van de zeldzame zogenoemd ‘\(NP\)-intermediaire’ vraagstellingen gaat, aangezien die moeilijker zijn dan alle problemen die tot \(P\) behoren, maar gemakkelijker zijn dan eender welk probleem uit \(NP\)-volledig. 

Dit fascinerende probleem is dus een vreemde eend in de bijt, wiens verhaal nog lang niet is uitverteld!

Samuel Fiorini
Associate Professor
Algebra and Combinatorics
Département de mathématique
Université libre de Bruxelles – ULB
http://homepages.ulb.ac.be/~sfiorini/

Pagina’s: 1 2 3