Modulo Errors

I’ve now converted the majority of my game theory project to E2nodes, through a dedicated account. The content has been significantly rearranged for some topics, to make better use of E2’s nodal structure; hopefully individual entries stand alone a bit better so that it isn’t necessary to read the entire report to understand what’s going on. I’ll also be adding more content to that account to clarify or expand upon the original document.

Despite my usual resistance to applied maths, yesterday’s BICS seminar sounded worthwhile, and turned out to be very good- Keith Briggs of BT gave a talk entitled Some practical experiences of hard graph problems. Graph Theory isn’t part of our syllabus, which seems a shame, as the concepts are simple- colouring, cliques etc. - but the questions difficult.

Much of the talk discussed the validity of results on infinite graphs when applied to smaller (and hence computationally feasible) ones: in particular, obtaining good bounds on clique and chromatic numbers. Towards the end, the reduction of graph problems to the satisfiability problem in propositional logic was mentioned. Obviously, the possibility of such reductions is a defining characteristic of NP-hard problems (and one I’ve recently been studying), but it’s good to see that this is of practical merit rather than simply theoretical interest.