P versus NP
Satz: $P$ ist in $NP$
Es gilt $P\subseteq NP$.
Beweis A: Zu einem Entscheidungsproblem $L$ aus $P$ gibt es einen Algorithmus $A$, der $L$ entscheidet. A kann man als Verifizierer auffassen, der die zweite Eingabe $c$ einfach ignoriert. Damit ist $L$ auch in $NP$. $\square$
Beweis B: Sei $L\in P$. D.g.
$$\begin{aligned} L\in P \Rightarrow& \exists \textrm{ DTM } M,\text{die $L$ in polynomieller Laufzeit entscheidet.}\\ \Rightarrow &\exists \textrm{ DTM } M,\text{die stets hält und ganau die Eingabe $w\in L$}\\ &\text{in Laufzeit polynomiell in $|w|$ akzeptiert.}\\ \Rightarrow& \exists \textrm{ DTM } V,\text{die stets hält und ganau die Eingabe} (w,c)\\ &\text{mit $w\in L, c=\epsilon$ in Laufzeit polynomiell in $|w|$ akzeptiert.}\\ &\text{Dabei ignoriert $V$ die Eingabe $c$ und verwendet $M$ auf $w$.}\\ \Rightarrow& L\in NP.\square \end{aligned}$$Offenes Problem
P versus NP
Gilt $P = NP$ oder $P\subset NP$?