Seminar: Probleme in NP

Dieses Seminar ist eine Ergänzung zu den Algorithmen Vorlesungen und Komplexitätstheorie.
Wir betrachten die Welt (zwischen) P und NP genauer:
Einerseits NP-Vollsständigkeitsbeweise (z.B. Nr. 5)
und andererseits Probleme wie das Graphenisomorphieproblem (Nr. 2 oder 9)
oder Monotone Boolean Duality (Nr. 8), zu denen keine Polynomialzeitalgorithmen bekannt sind.

Mögliche Seminarthemen:

1. Exponential lower Bounds for the Length of Resolution Proofs.
2. BP-Operator and GI.
3. The Berman-Hartmanis Conjecture and Sparse Sets.
4. Function Problems
5. The NP-completeness of some Edge-Partition Problems.
   Holyer, SIAM Journal of Computation, vol 10, no. 4, p. 713-717,1981.
6. Minesweeper is NP-complete.
   Kaye, Springer vol. 22, nr. 2, 2000.
7. The complexity of Solitaire.
   Longpré, McKenzie, In proceedings of MFCS, Springer,LNCS 4708, 2007.
8. On the complexity of Dualization of Monotone Disjunctive Normal Forms.
   Fredman, Khachiyan, Journal of Algorithms 21, p. 618-628, 1996.
9. A clique Problem equivalent to Graph Isomorphism.
   Kozen, SIGACT News, 10, 1978.

 

Referenzen:

• Schöning, Pruim: Gems of Theoretical Computer Science.
• Kozen: Theory of Computation, Springer 2006.
• Papadimitriou: Computational Complexity, Addison-Wesley 1994.
• Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen, Springer 2003.