THI2 Probeklausur 2

1

Wenn $L$ in $NP$ dann $L$ in $ExpTime$

Ja?
⇒ Die Exponential Time Hypothesis ?

Wenn $L,L^{\prime }\in NP$ dann gilt $L{\le }_p{L}^{\prime }$

Nein da P eine Untermenge von NP ist und wenn $L^{\prime }\in P$ dann kann dieses nicht auf ein NP Problem reduzieren.

Wenn $L{\le }_p{L}^{\prime }$ und $L^{\prime }{\le }_p{L}^{\prime \prime }$ dann auch $L^{\prime }{\le }_p{L}^{\prime \prime }$.

Ja da:

Wenn $L{\le }_p{L}^{\prime }$ gilt dann gibt es ein in polynomialzeit brechebares
$f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ sodass gilt $\forall w\in L⟺f(w)\in L^{\prime }$.

Wenn $L^{\prime }{\le }_p{L}^{\prime \prime }$ gilt dann gibt es ein in polynomialzeit brechebares
$g:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ sodass gilt $\forall w\in L^{\prime }⟺g(w)\in L^{\prime \prime }$.

Daher gibt es ein
$h:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$
$w\to g(f(w))$
sodass gilt: $\forall w\in L⟺h(w)\in L^{\prime \prime }$.
$h$ ist in polynomialzeit da f und g in polynomialzeit sind.

3.

a)

i)

Hamilton Path: Ja: b → a → d → c → e → f → g
Hamilton Kreis: Nein

ii)

Hamilton Path: Ja: a → d → e → g → f → h → c → b
Hamilton Kreis: Ja: a → d → e → g → f → h → c → b → a

iii)

Hamilton Path: Nein
Hamilton Kreis: Nein

b) Hamilton Path ${\le }_p$ Hamilton Cycle

Gegeben:
Eine Maschine M die für ein ungerichtetem Graph zurück gibt ob es einem Hamilton Kreis gibt.
Eine Sprache L die alle ungerichtetem Graphen G enthält für die es ein Hamilton Path gibt.
Gesucht:
Eine Funktion $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ die in Polynomialzeit den Graph so umwandelt das
$\forall G\in L\Rightarrow f(G)\in L(M)$ and $\forall G\notin L\Rightarrow f(G)\notin L(M)$

f sieht wie folgt aus:
Input: $G=(V,E)$
Output: $G^{\prime }=(V\cup \{v\},E\cup \{\{v_1,v\},\{v_2,v\},...\{v_n,v\}\})n=|V|$
Es wird eine weiterer Vertex hinzugefügt die eine Kante mit jeder anderem Vertex hat.

Beweis:
Wenn $G\in L\Rightarrow f(G)\in L(M)$
Wenn es im Graph ein Hamilton Path gibt hat dieser Graph zwei Vertecies die den Anfang und das Ende des Path beschreiben. Die neue Vertex verbindet diese beiden und schlißt so den Kreis.

Wenn $G\notin L\Rightarrow f(G)\notin L(M)$
Wenn es im Graph keinen Hamilton Path gibt ist dieser entweder nicht verbunden oder es gibt eine Vertex die mehr als einmal verwendet werden müsset um einen Path zu bilden.
Wenn man nun eine Vertex hinzufügt, die eine Verbung zu jeder anderen Vertex hat könnte es nun einen Hamiltion Path geben, aber es ist nicht möglich das es einen Kreis gibt, da nur eine Verbindung zwischen zwei nicht verbunden Bereichen nie einen Kreis bildet.

Auch die andere Richtung?

Hamilton Cycle ${\le }_p$ Hamilton Path

4. Vertex Cover ${\le }_p$ Directed Feedback Vertex Set

5.

Definition

Eine Sprache $L$ heißt NP-schwer, wenn für alle $L^{\prime }\in NP$ gilt $L^{\prime }{\le }_{p}L$

Daraus schießt sich das Lemma aus der Vorlsung:
Das ein Probelm NP-schwer ist sobald es auf ein anderes NP-schweres Problem in polynomialzeit Reduzieren kann.

SAT ${\le }_p$ Wortproblem
Wir müssen also eine funktion $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ finden die M und w in ein SAT Term umwandelt, sodass das Ergebnis des Wortproblem auf M mit w immer das Ergebnis wie der SAT Term hat.

6. Hamilton Path ${\le }_p$ SAT

$G=(V,E)$

Variablen:
$\{e_{v,u}\in \{0,1\}|\{v,u\}\in E\}$

Der Path enthält jede Vertex exact einmal:
${\bigwedge }_{v\in V}{\bigvee }_{\{v^{\prime },u\}\in E{v}^{\prime }=v}{e}_{v,u}\wedge {\bigwedge }_{\{v^{\prime },u^{\prime }\}\in E/\{v,u\}{v}^{\prime }=v}\neg e_{v,u^{\prime }}$
Der Path hat immer genau ein nachfolger bis auf zwei Vertcies:

\bigvee_{v_{start} \in V} \bigvee_{v_{end} \in V} \bigwedge_{\{v, u\} \in E / \{v_{start}, v_{end}\}} \neg e_{v, u} \vee \bigvee_{\{v', u\} \in E \; v = u} e_{v', u'} \land \bigvee_{\{v'', u''\} \in E / \{v, u\} \; v'' = u} \neg e_{v'', u''}$$ ![[Pasted image 20240714150947-0.jpg|700]]