Isomorfieproblemen

Isomorfieproblemen zijn beslisproblemen in de wiskunde en theoretische informatica die vragen of twee objecten als structureel gelijk kunnen worden beschouwd. Gegeven twee objecten X en Y uit een bepaald domein, is de vraag of er een isomorfie bestaat tussen X en Y: een bijectieve kaart f van X naar Y die alle relevante structuur behoudt, zodat relaties en operaties op X op dezelfde manier in Y voorkomen.

Tot de meest bestudeerde domeinen horen grafen, groepen, ringen en modules, maar isomorfieproblematiek komt in veel andere structuren voor, zoals reliëfs in meetkunde of algebraïsche objecten in computationele algebra. In elk domein ligt de nadruk op de vraag of twee invoeren in wezen hetzelfde object beschrijven onder een geschikte rijtje van transformerende observaties.

Er bestaan verschillende varianten van het probleem: het beslissen of twee invoeren isomorf zijn, het construeren van een expliciete isomorfie indien die bestaat, en het tellen of classificeren van niet-isomorfe objecten. Daarnaast bestaan gerelateerde problemen zoals het vinden van automorfismen (isomorfieën van een object met zichzelf) of het bepalen van een canonieke representatie voor elk isomorfe klasse.

Complexiteit en algoritmen variëren sterk per domein. Het Graph Isomorphism-probleem (GI) is beroemd: lang onbekend of GI in P zit, maar een quasi-polynomiale tijdsoplossing werd in 2016 gepresenteerd. Voor sommige classes, zoals bomen, grafen met beperkte degrees of planaire grafen, bestaan efficiënte algoritmen. Algoritmen voor canonieke vormen en kleurverfijning (Weisfeiler-Lehman) spelen een centrale rol bij praktische oplossingen.

Toepassingen bevinden zich onder meer in chemische informatica, patroonherkenning, databankdeduplicatie en netwerkvergelijking, waar het herkennen van structurele gelijkheid essentieel is.