Dein Leben (Problemsammlung)

Berechenbarkeit

Unterteilt in 4 Kategorien:

• entscheidbar
• unentscheidbar

  (Simplifizierung, da man nachgucken möchte ob ein Problem unentscheidbar ist !Heißt aber vllt. semi-entscheidbar!)

• semi-entscheidbar
• Nicht semi-entscheidbar

Entscheidbar

Sind nicht viele :D

• Eingabe TM M, Wort w. Frage: Schreibt M auf der Eingabe w jemals ein Nicht-Blanksymbol auf das Band? | Tutorium 03
• $L_2 =$ { $\langle M \rangle w \mid M$ bewegt auf der Eingabe $w$ den Kopf nie nach links} | Übung 03
• $H_{\le 97} =$ { $\langle M \rangle w \mid M$ hält auf Eingabe $w$ und zwar nach höchsten 97 Schritten} | Tutorium 04
• $L_1 =$ { $\langle M \rangle \mid M$ hält nicht in weniger als $2^{|\langle M \rangle|}-1$ Schritten auf $\langle M \rangle$} | Übung 04
• $H_{42} =$ { $\langle M \rangle \mid$ Auf jeder Eingabe hält M nach höchstens 42 Schritten} | Übung 04
• PKP über dem unären Alphabet $\{a\}$. | Tutorium 06
• PKP $((\mathbb{N}, +, 0))$ | Übung 06
• PKP $((S_n, \circ, id))$ | Übung 06

Nicht Entscheidbar

Alle Probleme die Nicht Entscheidbar sind (Sie können ggf. noch semi-entscheidbar sein wenn sie unten aufgelistet sind):

Ich nenne hier keine Komplemente, da wie ihr bestimmt wisst, die Komplemente von unentscheidbaren Problemen auch unentscheidbar sind.

• Diagonalsprache (Mithilfe des Diagonalargument) | VO
• Halteproblem (H) | VO
• spezielle Halteproblem ($H_\epsilon$) | VO
• $L_{17} =$ { $\langle M \rangle \mid$ M berechnet bei Eingabe der Zahl 17 die Zahl 42} | VO
• Allgemeine Halteproblem | VO
• Hilberts 10. Problem ($N =$ { $p \mid p$ ist ein Polynom mit einer ganzzahligen Nullstelle }) | VO
• Das Problem, ob ein ganzzahliges Polynom eine ganzzahlige Nullstelle hat, ist unentscheidbar. | VO
• $Dioph(M)$ | VO
• $ExpDioph(M)$ | VO
• Postsche Korrespondenzproblem (PKP) | VO
• MPKP (Modifizierte Postsche Korrespondenzproblem) | VO
• Spiel-des-Lebens (Anfangskonfiguration und aussterben) | VO
• $L_{never} =$ { $\langle M \rangle \mid M$ hält auf keiner Eingabe } | Tutorium 03
• $L_{110} =$ { $\langle M \rangle \mid M$ hält auf 110 nicht} | Tutorium 03
• $L = \{ 1^k \mid k \in \mathbb{N}, M_k$ akzeptiert $1^k$ nicht $\}$ | Tutorium 03
• $L_1 =$ { $\langle M \rangle \mid M$ akzeptiert genau 42 Wörter} | Übung 03
• Gegeben eine Turingmaschine $M$, ist $L(M)$ nicht leer? | Tutorium 04
• Gegeben eine Turingmaschine $M$, hält $M$ auf der Eingabe 110? | Übung 04
• $H_{\ge 97} =$ { $\langle M \rangle w \mid M$ hält auf Eingabe $w$ und zwar nach mehr als 97 Schritten} | Tutorium 04
• $L_2 =$ { $\langle M \rangle \mid f_M(\langle M \rangle)=1$ } | Übung 04
• $L_2 =$ { $\langle M \rangle \mid f_M(\langle M' \rangle)=1$ für alle TMen $M'$, die 3 Zustände haben } | Übung 04
• PKP über dem binären Alphabet $\{a,b\}$. | Tutorium 06
• $L_1 = \{ \langle M \rangle \mid M$ erreicht auf der Eingabe $w$ nie den Zustand $q_2$ $\}$ | Übung 06

Semi-entscheidbar

Alle semi-entscheidbaren Probleme (Eigentlich sind fast alle unentscheidbaren Probleme semi-entscheidbar !Außer allgemeine Halteproblem und $A_{all}$!):

• Halteproblem | VO
• Spezielle Halteproblem | VO
• $\overline{Diagonalsprache}$ | VO
• $L_{17} =$ { $\langle M \rangle \mid$ M berechnet bei Eingabe der Zahl 17 die Zahl 42} | VO
• Hilberts 10. Problem ($N =$ { $p \mid p$ ist ein Polynom mit einer ganzzahligen Nullstelle }) | VO
• $Dioph(M)$ | VO
• $ExpDioph(M)$ | VO
• Postsche Korrespondenzproblem (PKP) | VO
• MPKP (Modifizierte Postsche Korrespondenzproblem) | VO

Nicht semi-entscheidbar

Ich exkludiere hier die Probleme, wo die Komplemente semi-entscheidbaren Probleme sind. (ist ja lame sonst)

• Allgemeine Halteproblem ($H_{all}$) | VO
• $A_{all} =$ { $M$ akzeptiert alle Eingaben} | Übung 05
• $L_2 = \{ \langle M \rangle \mid M$ gibt auf jeder Eingabe 1010 aus $\}$ | Tutorium 06
• $L_1 = \{ \langle M \rangle w \mid M$ akzeptiert $w$ nicht $\}$ | Übung 06
• $L_2 = \{ \langle M \rangle \mid M$ erreicht auf jeder Eingabe den Zustand $q_7 \}$ | Übung 06
• $L_1 = \{ \langle M \rangle \mid M$ erreicht auf der Eingabe $w$ nie den Zustand $q_2$ $\}$ | Tutorium 06

Komplexität

Ich unterteile in: P, NP, NP-Complete. Für EXPTIME und PSPACE haben wir keine Probleme behandelt.

Natürlich unter der Annahme P $\neq$ NP.

P

• Sortieren | VO
• Graphzusammenhang | VO
• Kürzester Weg | VO
• Minimaler Spannbaum | VO
• Maximaler Fluss | VO
• Maximales Matching | VO
• Lineare Programmierung | VO
• GGT | VO
• Primzahltest | VO
• 2-COLORABILITY | Tutorium 08
• 2-SAT | Tutorium 09
• XOR-SAT | Tutorium 09
• DNF-SAT | Übung 09

NP

Ich nenne hier nicht Entscheidungs vs Optimierungsprobleme doppelt, wenn nicht relevant

Eigentlich ist hier alles NP-complete außer evt. Graphisomorphie (den Rest habem wir halt nicht behandelt), aber durch Satz von Ladner gibt es diesen Bereich unter der Annahme.

• CLIQUE | VO
• Knapsack (KP) | VO
• Bin Packing (BPP) | VO
• Traveling Salesperson (TSP) | VO
• SAT | VO
• 3-SAT | VO
• COLORING | VO
• SUBSET-SUM | VO
• PARTITION | VO
• Hamiltonkreis | VO
• Directed Hamiltonkreis | VO
• Graphisomorphie | VO, Übung 07
• 3-COLORABILITY | Tutorium 08
• MAXIMUM_SPANNING_TREE | Übung 08
• COMPOSITE | Übung 08
• $\{-1, 0, 1\}$-RESTRICTED_INTEGER_PROGRAMMING | Übung 08
• MATCHING $\{(G, k) \mid k \in \mathbb{N}$, G ist ein Graph und hat ein Matching der Größe k $\}$ | Übung 08
• NOT-ALL-EQUAL-SAT | Tutorium 09
• MAKESPAN-SCHEDULING | Tutorium 10
• INDEPENDENT_SET | Tutorium 10
• VERTEX_COVER | Tutorium 10
• QUADRATIC_ASSIGNMENT | Übung 10
• SET_COVER | Übung 10
• DOMINATING_SET | Tutorium 11 (Nur NP-schwer bewiesen)
• GRAPH_HOMOMORPHISM | Tutorium 11 (Nur NP-schwer bewiesen)
• SET_PACKING | Übung 11

NP-Complete

• SAT | VO
• 3-SAT | VO
• COLORING | VO
• SUBSET-SUM | VO
• PARTITION | VO
• Bin Packing (BPP) | VO
• Knapsack (KP) | VO
• CLIQUE | VO
• Hamiltonkreis | VO
• Directed Hamiltonkreis | VO
• Traveling Salesperson (TSP) | VO
• NOT-ALL-EQUAL-SAT | Tutorium 09
• MAX-3-VORKOMMNISSE-SAT | Übung 09 (Nur NP-schwer bewiesen)
• $\{-1, 0, 1\}$-RESTRICTED_INTEGER_PROGRAMMING | Übung 09
• MAKESPAN-SCHEDULING | Tutorium 10
• INDEPENDENT_SET | Tutorium 10
• VERTEX_COVER | Tutorium 10
• QUADRATIC_ASSIGNMENT | Übung 10
• SET_COVER | Übung 10
• DOMINATING_SET | Tutorium 11 (Nur NP-schwer bewiesen)
• GRAPH_HOMOMORPHISM | Tutorium 11 (Nur NP-schwer bewiesen)
• SET_PACKING | Übung 11