Exjobbsförslag från företag

Detta är ett uppsatsförslag hämtat från Nationella Exjobb-poolen. Klicka här för att komma tillbaka till samtliga exjobbsförslag.

Förslaget inkom 2011-08-22

Research Master’s Thesis Projects in Theoretical Computer Science

OBS! ANSÖKNINGSTIDEN FÖR DETTA EXJOBB HAR LÖPT UT.
FORMULA HARDNESS AND SAT SOLVING

Given a logic formula, is it possible to set its variables in such a way that the formula is satisfied? This simple looking problem has been on centre stage in theoretical computer science ever since the field got started some 40 years ago, and was recently named as one of the Millennium Prize Problems comprising some of the major challenges for all of mathematics in the 21st century. Today, students of computer science worldwide learn in their introductory theory courses that this so-called SAT problem is what is known as NP-complete, and therefore is very, very hard in practice.

Interestingly, practioners take a somewhat different view. During the last 10-15 years, SAT has developed from a problem of mainly theoretical interest into a practical approach for solving applied problems. Enormous progress in performance has led to satisfiability algorithms, so-called SAT solvers, becoming a standard tool for solving real-world problems with millions of variables in the context of, for example, hardware and software verification, electronic design automation, artificial intelligence, operations research, and bioinformatics. The theory of NP-completeness did not quite go away, however — for all these SAT solvers there are also known examples of tiny formulas with just a couple of hundred variables that make them fail miserably.

How can modern SAT solvers be so good in practice? And how can one know for a particular formula whether it will be hard or easy? These are the kind of questions we want to study in these Master's thesis projects, using a mix of theoretical research and practical experiments.

The projects are intended to give students a feel for what research in theoretical computer science is like, while at the same time focusing on concrete problems of huge practical importance. Apart from the Master's thesis itself, we hope that the results will also be published as (parts of) papers in leading scientific conferences and/or journals in the field.

This is all part of a larger EU-funded research project with international collaborators, which will be recruting PhD students for appointments starting in August 2012. So if you are thinking about going into research, this should be an excellent opportunity to try it out.

For more information, see the webpage http://www.csc.kth.se/~jakobn/openings/#msc or send an e-mail to [email protected].


  GÅ TILL XJOBB.NU FÖR FULLSTÄNDIG INFO OM DETTA EXJOBB




Informationen om uppsatsförslag är hämtad från Nationella Exjobb-poolen.