0 Daumen
46 Aufrufe

Beweisen Sie [A] aus der Vorlesung (Charakterisierung von NP).
Hinweis: Betrachten Sie die Arbeitsweise von indeterminierten Turingmaschinen.

[A]:

Eine Sprache \( L \) befindet sich in der Klasse NP, wenn und nur wenn eine zugehörige Sprache \( L^{\prime} \) in der Klasse P existiert und ein \( k \geq 0 \) vorliegt, sodass für jedes \( w \) aus dem Alphabet \( \Sigma \) folgendes zutrifft:
Ein Wort \( w \) ist Teil von \( L \) genau dann, wenn ein \( c \) existiert, sodass das Paar \( \langle w, c\rangle \) zu \( L^{\prime} \) gehört und die Bedingung \( |c|<|w|^{k} \) erfüllt ist.
Hierbei wird \( c \) als Zeuge (oder Zertifikat) für das Vorhandensein von \( w \) in \( L \) bezeichnet. Eine Deterministische Turing-Maschine (DTM), die \( L^{\prime} \) akzeptiert, wird als Verifizierer für \( L \) bezeichnet.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community