Algorithm Solves Graph Isomorphism in Record Time (2015)
quantamagazine.org
quantamagazine.org
(Originally presented for the Bourbaki Seminar, so not exactly for the non-mathematician, but has more context than reading the paper directly.)
The fixes linked above are mentioned in the WARNING below the abstract and explained at 18.1.
Here are some gentle articles on the zero-knowledge in case anyone is curious:
https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
"Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems."
(exp((log n)^O(1)))
Interesting that there could be a much more varied landscape than was previously thought.
EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.
See [1] the Tits alternative which implies that if your group is linear (huh) then the growth function is either polynomial or exponential. Then there is a result by Gromov [2] which says that if the growth is polynomial then the group is virtually nilpotent. There was a long standing question if there exist finitely generated groups with an intermediate growth and the first example was found [3].
So it's not interesting until it becomes interesting due to a newly discovered fact.
[1] https://en.wikipedia.org/wiki/Tits_alternative
[2] https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_o...
Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2.
There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step."
It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.
I assume you mean "interesting" ones? Since they could just show a program that counts up to n^log(n) and voila, you have a super-polynomial sub-exponential algorithm.
In which case... I still don't think it's just algorithms for these problems? https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8...
But if they're all still complicated, and this is why they're not taught, then I feel like I'd have appreciated being told this at least...
You're quite right that complexity theory takes us to a hierarchy far richer than simply polynomial and exponentiation [0]. Your question about the emphasis on those two in particular, is a good one. Might be worth submitting on cs.stackexchange.com as a 'soft question'.
[0] https://en.wikipedia.org/wiki/Time_complexity#Table_of_commo...
In particular, the section relevant to your question is "1.2.2 The Polynomial-Time Objection" on page 7, quoted in full below:
> Objection: But why should we draw the border of efficiency at the polynomial functions, as opposed to any other class of functions—for example, functions upper-bounded by n^2, or functions of the form n^((log n)^c) (called quasipolynomial functions)?
> Response: There’s a good theoretical answer to this: it’s because polynomials are the smallest class of functions that contains the linear functions, and that’s closed under basic operations like addition, multiplication, and composition. For this reason, they’re the smallest class that ensures that we can compose “efficient algorithms” a constant number of times, and still get an algorithm that’s efficient overall. For the same reason, polynomials are also the smallest class that ensures that our “set of efficiently solvable problems” is independent of the low-level details of the machine model.
> Having said that, much of algorithms research is about lowering the order of the polynomial, for problems already known to be in P, and theoretical computer scientists do use looser notions like quasipolynomial time whenever they’re needed.
To add a couple of points of my own:
- We need to consider at least polynomial functions, for the closed-ness reason (though in practice the exponent is usually small), and superpolynomial functions (in the theoretical/asympotic sense, slower than any polynomial, even n^100000 or whatever!) are already slow enough not to be considered efficient. For that matter do you learn any single exponential algorithm in (say) an undergraduate course? If you're in an area where exponential algorithms are of interest though, then it's not actually unusual to study sub-exponential (and superpolynomial) ones, as those are the most efficient we have.
* There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Factoring could be taught though, if the students are all interested in number theory I guess. When I took a course on "algebra and computation" (problems in group theory etc), we did encounter quite a few such algorithms.
Thanks for the link, but again, it only explains why polynomials are interesting, not why we don't care about things bete
> For that matter do you learn any single exponential algorithm in (say) an undergraduate course?
Fibonacci? And basically brute-force solution to pretty much any problem they give you in a first course?
> There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course.
Yeah I'm getting to the conclusion this is the crux of it. It'd be nice if they at least mentioned this is why?
* Case 1: Analysis of algorithms: This is where you write down some algorithm/program, and analyze how long it takes. Here, you're limited by the kind of algorithms you can write down easily; you're not likely to encounter “polynomial” in general but about specific typical functions like n, n log n, n^2, n^3, 2^n, k^n, etc. Functions like n^13 or n^(log n) are equally exotic and unlikely to be encountered this way (as there are no natural/simple algorithms with that complexity); perhaps the most “exotic” it gets are the n^(log 3) and n^(log 7) of Karatsuba's and Strassen's algorithms respectively (both happen to be polynomial).
* Case 2: Computational complexity theory: Here you care about which complexity class a problem / language lies in, like P, NP, PSPACE, whatever. As we've already established that polynomials are the smallest closed class, and anything superpolynomial is definitely not “fast”, here the only interesting distinction of note is between polynomial and superpolynomial, as between “fast” and “not fast”. From your telling it would seem that exponential complexity is somehow treated as especially interesting, but in my experience this is not the case. If at all exponential time comes up it's mainly because that turns out to be the result of analysis of some natural algorithm (as in Case 1 above) and “exponential” is interesting only insofar as it implies “not polynomial”.
My impression/guess is that you're combining (1) the fact that superpolynomial-subexponential algorithms don't turn up naturally (just as, say, n^53 doesn't either), (2) the fact that we do talk about polynomial complexity, and (3) the fact that exponential algorithms do turn up naturally, to claim that we care about polynomial and subexponential complexity but nothing in between, which doesn't seem to be the case.
A lot of people really struggle through these introductory courses. It wouldn't be very kind or helpful to stop and point out that the stuff they're struggling with is the easy stuff.
When undergrads do go a bit further, it tends to be about things like parallel algorithms, sub-linear algorithms, and space-bounded algorithms. Those are plenty interesting and tend to be more useful to know about.
Now, why "natural" problems so easily fall into these two categories and not others is a different mystery and not what you asked.
Converting an algorithm from a Turing machine to a random-access model will often give you a polynomial speedup, but not an exponential one, so "polynomial time" means the same for both.
If you have a problem A, and a polynomial reduction from A to B, and a polynomial algorithm for B, you have a polynomial algorithm for A.
Sometimes algorithms can be polynomial but intractable (or even exponential but practical for some real cases), but it's less "neat" or clean to reason about those things. (Very useful, though, just more done outside the academy.)
As for things that aren't polynomial, I guess exponential things just happen to be the most common kind? Not sure myself why "pseudo-polynomial" bounds aren't more common.
For one thing, it's robust to reasonable changes of model, for "No true Scotsman" definitions of "reasonable".
The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for.
Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.
I didn't mean more fine-grained than polynomial. I meant between polynomial and exponential.
> On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for.
> Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.
These just say why we care about polynomial-time reducibility as a means for specifying a class. It doesn't say why we only look at polynomial and exponentials classes though, which is what i'm saying. There are infinitely many classes in between. Why just focus on these two?
(Btw, I think you mean neither definitely P nor definitely NP-hard.)
In a decent textbook on computational complexity theory, you can read that a problem is NP-hard if for every problem in NP there exists a polynomial-time reduction to it. Nobody claims that such a reduction exists, e.g. for integer factorization and graph isomorphism.
So why the distinction between poly and exp? A modern computer runs at about 10 GHz, 10,000 million ticks per second, and there are about 3.16×10^7 seconds in a year. Suppose your problem has size n=100. Then an n^3 algorithm takes 3.17×10^{-12} years. A 2^n algorithm takes 4.02×10^{12} years. The first is perfectly practible, the second is not (its time is longer than the age of the universe).
So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function.
In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial.
Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.
No, that just tells me why we make a distinction between exponentials and polynomials, not why we always focus on those two in particular. It's not like there aren't other complexities in between that you can't make the same kind of statement about...
Complexity theory itself is a gross estimation on reality and performance. Complexity theory tells you nothing about how fast (or slow) an algorithm is in practice: quicksort typically is faster than merge sort, despite both being O(n * log(n)).
Heck, quicksort can be faster than radix sort in many cases. Another case: Bitonic sort is asymptotically slower at O(n * log^2(n)), but Bitonic sort lends itself to parallelism very well, so its "faster" in practice (even if its not work-efficient).
So why do people use complexity analysis at all? Its completely irrelevant to determining quicksort vs mergesort vs bitonic sort!
Well, simple: because its relatively easy to calculate, and relatively easy to understand. Polynomial time, and Nondeterministic Polynomial time (aka NP-complete) are both "easy" to describe and understand (for a... somewhat interesting definition of easy). At least, in the greater scope of mathematics they're concise and "simple" definitions.
----------
A great number of algorithms in Knuth's "The Art of Computer Programming" are calculated out to the precise number of assembly-language statements executed... including the constant. No "big-O" estimates involved.
This deeper analysis is great to read once or twice, but read enough of it and you realize how much harder it is to think about. Complexity theory is far faster to analyze and apply to algorithms, even if its an incomplete picture. As such, emphasis should be on "ease of use" and "convenience" as opposed to any real amounts of practical rigor.
----------
The other issue: is that NP vs P is the great unsolved mathematical problem of our lifetime. So a huge amount of professors introduce the concept of NP vs P so that their students can be ready for a major mathematical debate relevant to the field.
-----------
EDIT: In practical optimization, I think most people care about "Linear", "Sublinear", and "Superlinear". For example, the Painter's Algorithm for GPUs is superlinear: O(n * log(n)). But a depth-test based approach to GPU scene painting is linear: O(n). Linear is "good enough" so optimization basically stops there.
Any algorithm that visits all data is going to be, at best, linear. So that's why GPU programmers probably are happy with "depth test", because Asymptotically Linear complexity is the best you can reasonably hope for.
For more see: https://math.stackexchange.com/questions/226628/orders-of-gr...
1. P is a roughly approximate definition of «feasible» problems.
P doesn't perfectly capture problems we intuitively understand as feasible (e.g, P includes problems which are solved in O(n^10000) time), but it is good in other respects: its definition is independent of computation model (but the model has to be able to simulate a Turing machine with at most polynomial slowdown, which is true for all reasonable models); P has complete problems; P is closed under many ways of combining algorithms (e.g. if you run a poly-time algorithm poly times, what you get is also a poly-time algorithm). So P isn't perfect way to define feasible problems, but it's good enough (or maybe the best we have?).
There may exist other ways to formalize feasible computations, which could fix P's drawbacks. Maybe complexity theorists will come up with one later, when they get a better understanding of computations. But until then, they work with what they've got.
2. Even if you don't buy all this «feasibility» interpretation, P will still make perfect sense for theory. Especially, when you ask questions about its relation to other classes.
It is natural for computer scientists to consider variations of some computation model and try to understand which of those variations are stronger and how much stronger they are. For example, randomized and nondeterministic Turing machines are variations of usual deterministic Turing machine (DTM). But the former two have their own unique superpowers, which are randomness and nondeterminism. But how powerful these superpowers are? Can a DTM provided with such a superpower solve more problems? And if so, can we compensate the DTM's lack of superpower by providing it more running time? How much time would suffice for that?
In these terms we can say, that P-vs-NP question actually asks whether polynomial-time DTM's lack of nondeterminism can be compensated by allowing it to run poly(n) times longer. Similarly, if you ask the same question but with «randomness» instead of «nontereminism», you will get another famous problem of P-vs-ZPP (or P-vs-BPP, depending on your definition of randomness).
Computer scientists asked similar questions for models other than Turing machine, and successfully answered them. For example, for finite automatons we already know how many extra states we need to go from nondeterministic to deterministic one. Similarly, for communication complexity we know something about the relation between nondeterministic, deterministic, and randomized complexity.
EDIT: Ooops, I replied to the original version of your post, before you clarified what you meant.
I'm curious: for the graph isomorphism problem, how are the graphs defined then? It seems there must be a geometric component in there because if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same, wouldn't it?
It should be noted than one of the common used algorithms, called VF2, and descendants of it basically just check all possible bijections, although they use some heuristics to prune the search tree.
In order to show that one node in the first graph correspond to a particular node (i.e. is isomorphic) in the second graph, its not enough to check that they have the same number of outgoing edges. You have then to check all the connected nodes, and then make sure that those are also isomorphic to the respective same nodes in the same roles at the other graph.
This makes the problem recursive and dependent on the rest of the graph; you can't simply split the graph and solve each sub-problem fast.
0-1-2 0-2-1
Is that the same as this graph? a'->b' b'->c' c'->a' d'->a'
You can sort the edges alphabetically in the first graph. Then you could take the second graphs labels, and figure out if there is a way to "relabel" it, so when you sort those edges alphabetically, you can the same result.
There are |V|! possible ways to relabel |V| vertices. Other algorithms are better than "try everything", but this shows why it's not trivial. Like a puzzle, you can put the pieces into place, and everything looks right, but then when you get to the end you realize one piece doesn't fit. Does that mean it's not-isomorphic? or maybe you just need to re-arrange the pieces differently? That's why the complexity is so high.
No, there isn’t.
”if they were defined just in terms of abstract sets of vertices and edges between them, it would be rather trivial to show if two graphs are the same”
No, it isn’t, unless you know a novel argument that hasn’t been thought of yet by mathematicians.
It is fairly simple for graphs with very few vertices or very few edges, but in general, it isn’t easy at all.
Things like VF2 can be used for sub-graph isomorphism (and various variants of that problem). Nauty (and this paper) are useless for solving that problem.
I work in this area, and it's interesting (to me at least) that you would imagine the algorithms for graph isomorphism and sub-graph isomorphism would be quite similar and they really aren't.
So are you convinced that Nauty is still the best thing that we have nowadays? I was looking at the paper last summer with the intention to implement it for Julia, but then got sidetracked with other stuff. Maybe I should resume that.
The basic algorithm isn't that hard -- I have a few implementations lying around (nothing in Julia). Traces is better, but is much harder to implement and it isn't clear the improvement is worth it for someone implementing from scratch.
There are some improvements, particularly for graph isomorphism (as opposed to automorphism), but the basic algorithm framework is the same.