Seminar über Algorithmen und Komplexität, SS 2007

Inhalt

Das Seminar hat behandelt die Komplexität schwieriger Probleme. Die meisten algorithmischen Probleme sind NP-schwer oder noch schwieriger (PSPACE-vollständig). In diesem Seminar sollen ausgewählte Reduktionen, die zum Beweis der Schwierigkeit führen, besprochen werden.

Ablauf

Wenn dieser Termin nicht eingehalten wird, wird der Vortrag abgesagt und kein Schein vergeben.

Die regelmäßige Teilnahme gehört selbstverständlich ebenfalls zu den Teilnahmebedingungen.

Themen

• Hamilton-Kreis auf Gittergraphen (Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Paths in Grid Graphs. SIAM J. Comput. 11 (1982), 676-686)
  
• Planares 3-SAT (D. Lichtenstein; Planar formulae and their uses. SIAM Journal on Computing 11 (1982), 329-343; siehe auch D. E. Knuth and A. Raghunathan: The problem of compatible representatives. SIAM Journal on Discrete Mathematics 5 (1992), 422-427.)
  
• Das 15er-Spiel (D. Ratner, M. Warmuth, Finding a shortest solution for the (nxn)-extension of the 15-puzzle is intractable, J. Symbolic Computation 10 (1990), 111-137.)
  
• TETRIS ist PSPACE-schwer (Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell, ``Tetris is Hard, Even to Approximate,'' International Journal of Computational Geometry and Applications, volume 14 (2004), pages 41-68).
• Kieselsteinprobleme sind PSPACE-schwer (J. R. Gilbert, T. Lengauer, R. E. Tarjan)
• GO ist PSPACE-schwer (Lichtenstein und Sipser, Journal of the ACM 27 (1980), 393 - 401)
• SOKOBAN ist PSPACE-schwer (J. Culberson, in: Proc. Int. Conf. on FUN with Algorithms, S. 76-74, 1999; vergleiche auch Dor und Zwick, SOKOBAN and other motion planning problems
  Computational Geometry: Theory and Applications 13 (1999), 215-228.)
• RUSH-HOUR is PSPACE-complete, or Why you should generously tip parking lot attendants, Theoretical Computer Science 270 (2002), 895-911 (Flake und Baum)
• Gill Barequet , Matthew Dickerson, and David Eppstein, On triangulating three-dimensional polygons, Computational Geometry-Theory and Applications, Volume 10, Issue 3, June 1998, 155-170.
• J. Ruppert and R. Seidel, On the difficulty of triangulating three-dimensional non-convex polyhedra. Discrete Comput. Geom. 7 (1992), 227–253.
• SUDOKU ist NP-schwer. (im Zusammenhang mit lateinischen Quadraten, Charles Colbourn) (Yato and Seta).
• Dame ("checkers") ist EXP-TIME-schwer (J. Robson. N×N checkers is EXPTIME complete. SIAM Journal on Computing 13 (1984), 252--267)
• Domino (Therese Biedl: The complexity of domino tiling. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05), pages 187-190, 2005. Siehe auch Technical Report CS-2005-09, University of Waterloo.
  Siehe auch Don Sheehy, The Complexity of Domino Tiling Problems, 2005, Princeton University.
• Möbelrücken (Hopcroft, Schwartz, Sharir: On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the "Warehouseman's Problem",  International Journal of Robotics Research 3 (1984), 76-88).
• Minesweeper ist NP-schwer (Kay, Math. Intelligencer, 2002), siehe auch http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw1.pdf
  
• Triangulierung in einem vorgegebenen geometrischen Graphen ist NP-schwer (André Schulz 2005).
• Graphenfärbung: Graphen mit Maximalgrad 4 (M. R. Garey, D. S. Johnson, and L. Stockmeyer, "Some Simplified NP-Complete Graph Problems", Theoretical Computer Science 1 (1976), 237-267)
• Graphenfärbung: 3-Färbung planarer Graphen

Programm

Donnerstags, 16 Uhr, Raum 055

Last modified: July 26, 2007