Ian Gent, Chris Jefferson and Peter Nightingale have shown that the n-Queens puzzle (given a chessboard of size n x n, place n queens so that no two queens attack each other) is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30. See these two articles: “Simple” chess puzzle holds key to $1m prize and n-Queens Completion is NP-Complete for further details.
The Centre for Interdisciplinary Research in Computational Algebra (CIRCA) was established in 2000 to foster new and existing collaborative research between members of the Schools of Computer Science and of Mathematics and Statistics in the area of computational abstract algebra.
The Centre undertakes mathematical research with computer assistance, develops new techniques for computation in abstract algebra and develops and distributes software implementing these techniques. This work is supported by research grants from the EPSRC, the Leverhulme Trust, the British Council, the European Commission and the Royal Society of Edinburgh.
The Centre also organises conferences, seminars and training courses and coordinates the international efforts to develop maintain and promote the GAP (groups, algorithms and programming) software package, a leading integrated system for computational discrete mathematics and algebra.
News and Events
Groups St Andrews 2017 in Birmingham took place on August 5th-13th. This is the tenth in the series of Groups St Andrews Conferences which have been held every four years from 1981. The main speakers were Michael Aschbacher (Caltech), Pierre-Emmanuel Caprace (Université Catholique de Louvain), Radha Kessar (City, University of London) and Gunter Malle (TU Kaiserlautern). One hour speakers were Tim Burness (Bristol), Vincent Guirardel (Université de Rennes 1), Harald Helfgott (Göttingen), Andrei Jaikin-Zapirain (Universidad Autónoma de Madrid) and Donna Testerman (École Polytechnique Fédérale de Lausanne). The organisers are Colin Campbell, Martyn Quick, Edmund Robertson and Colva Roney-Dougal together with Chris Parker from Birmingham.
The conference has been followed by a satellite event – a tutorial on the computational algebra system GAP on August 13th-14th. It has been organised by Alexander Konovalov together with Sergey Shpectorov from Birmingham. On Sunday Alexander Konovalov taught the Software Carpentry lesson “Programming with GAP”, and on Monday Markus Pfeiffer explained various aspects of using GAP effectively and demonstrated the GAP Jupyter interface being developed in the OpenDreamKit project.