2. 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:

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

  3. dogelang adding pattern matching

    If you haven't read about dogelang, you really should. It is python with haskell-syntax where you can use all python modules. So basically coffee-script but for a language that is already useful. And python bytecode is emitted instead of first compiling to python itself, but that just as a side-node.

    On my behest, the developer of dg added pattern matching so that in an if-condition a tuple-unpacking-expression does not raise an exception if the unpacking fails but returns false.

    Therefore one can now implement their own zip and list-constructor in the following manner:

    zip = x' y' -> if
  ([x, *xs], [y, *ys] = x', y') =>
    yield (x, y)
    yield from $ zip xs ys
  otherwise => yield from ()

list = x' -> if
  ([] = x') => []
  ([x, *xs] = x') => [x] + list xs

    This looks almost like haskell's case-pattern-matching but not quite, so it is sure to annoy every haskell-programmer.

    You might need to execute python3 -m dg -b once after installing/updating dg to rebuild the interpreter/compiler-bundle with this feature.

    In other news: It is quite likely that I will hold a small talk about dogelang at Leipzig's next Haskell conference HaL-10.

  4. Upgrading Fedora 22 to 23

    Fedora 23 was released a few days ago.

    I've upgraded one of my machines. The others are soon to follow. I have yet to hit a problem with Fedora 23.

    If you're running Fedora 22 you can easily upgrade to Fedora 23 running the following console commands. But before that, make sure your system is fully upgraded and rebooted, especially if you installed some kernel updates.

    sudo dnf install dnf-plugin-system-upgrade
sudo dnf system-upgrade download --releasever=23 --best

    The --best argument makes sure if there are any transaction problems, the installation will not continue. I've had to remove some old gstreamer-plugins that are sure to come back with a new installation of fedy.

    Once all the downloads are done, type sudo dnf system-upgrade reboot to reboot your system starting the actual upgrading process.

  5. Published: Wed 04 November 2015
    meta

    technically, Hello Internet

    This is my new blog housing all the technical computer-science and programming stuff that doesn't fit nicely within my wordpress installation. I will also post links and the usual "to-remind-me" stuff.

    This page will be in English where applicable.

« Page 8 / 8

links

social

Theme based on notmyidea