0 Daumen
67 Aufrufe

(a) Gegeben sei eine injektive Funktion \( f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0} \), die Zahlen der Länge \( k \) auf Zahlen derselben Länge abbildet. Weiterhin gilt \( f \in \mathbf{P} \) und \( f^{-1} \notin \mathbf{P} \). Gilt
\( \left\{\langle x, y\rangle: f^{-1}(x)<y\right\} \in(\mathbf{N P} \cap \text { co-NP }) \backslash \mathbf{P} \text { ? } \)
(b) Angenommen wir haben eine DTM M, die eine Sprache \( L \) wie folgt entscheidet: (1) Wenn \( x \in L \), antwortet \( M \) in polynomieller Zeit mit ja, (2) wenn \( x \notin L \), antwortet \( \mathbf{M} \) in exponentieller Zeit mit nein. Ist \( L \in \mathbf{P} \) ?

von

Wie ist die Länge einer Zahl definiert?

Was ist \(\langle x,y\rangle\)?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community