# Musings on Graph Isomorphism pre-results

I think by now everybody has read that Babai et al will hold a seminar next
week where they want to "*outline an algorithm that solves the Graph Isomorphism
problem [...] in quasipolynomial time*".

So they are shooting for a result with the complexity \(2^{O(log(n))^c}\) while the best former result (by Luks, 1983) for Graph Isomorphism was \(2^{O(\sqrt{n*log(n)})}\).

**What is Graph Isomorphism?** Given two graphs, the question is, whether there
is a mapping function \(f\) between the nodes of one graph \(G_1\) to
the nodes of the other graph \(G_2\) so that every edge \((a,b) \in G_1\)
is also an edge \((f(a),f(b)) \in G_2\).

**So why is this quasipolynomial** when \(2^x\) is obviously not a polynome?
That's where the quasi comes from. If the \(c\) in \(2^{O(log(n))^c}\) is
\(1\) then this simplifies to \(2^{O(log(n))}\) which is a polynomial.
Remember that the base of both the logarithm and the exponentiation isn't actually
\(2\) so this doesn't simplify to \(O(n)\) but some other polynomial
(but a polynomial nevertheless). And the \(c\) is just a factor in the
formula (like the base the logarithm and the exponentiation) that have no impact
on the complexity properties (the general shape of the formula describing the
complexity) but can be changed by optimization (opposite to groundbreaking
research). So given proper optimization the algorithm we will be presented
could be (theoretically) as fast as a polynomial algorithm.

**When we talk about
"fast"** we talk about how the runtime changes (relatively) when the problem size
grows larger. A "faster" algorithm has smaller relative growth while it might
still be orders of magnitude slower in actual runtime for any practically sized
input.

**Is this result surprising?** Well, yes and no. On the one hand the "witness"
(or positive solution to the problem) is only of linear size
(one mapping for every node in the graph) and the algorithm for checking would
be basically quadratic in complexity (checking the definition given above for all
edges and there are only quadratically many). This holds for problems in NP-complete
but also for problems in P. I think it is obvious that this answer would
not be **very** hard to find (we surely don't need to check every possible mapping
- this would basically be the case for NP-complete) but it isn't obvious that the
answer is **easy** to find either (like for a problem in P).

**So what we're probably going to see** is a clever application of some result of group
theory that is applicable here and excludes a large number of all possible
isomorphism as possible solutions. So the problem is still not easy but math
can help a lot.

**What does it mean?** It is not known whether Graph Isomorphism is NP-Complete.
This result would be a strong hint, that it isn't (albeit no proof). Even if
we found Graph Isomorphism to be in P, this would have no larger impact
on the field of complexity theory in general.

**What's the next thing?** That would be finding an algorithm properly in P.
If such an algorithm exists, we would also find a way to compute a small "witness"
(or in this case "proof trail") that is an easily checkable answer to the question
"is there no such isomorphism?". How this proof trail would look is even less obvious.
There could be some function that, given a graph as input calculates a value
and all graphs that have an isomorphism between them have the same value (which
would also need to not be exponential in size). In practice it is very difficult
to even find hard instances of Graph Isomorphisms. So it might turn out that there
are actually only easy cases, we just don't know it yet.

Read more and differently here:

- https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-graph-isomorphism/
- https://www.reddit.com/r/compsci/comments/3ri3fo/earlier_today_i_was_tipped_off_to_what_might_be/
- http://www.scottaaronson.com/blog/?p=2521

*If it wasn't obvious, I don't believe that P=NP because I don't believe that NP
is closed under complement.*

Previous: dogelang adding pattern matching , Next: Deciding on the pure-ness of a python function

Comments and Discussionis provided by Disqus. They are tracking site and user interaction. Please refer to their privacy policy for information about data usage and retention. If you still want to look at comments or comment yourself, enable disqus by clicking here.