We described an algorithm to compute the Tutte polynomial in

• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Computing the Tutte polynomial in vertex-exponential time. 9th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. IEEE Computer Society 2008, pp. 677–686. [PDF]

In fact, we even have an implementation of this algorithm, which has been available on request from the authors for a while. We have now put this implementation on the public repository GitHub:

• github.com/thorehusfeldt/tutte_bhkk

You can either download a tar archive from there, or (if you use Git) clone the repository.

The code uses some tricks to speed up the implementation. for example, the coefficients are computed modulo several small prime moduli and then assembled with the Chinese remainder theorem.

However, the code remains a very faithful implementation of the underlying inclusion–exclusion idea and uses no other algorithmic ideas. This is the fastest worst-case implementation known to us and outperforms other implementations (for example, on dense graphs) around n(G) = 16. However, for specific input graphs you might meet in the wild, for instance graphs with few edges, small cuts, or many symmetries, other algorithms could perform much better. A very good implementation of many of these other ideas by Gary Haggard, David J. Pearce and Gordon Royle, can be found at

homepages.ecs.vuw.ac.nz/~djp/tutte/

The work in our implementation is done in a C program “tutte_bhkk”, which can be run from the command line. The input is given in 0/1 adjacency matrix format; more precisely, the input is “N row1 row2 ... rowN”, where N is the number of vertices and rowJ is the Jth row of the adjacency matrix. For example, a triangle is given as

3 0 1 1 1 0 1 1 1 0

The output is a table of coefficients, where the entry at row i, column j gives the coefficient of the monomial xⁱy^j for i, j=0, 1, 2, … in

where G is the input graph, V is the vertex set of G, E is the edge set of G, c(G) is the number of connected components in G, c_F(G) is the number of connected components in the subgraph of G with vertex set V and edge set F, and n(G) is the number of vertices in G.

For example, for the triangle we obtain the output

0 1
1
1

or equivalently, T_G(x, y) = x + x₂ + y.

The python module “tutte.py” is a very simple wrapper that serves two purposes.

First, it connects “tutte_bhkk” to the networkx library, which is a collection of graph algorithms and data structures for python. In particular, “tutte.py” exports the function tutte_poly(G), which returns the Tutte polynomial of a given networkx.Graph.

For example, you can write another python script like this:

from tutte import tutte_poly
from networkx import chvatal_graph

print tutte_poly(chvatal_graph())


Second, “tutte.py” can be called from the command line and serves as a convenient interface to “tutte_bhkk”. The input can be given either as an edge list on standard input, or in a compact shorthand format. The output is either a table of coefficients (default) or TeX.

Some examples:

$ python tutte.py --petersen
$ python tutte.py --short="0--1 1--2 2--0" --output=tex
$ python tutte.py
0 1
1 2
2 0
^D


This is an overview of the state of research in exponential time algorithms, which we submitted as a motivation for a Dagstuhl seminar in April 2009. See my longer organiser’s report:

• Organising a Dagstuhl Seminar

The seminar, 10441, is now over, but I think the proposal is a competent snapshot of a rapidly evolving field.

A decade before NP-completeness became the lens through which Computer Science views computationally hard problems, beautiful algorithms were discovered that are much better than exhaustive search, for example Bellman’s 1962 dynamic programming treatment of the Traveling Salesman problem and Ryser’s 1963 inclusion–exclusion formula for the permanent.

Today we know that all NP-hard problems are unlikely to admit polynomial-time algorithms, yet NP-hard problems must be solved, in some way, for everything from manufacturing and supply-chain optimization to railroad timetabling. Approaches include approximation algorithms, heuristics, average-case analysis, and exact exponential-time algorithms: all are essential. While all NP-complete problems are equivalent from the polynomial-time perspective, their exponential-time properties vary widely. Which problems are easiest or hardest? What are the promising algorithmic techniques? What are the connections with parametrized complexity? How fast an algorithm can we find? What about complexity lower bounds?

Work addressing such questions, both from the algorithmic and complexity theoretic sides, has become known as exact complexity. Despite significant progress, the area is still fairly new and many fundamental problems remain open. Where the approximation algorithms field, for example, has unifying algorithmic techniques such as LP rounding and semidefinite programming, and hardness techniques from probabilistically checkable proofs and the Unique Games conjectures, much exact algorithms work is still specific to a particular NP-complete problem: powerful unified techniques are just emerging.

Exciting new results and directions have been established by scientists on several continents, with important contributions coming from young researchers such as Williams and Traxler. The purpose of this workshop is to accelerate developments in this late-blooming field. Below, we outline several new results and promising directions.

The Tutte polynomial of an n-vertex, m-edged graph can trivially be evaluated in time O^*(2^m), but no vertex-parameterized algorithm is obvious. The Potts (q-coloring) partition function can trivially be evaluated in time O^*(qⁿ), but it is not obvious if one can remove the dependence on q. The Fortuin–Kasteleyn model from statistical physics generalizes both, and a breakthrough result of Björklund, Husfeldt, Kaski, and Koivisto [FOCS 2006, STOC 2007, FOCS 2008] shows how to evaluate it using the inclusion–exclusion method in time O^*(2ⁿ). It is an intriguing question as to how far these techniques could be extended.

Recently, the color-coding technique of Alon, Yuster, and Zwick [JACM 1995] has been extended by introducing algebraic structures that yield faster fixed parameter tractable algorithms. Koutis [ICALP 2008] uses “vector coding” for a randomized O^*(2^3k/2) algorithm for the k-Path problem, and Williams [IPL 2009] improves this to O^*(2^k). Such algorithms from group algebra are a promising direction for further exploration.

Branch-and-reduce is one of the most frequently used methods for solving \np-hard problems, but current analyses of such algorithms may be overly pessimistic. Fomin, Grandoni and Kratsch [ICALP 2005, SODA 2006] used a measure and conquer framework to establish simple and fast algorithms to solve the Minimum Dominating Set and the Maximum Independent Set problem. By now measure and conquer analysis has had an enormous impact. This and related methods, Eppstein’s quasiconvex analysis [SODA 2004] and Scott and Sorkin’s linear programming method [Random 2005], have become indispensable, but a need remains for further improvements.

Faster algorithms, notably for Maximum Independent Set, have resulted from computer-produced graphical reductions and case analysis. Can these automated techniques be put on a more general theoretical level, and improved? Can similar automation be applied to logic-based branching rules such as the “clause learning” of Kulikov and Kutzkov [CSR 2007]? What about lower bounds on such local methods?

Exponential-time and other approaches may be combined. Scott and Sorkin’s [CPC 2006] average-case analysis of an exponential-time algorithm shows that Max 2-CSP is solvable in expected linear time on random constraint graphs below the giant-component threshold. It would be interesting to obtain similar results for other problems. Cygan, Kowalik, Pilipczuk and Wykurz [2008] explore exponential-time approximation algorithms trading off the running time and approximation ratio for various problems, an approach well worth further investigation. Hybrid algorithms, introduced by Vassilevska, Williams and Woo [SODA 2006], are exemplified for Minimum Bandwidth: the fastest exact algorithm known takes time O^*(5ⁿ) and the best polynomial-time approximation ratio is roughly O(log³ n), but there is a hybrid algorithm that, depending on the input, produces either the exact minimum in time roughly O^*(4ⁿ) or an O(log^2.5 n) approximation in polynomial time.

Some other approaches merit mention. Horowitz and Sahni’s O^*(2^n/2) Knapsack algorithm [JACM 1974] is an early example of the approach of reducing a hard problem to one that is easy but exponentially large. Williams’ O^*(1.74ⁿ) algorithm for Max 2-CSP [ICALP 2004] is the only nontrivial algorithm known for dense instances. Koivisto’s ring extension of this algorithm [IPL 2006], the Tutte and k-Path work previously mentioned, and Scott and Sorkin’s ring extension of other Max 2-CSP algorithms [TALG 2009] show the power of algebraic approaches.

Despite these algorithmic successes, there may be limits to what is possible. Impagliazzo, Paturi and Zane [FOCS 1998] initiate a complexity theory of exact algorithms, using subexponential-time Turing reductions. They introduce the Exponential-Time Hypothesis (ETH), viz., that the best exact algorithm for 3-SAT has exponential complexity 2^cn where c>0. Assuming ETH they prove that the best exponent sequence c_k for k-SAT must be an increasing sequence [CCC 1999]. Using similar techniques, Traxler [IWPEC 2008] shows that for 2-CSPs over k-valued variables, assuming ETH, any algorithm’s running time must depend strongly on k; this is in sharp contrast to the earlier-mentioned result that k-coloring can be solved in time O^*(2ⁿ), independent of k. These results call for a vigorous investigation of the complexity-theoretic limitations of exact algorithms.

The authors are Dieter Kratsch, Ramamohan Paturi, Gregory Sorkin, and me.

Two years ago, at the Dagstuhl seminar 08431: Moderately Exponential Time Algorithms I was asked to join Dieter Kratsch, Gregory Sorkin, and Ramamohan Paturi to propose a new seminar for 2010.

Here’s how that works.

Dagstuhl expects a written proposal for the proposed seminar, see Dagstuhl’s submission guidelines.

By February 2009, we had an early draft of the proposal ready, and polished it in the following weeks. The most rewarding part was writing the scientific motivation, which turned out as a really good overview of the field of exponential time computation as of Winter 2008. I made a separate blog post of it:

• Overview of Exponential Time Algorithms, Early 2009

The other big task is the list of people to invite. Dagstuhl seminars are by invitation, and a preliminary guest list is submitted by the organisers together with the proposal. Dagstuhl has room for 50 people or so, and we were asked to concoct a non-binding list of 80 potential invitees.

We submitted our proposal time, in early April. I can count some 90 emails between the organisers in my inbox for that part of the process. After the Summer 2009, we got a positive reply from Dagstuhl, together with dates (November 2010).

Next task: assemble the true list of 80 invitees, so that the Dagstuhl office could send out the invitations roughly one year in advance. Also, this list should be partitioned into two rounds of 60 and 20 people, respectively. Dagstuhl then sent out the first 60, using the others when they got refusals back peu à peu. All communication was handled conveniently by the very professional Dagstuhl officers, who regularly kept us up-to-date about the invitation status.

Our hope was that everybody on our 80 people list would be invited, but this turned out to be far from the case. Apparently, acceptance was very high, leaving many very good people uninvited.

Dagstuhl-related emails in late 2009: Maybe 20. Letters of invitation arrived in people’s inboxes January 2010. Yes, that’s physical mail. It’s like the Internet, but made out of trees.

In the first half of 2010, I count 52 emails between the organisers, mainly about individual guests, such as people who hadn’t replied, though they told somebody over coffee they’d surely come, etc. By July, we seemed to have 49 acceptances, at which point Dagstuhl would not invite more people.

Most of the remaining organisation tasks, again, were handled by Dagstuhl: Setting up a web page for Dagstuhl Seminar 10441, sending out travel information, etc.

Among the organisers, we started to talk about the seminar format: how many talks, how to select and schedule, etc., leading to a respectable number of 68 more emails. Most notably, the very last days before the meeting became hectic because of a number of last-minute cancellations.

The seminar itself was stress-free, and I really enjoyed myself. There was some extra organising work with respect to scheduling, arranging an excursion, etc., but for almost everything one can rely fully on the very experienced Dagstuhl environment. It feels extremely reassuring that every little situation that comes up has been handled countless times before, be it by the Dagstuhl staff, the local taxi company, or the restaurant owner arranging the wine tasting.

After the meeting, we wrote a brief thank-you note to the attendees. What remains now is some wrap-up work: a final report, list of open problems, etc.

Oh, and think about the next proposal.

Ryan Williams’s breakthrough result that ACC₀ does not contain NEXP was announced on Richard Lipton’s blog on 8 November 2010.

This is exactly 3 months after a superficially similar announcement, Vinay Deolalikar’s attempt to show that P does not contain NP, which created unprecedented hubbub and excitement on the internet. (See my previous post P vs NP vs PR.)

Few researchers believed Deolalikar’s manuscript. By contrast, the result of Williams has been immediately welcomed with universal astonishment and respect. Our jaws collectively dropped. But they dropped in silence:

Internet attention does not seem to be a good way of measuring validity or relevance. There may be another message here about philosophy of science: Schopenhauer could hardly have been more wrong when he said,

All truth passes through three stages. First, it is ridiculed. Second, it is violently opposed. Third, it is accepted as being self-evident.

Now, back to reading Ryan’s paper. Silently.

I am spending the week at the Dagstuhl meeting 10441: Exact Complexity of NP-hard Problems, which I am also organising.

The site, Schloss Dagstuhl (Dagstuhl @ Wikipedia) is a wonderful place with lots of small details aimed at computer scientists. For example, the street address is Konrad Zuse-Straße. (A full list of Konrad Zuse-Straßen in Germany is maintained by his son, Horst Zuse.)

More whimsically, the marked running trial around Dagstuhl is called n² [PDF]. As Dagstuhl attendees can attest, the route is pretty difficult despite its relatively short length of 5 kilometers. However, I felt that for a workshop on exponential time computation, polynomial “running times” are not ambitious enough, so I organised a longer run, based on the Bardenbacher-Fels-Weg (13–15 kilometers, depending on which map you consult). This hiking trail is currently labelled WA4 by the Wadern tourist authorities, but I am sure if I get the entire Max-Planck Gesellschaft behind me, I can get it renamed to exp(log² n), or something similarly attractive.

In spite of a steady drizzle and the competition from attractive alternative hiking and biking outings, five attendees joined me on this, for a very satisfying run. Maybe next time we’ll arrange a half-marathon. Or maybe not.

I’m immensely proud to have received the 2010 pedagogical prize of D-sektionen, the computer engineering students’ association at Lund University.

The award consists of a diploma and the trophy itself, a golden pointer mounted on a wooden board. The word “pointer” refers to (see what I did there?) a teacher’s pointing stick, not to the computing term, even though I suspect that the play on words is deliberate. Close inspection reveals that the pointer is in fact wooden and painted with gold colour. The left part of the mounting board displays plaques with the names of previous recipients:

• 2005: Görel Hedin
• 2006: Jan Eric Larsson
• 2007: Lars Bendix
• 2009: Andrey Ghulchak
• 2010: Thore Husfeldt

I’ve been teaching at the computer engineering programme for two years now. The course is EDAF05, an introduction to algorithms design that appears in the fourth term of the computer engineering programme, and elsewhere on other programmes.

Here’s an excerpt from the nomination, in Swedish:

Thore är enligt oss den perfekta läraren, han har kunskapen, han har humorn och han har förmågan att kombinera dessa förmågor i en god och pedagogisk undervisning. Genom hans brinnande intresse för pedagogisk undervisning och sitt egna ämne samt sitt engagemang i att göra det intressant även för människorna i hans omgivning, för han över intresset på de studenter han undervisar.

Han pratar öppet och gärna om sin forskning både under föreläsningar, i pauser och när en student kommer upp till honom och visar sig nyfiken. Han har även förmågan att anpassa nivån när han berättar om sin forskning så den passar de aktuella åhörarna. Att knyta an forskning till utbildning på det vis Thore gör är något som vi anser vara eftersträvansvärt, samt belysandet av att detta är genomförbart anser vi alltid ligga rätt i tiden.

Thore lägger även in flertalet trevliga moment i undervisningen. För att ge ett exempel så tog han ner ett antal studenter under en föreläsning för visa hur algoritmen Stable Marriage fungerar på personerna, i stället för att rita på tavlan.

Han lyckas även få studenterna engagerade i föreläsningarna vilket märks genom att studenterna vågar ställa frågor och även öppet svarar och spekulerar när Thore själv ställer frågor under föreläsningarna. Ett förfarande som uppskattas av många studenter är att han även implementerar de algoritmer han går igenom under föreläsningstid, istället för att använda sig av färdigskriven kod.

Algoritmer kan vara väldigt abstrakt och svårt att greppa, men Thore lyckas genom koppling till praktiska, relevanta och roliga exempel konkretisera ämnet på ett mycket bra vis.

What can I say? I’m really happy for this, thanks to whoever nominated me. I have some ideas for improving this course further, all time-consuming, and now feel doubly inspired to implement them next time.

Teaching remains the part of my job I enjoy (and do) best, but it is unrewarding: not in itself—the fact that somebody listens me, and somebody else pays me for, telling about algorithms is an enormous privilege. But all other parts of my job include external gratification as well: when I invest time and energy in research, I can hope to put a new publication on my cv. When I actually prepare for a departmental meeting, I might take some administrative victory home. But for teaching, no such reward system exists. It’s a task that is removed from meritocratic principles, with no external incentive for excellence.

Except, of course, for awards like this. Which is why they not only are a way to make people like me feel immensely good about themselves. They are also a valuable and influential instrument to improve quality of higher education, provided they are handed out with care. With great power comes great responsibility, so please think long and hard about who should be the next recipient.

Here are the papers accepted at The Fifth International Symposium on Parameterized and Exact Computation (IPEC 2010), December 13-15, 2010 at Chennai, India, with links to whatever electronic version I could find. Updates are welcome.

• Robert Crowston, Gregory Gutin, Mark Jones and Anders Yeo. A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and its Algorithmic Application [arxiv 1004.0526]
• Frederic Havet and Leonardo Sampaio. On the Grundy number of a graph
• Robert Ganian, Petr Hlineny, Joachim Kneis, Daniel Meister, Jan Obdrzalek, Peter Rossmanith and Somnath Sikdar. Are there any good digraph width measures? [arxiv 1004.1485]
• Daniel Binkele-Raible and Henning Fernau. Enumerate & Measure: Improving Parameter Budget Management
• Chris Calabro, Impagliazzo Russell and Ramamohan Paturi. On the Exact Complexity of Evaluating Quantified k-CNF
• Thore Husfeldt and Nina Taslaman. The exponential time complexity of computing the probability that a graph is connected [arxiv 1009.2362]
• Britta Dorn and Ildikó Schlotter. Multivariate Complexity Analysis of Swap Bribery [PDF at Schlotter’s web page]
• Katarína Cechlárová and Ildikó Schlotter. Computing the deficiency of housing markets with duplicate houses [PDF at Schlotter’s web page]
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Improved FPT algorithm and quadratic kernel for Pathwidth One Vertex Deletion
• Yixin Cao and Jianer Chen. Weighted Cluster Editing: Kernelization based on Edge-Cuts [arxiv 1008.4250]
• Jesper Nederlof and Johan M. M. van Rooij. Inclusion/Exclusion Branching For Partial Dominating Set and Set Splitting
• Nadja Betzler, Robert Bredereck and Rolf Niedermeier. Partial Kernelization for Rank Aggregation: Theory and Experiments [PDF at Betzler’s web page]
• M. Praveen. Small Vertex Cover makes Petri Net Coverability and Boundedness Easier [arxiv 1009.2577]
• Yngve Villanger. Proper Interval Vertex Deletion
• Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo. Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
• Sylvain Guillemot, Christophe Paul and Anthony Perez. On the (non-)existence of polynomial kernels for Pl-free edge modification problems [arxiv 1007.4011]
• Christian Hoffmann. Exponential Time Complexity of Weighted Counting of Independent Sets [arxiv 1007.1146]
• Michael Fellows, Serge Gaspers and Frances Rosamond. Parameterizing by the Number of Numbers [arxiv 1007.2021]
• M A Abhimanyu, B Radheshyam, Chintan Rao H, Venkata Koppula, Neeldhara Misra, Geevarghese Philip and Ramanujan M.S..On the Kernelization Complexity of Colorful Motifs

Sweet circumstance! The huge positronic brain that I built in my cellar to compute the algorithmic movie ranking FilmRank is still warm. So when I saw this list of

• 25 classic science fiction movies that everybody must watch at io9

how could I resist to submit the question to the electronic abomination? After all, left to its own devices, the machine might otherwise become sentient in its idle time and decide to take over the Internet. And then. The. World.

“Can you give me the 25 most important sci-fi movies, ranked by FilmRank.”

There was a moment’s expectant pause whilst panels slowly came to life on the front of the console. Lights flashed on and off experimentally and settled down into a businesslike pattern. A soft low hum came from the communication channel.

“Difficult. What is this Sci-Fi of which you speak?”

To decide what is Sci-Fi and what isn’t, I again fell back on IMDB, namely on the genre labelling. Now, many movies list dozens of genres, so I arbitrarily chose to only recognise the two or three that make it to the front page.

This leads to some decisions that I disagree with: For example, the hive-mind that is IMDB users don’t classify Der Golem, wie er in die Welt kam (1920) as Sci-Fi, so it doesn’t make the list. On the other hand, Superman (1978) is in there. Even more unbearably, the The Rocky Horror Picture Show would have made a respectable 24th place, had it not been classified as Comedy/Musical.

But of course, the conceit of this whole project is to minimise my influence, so the list is what it is. I defer completely to my algorithmic overlord, and the human life-forms it has absorbed into its computational matrix.

So here it is, presented with infinite majesty and calm. Those movies that appear on both the FilmRank list and on io9’s I have marked with a star.

1. Star Wars (1977)
2. 2001: A Space Odyssey (1968) [*]
3. Metropolis (1927) [*]
4. Frankenstein (1931)
5. A Clockwork Orange (1971)
6. The Terminator (1984)
7. E.T.: The Extra-Terrestrial (1982) [*]
8. Star Wars: Episode V – The Empire Strikes Back (1980) [*]
9. Alien (1979) [*]
10. The Matrix (1999) [*]
11. THX 1138
12. Blade Runner (1982) [*]
13. Aliens (1986)
14. Superman (1978)
15. Back to the Future (1985) [*]
16. Gojira (1954)
17. Bride of Frankenstein (1935)
18. Terminator 2: Judgment Day (1991) [*]
19. Star Wars: Episode VI – Return of the Jedi (1983)
20. Planet of the Apes (1968) [*]
21. Jurassic Park (1993)
22. The Day the Earth Stood Still (1951) [*]
23. Close Encounters of the Third Kind (1977)
24. RoboCop (1987) [*]
25. Invasion of the Body Snatchers (1956)

Comments? The FilmRank list is a lot more “classical,” which is an artefact of the algorithm. (The damping factor is 0.50.) For example, the spectacularly good District 9 doesn’t have a chance. I note with surprise that Back to the Future appears on both lists, even though it probably wouldn’t make my own. Oh, and FilmRank has Gojira, so it’s full of win. Now, I wonder which parameters I must tweak to get Reptilicus (1961) on the list…

In August 2010, an enormous public relations opportunity fell into Computer Science’s lap, when Vinay Deolalikar’s attempt to separate P from NP resulted in unprecedented internet interest and media coverage.

I think it was a big success. (The outreach. Not the proof.) There are lots and lots of people who are interested in this stuff, and we should tell them more about it. Here are some reflections on my own tiny involvement.

Timeline

• On Sunday, 8 August, email from a former student pointed me to Greg Baker’s blog, which had announced Deolalikar’s manuscript the day before. Within two days, and perhaps largely due to Richard Lipton’s enthusiasm, hundreds of blog comments are written, and it is clear to me that this story could make it into regular news. Not because of the proof, but because of the collaborative model.
• Tuesday, 10 August, I write a crisp but comprehensive summary to the communications department at ITU Copenhagen, explaining the case, and my reasoning for why and how this could attract the attention of journalists. Luckily, they bite, and start pitching the story to Danish media.
• Wednesday, 11 August. The communication department gets back to me. Both venues I had in mind accepted: Danish public radio DR P1 Morgen and the weekly paper Weekendavisen. (I have appeared in both of these places previously, listen to the former and subscribe to the latter, so they are aimed at the demographic I am in.)

  Meanwhile, the story itself got even better: a wiki page at polymath has been created to discuss the proof. On the other hand, Deolalikar’s proof doesn’t fare too well because of problems with the structure of random k-Sat.

• Thursday, 12 August. I spend well over an hour in the morning talking to a journalist from DR P1 Morgen on the phone, to prepare for a radio interview for Saturday. This is how it works: she spends a lot of time and energy asking very good question and exploring various angles, actually really trying to understand what’s going on, scientifically. She then writes a brief intro and a list of possible questions and angles to the host of the radio show, who will conduct the broadcast interview.

  In the afternoon, I do basically the same hour-long phone interview with a journalist from Weekendavisen. WA’s deadline is Wednesday evening, so we aim for a longer piece in the paper’s science section next week.

  Meanwhile, Neil Immerman points to big problems with the finite model theory part of Deolalikar’s proof.

• Saturday, 13 August. I take an early train to Copenhagen, and enter the DR building. I’ve done this part once before, so I already feel like a jaded member of the chattering classes, going through the motions like a frequent airplane traveller through security. I announce my presence at the reception, receive a badge, and an assistant picks me up to lead me to a waiting area. The assistant gives me a brief chance to summarise what I’m going to talk about, probably this just to loosen my tongue. There’s coffee and morning papers. (Nothing about Deolalikar. I had hoped some major newspaper would falsely run the angle that “Outsider solves major math riddle, embarrassing reluctant ivory tower academics.” But no such luck.) After half an hour of waiting I’m ushered into the studio and get a bit more than the previously agreed 8 minutes to say the word algorithms as often as I can.
  • DR P1 Morgen summary (includes audio)

  I think it went well, though I still haven’t had the guts to hear it.

• Tuesday, 17 August. I should have had the Weekendavisen article for review by now, but WA has changed its overall design, including the software, so everything is running very late. (But they did change the body typeface to Garamond, making WA officially the best typeset paper on the planet. So all is forgiven, and my subscription renewal is guaranteed.)
• Wednesday, 18 August. I get the WA article, and I’m quite impressed. The angle is via Wiles and Perelman, then to collaborative software, outsourcing, and what I call the triumph of amateurism. Even some of my concerns about basic research funding are briefly touched upon, mathoverflow and polymath are mentioned. I know full well that I can’t change the angle anyway, but there are of course numerous problems with the details. Predictably, the article writes “mathematics” whenever it should write “computer science.” I spend some more time editing and send my changes back, fingers crossed.
• Thursday, 19 August. I get WA with my regular Swedish paper in the morning. The article is the front piece for the science section. (WA has no electronic edition I can link to. You have to buy it.)

Even though this all took a lot of time and energy, I’m pretty happy. The angle, i.e., collaborative math, turned out to be just right, and is the same that several other media have chosen. But remember this is all just a platform to say P, NP, algorithms, and complexity in public media as often as possible.

But it’s Wrong!

When doing something like this, know from the beginning that you have no bandwidth. You cannot explain anything. You have no time, and you have no visual aids. News media are neither very good at, nor even interested in, explanation of concepts. So don’t. And refrain from unnecessary precision. I wish I would learn.

The summary of the radio show includes the following (in my translation):

P versus NP is a scientific hypothesis that can be translated, very simplified, to the claim that there are problems that can be solved, and problems that can’t be solved.

Now, this is of course false. There are problems that cannot be solved, whole classes of them. Everything in UNDECIDABLE is undecidable no matter how much time you invest, and the problems in EXPTIME are infeasible in the sense that even though algorithms exist, they don’t run in polynomial time; we know P differs from EXPTIME by the time hierarchy theorem.

Would it have been worth correcting? No. The whole P versus NP problem loses a lot of its appeal once you start with “even though this claim is proved for some problems, there is a certain class of problems called NP for which this is not yet known.” Of course, the trick is instead to establish NP via verification versus computation, and I tried that both in the radio and the paper using Sudoku.

But the important thing is that none of this is the point. My mission is not to ventilate the correct definition of NP; anybody really interested can look it up on Wikipedia. I’ve had students who took whole classes from me who blissfully live in this misunderstanding. Those I try to correct, and sometimes successfully. But for the general public, I think this is unnecessary complication that only weakens the story.

I did get them to sneak “very simplified” in the summary, out of scientific integrity, and left it at that.

I can see that the New York Times currently has the same problem. A pretty good article from 16 August now has the following retraction:

Correction: August 21, 2010.
An article on Tuesday about a proposed solution of a classic mathematical formula called P versus NP described NP incorrectly and misidentified the location of the CERN physics research center. NP stands for the class of problems for which solutions can be verified relatively quickly, not the class of problems that are difficult to solve but easy to verify. And the CERN laboratory is near Geneva, not in Zurich.

Got it? I don’t.

The WA article contains a bigger mistake, and one I feel bad about. In my translation:

A 9×9 Sudoku is just big enough to entertain us during our morning coffee. But if we played Sudoku with letters instead of numbers, the number of combinations would be so huge, that all supercomputers on the planet would need until the end of the Universe to find a solution. “Unless, of course, there’s a really clever way to solve Sudokus that we just haven’t discovered yet,” adds Thore Husfeldt.

The usual Sudoku is a P-problem: it’s possible to write a recipe, an algorithm, to solve it. The big Sudoku is an NP-problem, one of the tasks mathematicians called Herculean, where you can use infinite time to check all combinations without ever finding the solution, but where you could immediately verify one if you had found it.

Vader voice: Noooo! This is the scientifically most ambitious part of the article, and contains crippling mistakes. All I can say is that it was worse when I got the first draft. Some of my edits made it (for example, it now no longer says that an 18×18 Sudoku contains twice as many cells as a 9×9 Sudoku.) Others, as you can see, didn’t. For completeness:

1. Sudoku is always NP-hard. The small ones are merely small enough that systematic exploration is still feasible. But for NP-hard problems, solution time presumably grows exponentially with problem size, so even the seemingly harmless increase to 25×25 alphabet Sodoku destroys any hope of solving it. (There’s more to say about the hardness of Sudoku. Maybe for another post.)
2. Even a 25×25 Sudoku still does not use infinite time. It’s a finite problem, after all. To a mathematician, 25×25 Sodoku is an easy problem, because the number of steps it takes is a small integer “close to zero”. But to a computer scientist, it’s important that this finite number of steps exceeds the computational power that remains in the universe for the rest of its lifetime. Yes, even if you install Ubuntu.
3. “Herculean” was a term suggested in Donald Knuth’s Herculean efforts to give NPC a better name.

Would another round of edits have made a difference? Probably. But because of the narrow schedule imposed by WA’s new layout engine, it was not to be. On the other hand, the new layout means I get to see my name in beautiful Garamond. I retain a weak spot for Aestheticism from my younger days, so I guess I will let the pleasures of form triumph over the constraints of content.

What I Should have Done

Next time, I will try with Impagliazzo’s five worlds, or rather two of them.

When trying to explain P versus NP, talk about Algorithmica versus Cryptomania instead. Morally, it’s the same problem, you need to worry about average-case complexity to see the difference. But it’s so much nicer to talk about. Algorithimica is a country in which you have Star Trek computers (or Skynet, depending no how much of an optimist you are), no mathematicians, etc. In Cryptomania you have crypto. We know that we live in one of these worlds (there are a few more), but we don’t know which. I think that’s a good way of putting it, because it conjures images. So that’s what I’ll try next time.

I just have to wait until the next proof attempt.

I still haven’t quite absorbed the fact that the natural science students found me worthy of their pedagogical prize 2007, but now it seems I get the university-wide prize as well: Lunds Universitets Studenkårer (Lund University’s Student Unions) will be honouring me with their prize for outstanding teaching on Oct 19.

Nomination

Part of the nomination is now on-line at the University
webspace. Translating that into English gives something like this:

In his role as Computer Science teacher, Thore Husfeldt has proved that enthusiasm actually can be contagious. Like no other he manages to create motivation for learning and enthusiasm for the topic in his students. This may hinge the fact that he really is a fiery spirit and has stated he sees teaching as the most fun thing he does at University.

Pedagocial development is an issue that lies close to Thore’s heart. Apart from being a driving force in development Thore has also shown enthusiasm and participation in the development of quality measures, models that depend on the central role of examination for learning.

Thore makes time for his students. His door is seldom closed. It’s never a problem if students need an extra seminar or explanation, Thore is always there for them.

What can I say? First, I need to express my enormous gratitude to whatever students fought for my nomination in whatever covens these things are decided. I have always tried to take the right people seriously, and engage politically able and rational students in honest and well-reasoned debate. This costs a lot of easy points, but has made me popular with some other fiery spirits who throw some weight around. It’s supremely satisfying to see this strategy validated.

Second, there are a lot of teachers better than me who don’t get recognised. Students: do you bloody job and nominate the right people. They need you.

Third, I’m happy to see myself awarded for things that are really important to me, and not so trivial. (I’m pretty sure you can be a terrible teacher while being available and enthusiastic. I understand why these criteria are on the list, since they are necessary. But they don’t make you a good teacher.) But the nomination does mention my stubborn insistence on Good Exams, a topic that is really important to me. The fact that the student union recognises this is great, and verifies one of my dogmas: the idea that students prefer fuzzy exams is a myth.

I have never ever taken a pedagocial course, and most of those I’ve looked at disgusted me. But I have copied all the best teachers I’ve ever met, and anything I do right I have shamelessly stolen from them: from people who derive pleasure from explaining difficult things really, really well.

Full nomination

Update: Here is the full text of the nomination.

Lunds Naturvetarkår (LUNA) nominerar härmed Thore Husfeldt, institutionen för datavetenskap, till Lunds universitets pedagogiska pris 2007.

Thore Husfeldt har i sin gärning som lärare i datavetenskap visat att entusiasm faktiskt kan smitta av sig. Som ingen annan förmår han skapa inlärningsvilja och intresse för ämnet hos sina studenter. Detta beror kanske på att han verkligen är en eldsjäl och att han uttalat ser undervisningen som det roligaste han gör på universitetet.

Att undervisa i datavetenskap är svårt, om detta kan många vittna. Dåligt undervisad datavetenskap blir obegriplig p.g.a. sin extremt tunga teoretiska bas. Här har Thore en enorm förmåga att förklara svåra teoretiska resonemang på ett begripligt sätt. Mycket av detta beror på att han gärna sätter teorin i sitt sammanhang. De datavetenskapliga teoretiska modellerna har en avgörande betydelse för alla vetenskaper som behandlar stora statistiska underlag, bland annat inom naturvetenskap, samhällsvetenskap och ekonomi. Detta klargör Thore i sin undervisning på ett utmärkt sätt. Detta betyder inte att Thore trivialiserar sin vetenskap och dess teori, tvärtom. Ärlighet är ett nyckelord i Thores undervisning.

Om ett kursmoment är svårt så säger han det. Om ett kursmoment är tråkigt säger han det. Thore anser att detta är en betydligt bättre motivationsteknik än att trivialisera svåra och tråkiga moment. Enkelhet och tydlighet är andra viktiga begrepp i Thores pedagogik.

Det har sagts att Thores kurser inte liknar varandra från termin till termin. Detta beror på att Thore kontinuerligt utvecklar kursinnehållet och sin egen pedagogik. Han har varit drivande i arbetet med bolognaanpassning av utbildningen och grundutbildningens upplägg. Thore har även hållit i utbildning för laborationsassistenter och forskningsassistenter. Det pedagogiska utvecklingsarbetet är något som ligger Thore varmt om hjärtat.

Förutom att ha varit drivande i utvecklingsarbetet har Thore också visat entusiasm och engagemang i att utveckla kvalitetssäkringsmodeller för utbildningen. Kvalitetssäkringsmodeller som tar fasta på examinationens centrala roll för lärandet.

Thore har länge påpekat att utbildning ges för lite utrymme och status i förhållande till forskning, men att forskning och utbildning går hand i hand. Det är särskilt tydligt inom datavetenskapen där utvecklingen går hejdlöst snabbt, och en lärare som är borta från forskningen en tid förlorar möjligheter att hänga med i utvecklingen. Thore för en “kamp för att höja nivån på undervisningen” vilket bland annat innebär att forskande lärare aktivt deltar i undervisningen. Thore har bland annat arrangerat “algoritmseminariet”.

Thore tar sig tid för sina studenter. Hans dörr är sällan stängd. Om studenterna har behov av ett extra seminarium eller en genomgång till är det aldrig ett problem utan Thore ställer upp.

Att Thore uppskattas av sina studenter har bland annat manifesterats i att han har mottagit datalogernas pedagogiska pris “Golden Keyboard Award” samt LUNAs pedagogiska pris.

Detta sammantaget gör att vi rekommenderar varmt att Thore Husfeldt tilldelas Lunds universitets pedagogiska pris för 2007.

I especially like the third paragraph.