anthropic/claude-opus-4.1

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Sei L∈NPL \in \mathsf{NP} mit Verifizierer VV und Zertifikatslänge polynomial beschränkt durch p(n)p(n) für Eingaben der Länge nn.

Wir zeigen L∗∈NPL^* \in \mathsf{NP} durch Angabe eines Verifizierers:

Zertifikat für w∈L∗w \in L^*:
- Eine Zerlegung w=w1w2…wkw = w_1 w_2 \ldots w_k mit wi∈Lw_i \in L für alle ii
- Für jedes wiw_i ein Zertifikat cic_i mit ∣ci∣≤p(∣wi∣)|c_i| \leq p(|w_i|), das bezeugt, dass wi∈Lw_i \in L

Verifizierer für L∗L^*:
Bei Eingabe ww und Zertifikat (w1,…,wk,c1,…,ck)(w_1, \ldots, w_k, c_1, \ldots, c_k):
1. Prüfe ob w=w1w2…wkw = w_1 w_2 \ldots w_k
2. Für jedes i∈{1,…,k}i \in \{1, \ldots, k\}: Prüfe ob V(wi,ci)=1V(w_i, c_i) = 1
3. Akzeptiere genau dann, wenn alle Prüfungen erfolgreich sind

Polynomialität:
- Es gilt k≤∣w∣k \leq |w| und ∣wi∣≤∣w∣|w_i| \leq |w| für alle ii
- Die Gesamtlänge des Zertifikats ist O(∣w∣⋅p(∣w∣))O(|w| \cdot p(|w|)), also polynomial in ∣w∣|w|
- Die Laufzeit ist polynomial, da wir höchstens ∣w∣|w| mal den Verifizierer VV aufrufen

Daher gilt L∗∈NPL^* \in \mathsf{NP}.

anthropic/claude-sonnet-4

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (0.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☐f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0 
wrong answer for choice (1)

Subproblem d (0.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☐A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B 
wrong answer for choice (0)

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Since L∈NPL \in \NP, there exists a polynomial-time verifier VV and polynomial pp such that x∈L  ⟺  ∃yx \in L \iff \exists y with ∣y∣≤p(∣x∣)|y| \leq p(|x|) such that V(x,y)=1V(x,y) = 1.

I construct an NP verifier for L∗L^*:

Input: (w,cert)(w, cert) where cert=(pos,y1,…,yk)cert = (pos, y_1, \ldots, y_k)
- pospos encodes split positions in ww  
- yiy_i are certificates for pieces wiw_i

Algorithm:
1. Split ww into w1,…,wkw_1, \ldots, w_k using pospos
2. For each ii, verify V(wi,yi)=1V(w_i, y_i) = 1
3. Accept iff all verifications succeed

Certificate length: ∣cert∣≤∣w∣+∑i=1kp(∣wi∣)|cert| \leq |w| + \sum_{i=1}^k p(|w_i|)

Since ∑i=1k∣wi∣=∣w∣\sum_{i=1}^k |w_i| = |w| and p(n)=ndp(n) = n^d, by convexity the sum ∑i=1k∣wi∣d\sum_{i=1}^k |w_i|^d is maximized when one piece has length ∣w∣|w| and others are empty (or length 1 in our context). Thus ∑i=1kp(∣wi∣)≤∣w∣d\sum_{i=1}^k p(|w_i|) \leq |w|^d.

Therefore ∣cert∣≤∣w∣+∣w∣d|cert| \leq |w| + |w|^d, which is polynomial in ∣w∣|w|.

Hence L∗∈NPL^* \in \NP.

deepseek/deepseek-chat-v3.1

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Beweis: Da L in NP ist, gibt es einen polynomialzeit Verifizierer V für L. Das heißt, für jedes Wort x existiert ein Zertifikat c, so dass V(x, c) in polynomialzeit akzeptiert genau dann wenn x ∈ L.

Um L* zu verifizieren, konstruieren wir einen Verifizierer V* wie folgt: Für ein Eingabewort w erraten wir nicht-deterministisch eine Partition von w in Teilwörter w1, w2, ..., wk (mit k ≥ 0) und für jedes wi ein Zertifikat ci. Dann überprüfen wir, dass die Konkatenation der wi gleich w ist, und dass für jedes i, V(wi, ci) akzeptiert. Da die Anzahl der Teilwörter k ≤ |w| ist und jede Verifikation V(wi, ci) in Zeit polynomial in |wi| ≤ |w| läuft, ist die Gesamtzeit von V* polynomial in |w|. Somit ist L* in NP.

deepseek/deepseek-r1-0528

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (0.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☒{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\} 
wrong answer for choice (1)

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Beweis: Da L∈NP L \in \text{NP} , existiert ein polynomieller Verifizierer V V  für L L  mit einer Laufzeitbeschränkung durch ein Polynom p p . Wir konstruieren einen nichtdeterministischen polynomiellen Verifizierer V′ V'  für L∗ L^*  wie folgt:  

Bei Eingabe w w  (mit ∣w∣=n |w| = n ) und Zertifikat c c :  
1. Wenn w=ε w = \varepsilon , akzeptiere (denn ε∈L∗ \varepsilon \in L^*  per Definition).  
2. Rate nichtdeterministisch eine Zerlegung von w w  in k≥1 k \geq 1  Teilwörter w1,w2,…,wk w_1, w_2, \dots, w_k  mit w=w1w2⋯wk w = w_1 w_2 \cdots w_k . Dies entspricht dem Raten von k−1 k-1  Trennstellen 0=i0<i1<i2<⋯<ik=n 0 = i_0 < i_1 < i_2 < \dots < i_k = n , wobei wj=w[ij−1+1 bis ij] w_j = w[i_{j-1}+1 \, \text{bis} \, i_j]  für j=1,…,k j = 1, \dots, k .  
3. Rate für jedes Teilwort wj w_j  ein Zertifikat cj c_j  der Länge höchstens p(∣wj∣) p(|w_j|) . Das Gesamtzertifikat c c  besteht aus der Beschreibung der Trennstellen und den cj c_j .  
4. Verifiziere für jedes j j , dass V(wj,cj) V(w_j, c_j)  akzeptiert (d.h., wj∈L w_j \in L ).  
5. Akzeptiere nur, wenn alle V(wj,cj) V(w_j, c_j)  akzeptieren; andernfalls verwerfe.  

Korrektheit und Laufzeit:  
- Die Anzahl der Trennstellen k−1 k-1  ist durch n n  beschränkt, daher hat ihre Beschreibung Länge O(nlog⁡n) O(n \log n) .  
- Die Zertifikate cj c_j  haben jeweils Länge ≤p(∣wj∣)≤p(n) \leq p(|w_j|) \leq p(n) , und ihre Gesamtlänge ist höchstens k⋅p(n)≤n⋅p(n) k \cdot p(n) \leq n \cdot p(n) , also polynomiell in n n .  
- Die Verifikation mit V V  für jedes wj w_j  dauert Zeit ≤p(∣wj∣)≤p(n) \leq p(|w_j|) \leq p(n) . Die Summe dieser Zeiten ist ≤k⋅p(n)≤n⋅p(n) \leq k \cdot p(n) \leq n \cdot p(n) , ebenfalls polynomiell.  
Daher akzeptiert V′ V'  ein Wort w w  genau dann, wenn w∈L∗ w \in L^* , und läuft in nichtdeterministischer Polynomzeit. Somit ist L∗∈NP L^* \in \text{NP} .

google/gemini-2.5-pro

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Sei $L \in \NP$. Dann existiert eine deterministische, polynomiell zeitbeschränkte Turingmaschine $V_L$ (der Verifizierer) und ein Polynom $p$, so dass für jedes Wort $w \in \Sigma^*$ gilt:
$w \in L \iff \exists c \in \Sigma^* \text{ mit } |c| \le p(|w|)$, so dass $V_L(w, c)$ akzeptiert.
Die Laufzeit von $V_L(w, c)$ ist durch ein Polynom $q(|w|)$ in $|w|$ beschränkt.

Wir zeigen, dass auch $L^* \in \NP$ ist, indem wir einen polynomiellen Verifizierer $V_{L^*}$ für $L^*$ konstruieren.

**Zertifikat für $w \in L^*$:**
Ein Wort $w \in\Sigma^*$ ist in $L^*$, wenn es als Konkatenation $w = w_1w_2\dots w_k$ geschrieben werden kann, wobei jedes $w_i \in L$ ist. Ein Zertifikat $C$ für $w \in L^*$ besteht aus:
1. Einer Beschreibung der Partition von $w$ in $w_1, \dots, w_k$. Dies kann durch die Angabe der $k-1$ Trennstellen als eine Folge von Indizes erfolgen.
2. Einer Konkatenation der Zertifikate $c_1, \dots, c_k$, wobei $c_i$ ein Zertifikat dafür ist, dass $w_i \in L$.
Formal kann das Zertifikat als $C = \langle \text{Indizes} \rangle \# \langle c_1 \rangle \# \dots \# \langle c_k \rangle$ kodiert werden, wobei $\#$ ein Trennzeichen ist.

**Verifizierer $V_{L^*}(w, C)$:**
1. Wenn $w = \epsilon$, akzeptiere (da $\epsilon$ per Definition in $L^*$ ist).
2. Parse das Zertifikat $C$, um die durch die Indizes definierte Partition $w=w_1 w_2 \dots w_k$ und die einzelnen Zertifikate $c_1, \dots, c_k$ zu extrahieren. Wenn $C$ kein gültiges Format hat, verwerfe.
3. Für jedes $i$ von $1$ bis $k$:
   - Rufe den Verifizierer $V_L$ mit der Eingabe $(w_i, c_i)$ auf.
   - Wenn $V_L(w_i, c_i)$ verwirft, so verwerfe auch $V_{L^*}$.
4. Wenn alle Aufrufe von $V_L$ akzeptieren, akzeptiere.

**Korrektheit:**
- *($\Rightarrow$)* Wenn $w \in L^*$, dann existiert (falls $w\neq\epsilon$) eine Zerlegung $w = w_1 \dots w_k$ mit $w_i \in L$. Für jedes dieser $w_i$ existiert ein Zertifikat $c_i$. Das aus den Indizes der Zerlegung und den Zertifikaten $c_i$ kombinierte Zertifikat $C$ wird vom Verifizierer $V_{L^*}$ akzeptiert.
- *($\Leftarrow$)* Wenn $V_{L^*}$ ein Zertifikat $C$ für $w$ akzeptiert, dann impliziert dies die Existenz einer Zerlegung $w=w_1\dots w_k$ und Zertifikate $c_i$, so dass $V_L(w_i, c_i)$ für alle $i$ akzeptiert. Das bedeutet $w_i \in L$ für alle $i$, und somit ist $w \in L^*$.

**Komplexitätsanalyse:**
Sei $n = |w|$. Wir können o.B.d.A. annehmen, dass $\epsilon \notin L$ (andernfalls betrachten wir $L' = L \setminus \{\epsilon\}$; es gilt $(L')^* = L^*$ für $L \neq \{\epsilon\}$ und $L' \in \NP$). Damit gilt für jede Zerlegung $w=w_1\dots w_k$ in nicht-leere Worte, dass die Anzahl der Teile $k \le n$ ist.

- **Länge des Zertifikats:**
  - Die $k-1$ Indizes benötigen $O(k \log n) = O(n \log n)$ Speicherplatz.
  - Die Länge der Zertifikate $c_i$ ist $|c_i| \le p(|w_i|)$. Die Gesamtlänge ist $\sum_{i=1}^k |c_i| \le \sum_{i=1}^k p(|w_i|)$. Da $p$ ein Polynom ist und $\sum_{i=1}^k |w_i| = n$, ist auch die Summe $\sum_{i=1}^k p(|w_i|)$ polynomiell in $n$. Zum Beispiel ist für $p(x)=a x^d$ die Summe $\sum a|w_i|^d \le a(\sum |w_i|)^d = an^d$.
  - Die Gesamtlänge des Zertifikats für $V_{L^*}$ ist somit polynomiell in $n$.

- **Laufzeit des Verifizierers:**
  - Das Parsen des Zertifikats ist polynomiell in dessen Länge, also auch in $n$.
  - Die Hauptarbeit sind die $k$ Aufrufe von $V_L$. Die Laufzeit von $V_L(w_i, c_i)$ ist durch $q(|w_i|)$ beschränkt.
  - Die Gesamtlaufzeit der Verifikationsschleife ist $\sum_{i=1}^k q(|w_i|)$. Analog zur Länge des Zertifikats ist diese Summe polynomiell in $n = \sum |w_i|$.
  - Die Gesamtlaufzeit von $V_{L^*}$ ist somit polynomiell in $n$.

Da ein polynomieller Verifizierer für $L^*$ existiert, gilt $L^* \in \NP$.

openai/gpt-5

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Sei L ∈ NP mit Verifizierer V, der auf Eingabe w eine Zeugenkette z mit |z| ≤ q(|w|) (q polynomial) in Zeit p(|w|) (p polynomial) prüft.

Wir konstruieren einen NP-Verifizierer V* für L*. Für eine Eingabe x ∈ Σ* (|x| = n) erwartet V* als Zeugnis:
- eine Zerlegung von x in k Faktoren x = x₁ … x_k mit k ≤ n (für x = ε ist k = 0 erlaubt) und alle x_i ≠ ε,
- zu jedem Faktor x_i ein Zeugnis z_i für V mit |z_i| ≤ q(|x_i|).

V* prüft:
1) die Korrektheit der Zerlegung (in O(n)),
2) für i = 1,…,k: V(x_i, z_i) akzeptiert.

Akzeptiere genau dann, wenn alle Prüfungen akzeptieren.

Korrektheit: x ∈ L* gdw. es eine Zerlegung in Faktoren aus L gibt; genau diese liefert obiges Zeugnis.

Laufzeit: Die Gesamtlaufzeit ist O(n) + ∑_{i=1}^k p(|x_i|). Für ein Polynom p(t) = ∑_{j=0}^d a_j t^j mit a_j ≥ 0 gilt
∑_{i=1}^k |x_i|^j ≤ (∑_{i=1}^k |x_i|)^j = n^j
und k ≤ n, also
∑_{i=1}^k p(|x_i|) ≤ ∑_{j=1}^d a_j n^j + a_0 k ≤ p(n) + a_0 n = poly(n).
Die Zeugnislänge ist |(Zerlegung)| + ∑ |z_i| ≤ O(n) + ∑ q(|x_i|) ≤ poly(n).
Also verifiziert V* in polynomieller Zeit mit polynomiell langem Zeugnis.

Damit ist L* ∈ NP.

openai/gpt-oss-120b

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (0.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☐f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0 
wrong answer for choice (1)

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (0.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☒{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\} 
wrong answer for choice (1)

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Beweis, dass L∗∈NPL^* \in \NP für jedes L∈NPL\in\NP

Sei VV ein polynomieller Verifizierer für LL.  
Für ein Wort w∈Σ∗w\in\Sigma^* der Länge nn konstruieren wir einen Verifizierer V∗V^{*} für L∗L^{*} wie folgt.

Zertifikat.  
Das Zertifikat besteht aus  

1. einer Folge von Trennpositionen 0=i0<i1<i2<⋯<ik=n0 = i_0 < i_1 < i_2 < \dots < i_k = n (wobei k≤nk\le n), die die Zerlegung   
   w=w1w2…wk,\qquwj=w[ij−1+1 .. ij]w = w_1 w_2 \dots w_k,\qqu w_j = w[i_{j-1}+1\ ..\ i_j]  
   definiert, und  

2. für jedes Teilwort wjw_j ein Zertifikat cjc_j für VV, das beweist, dass wj∈Lw_j\in LDa k≤nk\le n und jedes cjc_j nur polynomielle Länge in ∣wj∣|w_j| (also ≤n\le n) besitzt, hat das gesamte Zertifikat Gesamtlänge  
O(n)⏟Trennpositionen+k⋅poly⁡(n)⏟∑∣cj∣  =  O ⁣(n⋅poly⁡(n))=poly⁡(n).
\underbrace{O(n)}_{\text{Trennpositionen}} + \underbrace{k\cdot \operatorname{poly}(n)}_{\sum |c_j|} \;=\; O\!\bigl(n\cdot\operatorname{poly}(n)\bigr)=\operatorname{poly}(n).


Verifikation.  
Der Verifizierer V∗V^{*} prüft in polynomialer Zeit:

1. dass die angegebenen Trennpositionen tatsächlich eine Zerlegung von ww ergeben,
2. für jedes j=1,…,kj=1,\dots,k, dass VV das Teilwort wjw_j zusammen mit dem zugehörigen Zertifikat cjc_j akzeptiert.

Jede einzelne Ausführung von VV benötigt Zeit poly⁡(∣wj∣)≤poly⁡(n)\operatorname{poly}(|w_j|)\le\operatorname{poly}(n), also insgesamt  
k⋅poly⁡(n)≤n⋅poly⁡(n)=poly⁡(n)
k\cdot\operatorname{poly}(n) \le n\cdot\operatorname{poly}(n)=\operatorname{poly}(n)

Zeit.

Damit existiert ein polynomieller Verifizierer für L∗L^{*}, also liegt L∗L^{*} in NP\NP.

L∈NP  Longrightarrow  L∗∈NP
\boxed{L\in\NP \;\Longrightarrow\; L^{*}\in\NP}


Damit ist die Aussage „L∗∈NPL^{*}\in\NP“ richtig.

qwen/qwen3-235b-a22b

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Beweis: Sei L∈NP L \in \NP  mit einem Zertifikatsverifizierer VL(x,c) V_L(x, c) , der in Polynomzeit prüft, ob x∈L x \in L  mit Zertifikat c c . Für L∗ L^*  definiere den Verifizierer V∗ V^* : \\
1. Zertifikat enthält eine Aufteilung w=w1w2⋯wk w = w_1w_2\cdots w_k  und Zertifikate c1,…,ck c_1, \dots, c_k  für wi∈L w_i \in L . \\
2. Prüfe in Polynomzeit, dass alle wi∈L w_i \in L  gelten (mit VL(wi,ci) V_L(w_i, c_i) ). \\
Da k≤∣w∣ k \leq |w|  und jedes ci c_i  polynomiell in ∣wi∣ |w_i|  ist, ist das Gesamtzertifikat polynomiell lang, und die Prüfung ist in Polynomzeit durchführbar. Also gilt L∗∈NP L^* \in \NP .

qwen/qwen3-235b-a22b-thinking-2507

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Ja. Sei L∈NPL \in \NP mit einem polynomiellen Verifizierer VLV_L. Für w∈Σ∗w \in \Sigma^* ist w∈L∗w \in L^* genau dann, wenn es eine Zerlegung w=x1x2⋯xkw = x_1x_2\cdots x_k mit k≥0k \geq 0 und xi∈Lx_i \in L gibt. Das Zertifikat für ww besteht aus den Teilungsstellen 0=i0<i1<⋯<ik=∣w∣0 = i_0 < i_1 < \cdots < i_k = |w| sowie Zertifikaten c1,…,ckc_1, \dots, c_k für xj=w[ij−1..ij]∈Lx_j = w[i_{j-1}..i_j] \in L. Der Verifizierer für L∗L^* überprüft:
1. Die Gültigkeit der Teilungsstellen (d. h. i0=0i_0=0, ik=∣w∣i_k=|w|, ij>ij−1i_j > i_{j-1}).
2. Für jedes jj, dass VL(xj,cj)V_L(x_j, c_j) akzeptiert.

Da k≤∣w∣k \leq |w| und jedes cjc_j polynomiell in ∣xj∣|x_j| ist, ist die Zertifikatlänge polynomiell in ∣w∣|w|. Jeder Verifikationsschritt läuft in polynomieller Zeit, also ist der Gesamtverifizierer polynomiell zeitbeschränkt. Somit gilt L∗∈NPL^* \in \NP.

x-ai/grok-4

Exercise 6: Quiz: Berechenbarkeit und Komplexität

Teilaufgaben (a-e): Für diese Fragen ist eine Begründung nicht gefordert. Sie erhalten die Punkte auf eine Teilaufgabe genau dann, wenn Sie alle Antwortmöglichkeiten korrekt angekreuzt haben.
Es ist immer mindestens eine Antwortmöglichkeit richtig.
In dieser Aufgabe verwenden wir durchgehend das Alphabet Σ:={0,1}\Sigma := \{0, 1\}.

Subproblem a (2.0/2.0P) 

Sei LL eine kontextfreie Sprache. Welche Aussagen sind wahr?
☒LL ist entscheidbar☒L‾\overline{L} ist entscheidbar☒LL ist semi-entscheidbar

Subproblem b (2.0/2.0P) 

Seien L1,L2⊆Σ∗L_1,L_2\subseteq\Sigma^* entscheidbare Sprachen. Welche der folgenden Sprachen sind entscheidbar?
☒L1∩L2L_1\cap L_2☒L1∖L2L_1\setminus L_2☒L1L2L_1L_2

Subproblem c (2.0/2.0P) 

Sei L⊆{0}∗L\subseteq\{0\}^* unentscheidbar. Welche der folgenden Funktionen f:N→Nf:\N\rightarrow\N sind berechenbar?
☐f(n):=∣L∩Σn∣f(n):=|L\cap \Sigma^n|☒f(n):=min⁡{k∈N:0k∈L}f(n):=\min\{k\in\N: 0^k\in L\}☐f(n):=1f(n):=1, falls 0n∈L0^n\in L, sonst f(n):=0f(n):=0

Subproblem d (2.0/2.0P) 

Seien A,B⊆Σ∗A,B\subseteq\Sigma^* Sprachen mit A≤pSAT≤pBA\le_p\SAT\le_p B. Welche Aussagen sind wahr?
☒A∈NPA\in\NP☐B∈NPB\in\NP☒BB ist NP-hart☒A≤pBA\le_p B

Subproblem e (2.0/2.0P) 

Sei L⊆Σ∗{#}Σ∗L\subseteq \Sigma^*\{\#\}\Sigma^* eine Sprache, sodass L∈PL\in\P; LL enthält also Wörter der Form u#vu\#v, mit u,v∈Σ∗u,v\in\Sigma^*. Welche der folgenden Sprachen sind in NP\NP?
☒LL☐{u∣∃v∈Σ∗:u#v∈L}\{u\mid\exists v\in\Sigma^*:u\#v\in L\}☒{u∣∃v∈Σ∗:u#v∈L∧∣u∣=∣v∣}\{u\mid\exists v\in\Sigma^*:u\#v\in L\wedge |u|=|v|\}

Subproblem f (4.0/4.0P) 

Sei L∈NPL\in\NP. Zeigen oder widerlegen Sie: L∗∈NPL^*\in\NP.
☒Ja, Beweis:☐Nein, Gegenbeispiel: 
Sei L∈NPL\in\NP. Dann existiert ein polynomiell zeitbeschränkter deterministischer Verifizierer VV und ein Polynom qq, sodass für jedes x∈Σ∗x\in\Sigma^* gilt: x∈Lx\in L gdw. es ein Zertifikat cc mit ∣c∣≤q(∣x∣)|c|\le q(|x|) gibt, für das V(x,c)V(x,c) akzeptiert.

Für L∗L^* konstruieren wir einen Verifizierer V∗V^* wie folgt. Sei w∈Σ∗w\in\Sigma^* mit ∣w∣=n|w|=n. Ein Zertifikat für ww codiert: eine Zahl kk (0≤k≤n0\le k\le n), Endpositionen 0=p0<p1<⋯<pk=n0=p_0 < p_1 <\dots< p_k = n (jede pip_i in Binärdarstellung mit O(log⁡n)O(\log n) Bits) und Zertifikate c1,…,ckc_1,\dots,c_k mit ∣ci∣=q(pi−pi−1)|c_i|=q(p_i - p_{i-1}) (ggf. gepaddet).

Die Gesamtlänge des Zertifikats ist O(klog⁡n)+∑q(∣wi∣)≤O(nlog⁡n)+nrO(k\log n) + \sum q(|w_i|)\le O(n\log n) + n^r für geeignetes rr (da qq polynomiell und ∑∣wi∣r≤nr\sum |w_i|^r \le n^r), also polynomiell in nn.

V∗V^* dekodiert das Zertifikat (in polynomieller Zeit), extrahiert die wi=w[pi−1+1..pi]w_i = w[p_{i-1}+1..p_i], überprüft für jedes ii mit V(wi,ci)V(w_i, c_i), ob es akzeptiert, und akzeptiert iff alle tun und die Positionen gültig sind. Für n=0n=0 akzeptiert V∗V^* direkt (leeres Wort ∈L∗\in L^*).

Die Laufzeit ist polynomiell, da Dekodierung und Kopieren/Verifizieren der k≤nk\le n Teile jeweils polynomiell Zeit benötigt, insgesamt O(poly(n))O(\mathrm{poly}(n)).

Somit ist L∗∈NPL^*\in\NP.