# Programming
Project Topics

## Below
are
some suggestions of mine; you are welcome to come up with your own as
well, but in any case, these are a starting point, and the development
of a topic is an interactive process between the supervisor/s and the
student. The main issue is to come up with a project which can be done
in one semester, and so the scoping of the project is quite important.
A programming project for an M.App.Sci(IT) project does not have to aim
for publishable research, but involves the development of some novel or
interesting
application (such as a tool for a research project). Some of these
topics are also suitable for summer projects, or just for investigaion
as and when you feel like it.

An
investigation of the use of SAT solvers

## At IJCAI in August 2005, I heard
about
the amazing progress that has occurred recently in solvers for the 3SAT
problem, which can now solve problems with around 1,000,000 variables
in them. This is large enough to cope with many realistic large
problems. It then suggests that one way to solve your favourite
NP-complete problem is to use such a SAT solver (many of which are
available as open source) as the base engine and to use polynomial
reductions from say the travelling salesman or vertex cover problem to
3SAT as the basis of an implementation. The aim of this project is to
determine how feasible this approach is by means of a series of
experiments.