Informatiker Board | Druckvorschau: PSPACE-vollständigkeit

Geschrieben von joho am 21.01.2017 um 22:30:

PSPACE-vollständigkeit

Hallo allerseits Wink

,

ich hänge bei dem Beweis der PSPACE-vollständigkeit der Sprache:

$[latex]L = \{\langle c(M), w, 1^n \rangle :[/latex]$ Turingmaschine [latex]M[/latex]

, die das Wort [latex]w[/latex]

akzeptiert und dabei höchstens [latex]n[/latex]

Bandzellen besucht $[latex]\}[/latex]$

1. Reicht es um zu zeigen, dass $[latex]L \in PSPACE[/latex]$ , wenn eine universelle TM konstruiert wird, welche [latex]M[/latex]

simuliert, aber nach spätestens [latex]n[/latex]

Schritten stoppt, falls M nicht vorher terminiert?

2. Für den Beweis, dass [latex]L[/latex]

auch

ist, muss ich [latex]L[/latex]

auf ein anderes Problem aus [latex]PSPACE[/latex]

reduzieren?

und genau bei 2. stehe ich echt auf dem Schlauch.

Schon mal vielen Dank im voraus smile