Practical Research Projects - Project Description
Project Description
This is a description of a Practical Research Project associated with the PREP course
Project Title
NP-completeness of puzzles.
Quarter
Q1 2010Responsible
Second level advisor: Peter Bro Miltersen.
Aims
The solvability of Sudoku and other puzzle type problems has been shown to be NP-complete.
First, the student should get an overview of the existing results regarding NP-completeness of different puzzles. This requires the student to search the research literature for these results and structuring the obtained information. Furthermore the student should identify a number of puzzles for which NP-completeness is suspected, but not currently known.
Second, the student will examine problems identified above as not currently shown to be NP-complete. The student will examine possible approaches to obtaining such a result, and evaluate their potentials. It is expected there is a reasonable chance that the student may be able to obtain a new NP-completeness result.
The student must write a report with the results of both parts.
Learning Outcome
- The student will learn to read and understand technical scientific papers.
- The student will learn to express and discuss ideas using relevant terminology.
- The student will learn to take initiative with respect to the direction of the project.
- The student will learn to formulate, write and present technical results.