Satt og tenkte litt på problemet med å sjekke at to grafer er isomorfe. La oss bare anta at de har lik lengde og slikt, sånn at man ikke jobber med slike special cases. Ideelt så burde man sortere nodene i riktig rekkefølge i forhold til hverandre også bare sjekke om kantstrukturen er identisk (eller om nabomatrisene deres er identiske), men akkurat denne sorteringen av noder virker ikke helt triviell eller polynomisk for meg. Har noen et hint eller et innspill?

Basert på Piazza-spørsmål fra 2015

To grafer er isomorfe hvis de har lik struktur for en eller annen mapping av nodene i den ene til den andre. Så hvis du antar en fast mapping (f.eks. at nodene skal mappes til dem med samme navn), og du finner at de har samme struktur, så er grafene isomorfe, ja (og det kan du lett gjøre i polynomisk tid), men om de ikke har samme struktur, så sitter du fortsatt igjen med \(n!-1\) mulige mappinger som må prøves ut før du kan svare definitivt nei.

Så du har helt rett i at denne sorteringen ikke er triviell, siden det er akkurat den som er problemet :-)

Så langt har vel ingen klart å vise at graf-isomorfi er NP-komplett, men man tror kanskje den tilhører en egen klasse i NP, utenfor P og NPC (gitt at P ≠ NP, selvfølgelig), sammen med flere andre like vanskelige (graf-isomorfi-komplette, eller GI-komplette) problemer.

Se ellers: http://mathworld.wolfram.com/GraphIsomorphismComplete.html

Det er forøvrig lett å vise at delgraf-isomorfi er NP-komplett. (Dvs., å avgjøre om én graf er isomorf med en delgraf av en annen.)

Oppdatering, noe senere:

Nyhet/rykte: En kvasipolynomisk algoritme (dvs. en med kjøretid \(2^{O((\log n)^c)}\) for en konstant \(c\) – altså mellom polynomisk og eksponentiell) for dette problemet:

https://lucatrevisan.wordpress.com/2015/11/03/laci-babai-and-graph-isomorphism/

Hm, jeg kom over den nyheten for noen dager siden. Veldig spennende, men siden GI ikke er i NPC så har det vel uansett ikke noen implikasjoner for om NP = P, det vil vel bare bidra til mer knoting mtp ulike kompleksitetsklasser? :P Kom forøvrig over det gjennom han fyren her: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

Men jeg skjønner enda ikke helt hvorfor det tar polynomisk tid å verifisere en løsning på GI. Jeg kom over denne løsningen: http://cs.jhu.edu/~cs363/fall2013/assign9_sln.pdf som jeg egentlig ikke skjønner helt. Består denne verifiseringen bare av at du har at nodene i riktig rekkefølge, og du bare går over den grafen du sjekker at det er tilsvarende kanter og noder som i den andre…?

Vi vet ikke om GI er i NPC :-). Men du har jo rett – foreløpig har ingen vist at GI er i P eller i NPC, så det påvirker ikke P vs NP. Men P vs NP er jo uansett bare en flik av feltet kompleksitetsteori – den fliken dere lærer om ;-)

Det med å sjekke svaret er egentlig veldig enkelt – det var bare den forklaringen som kanskje var litt formell. La oss si at nodene i den første grafen heter \(a, b, \dots\) og nodene i den andre heter \(1, 2, \dots\) Jeg forteller deg at de er isomorfe, og vil overbevise deg ved å fortelle deg at \(a\) tilsvarer \(1\), \(b\) tilsvarer \(2\) og så videre. (Altså en én-til-én-mapping mellom nodesettene). Du kan da sjekke at de to grafene har kanter mellom nøyaktig de samme nodene, for hvis du behandler de korresponderende nodene som ekvivalente. Dvs., det skal være en kant mellom \(a\) og \(b\) hvis og bare hvis det er en kant mellom \(1\) og \(2\), etc.