PSPACE-vollständigkeit

21.01.2017, 22:30	Auf diesen Beitrag antworten »
joho	PSPACE-vollständigkeit Hallo allerseits , ich hänge bei dem Beweis der PSPACE-vollständigkeit der Sprache: $[latex]L = \{\langle c(M), w, 1^n \rangle :[/latex]$ Turingmaschine , die das Wort akzeptiert und dabei höchstens Bandzellen besucht $[latex]\}[/latex]$ 1. Reicht es um zu zeigen, dass $[latex]L \in PSPACE[/latex]$ , wenn eine universelle TM konstruiert wird, welche simuliert, aber nach spätestens Schritten stoppt, falls M nicht vorher terminiert? 2. Für den Beweis, dass auch ist, muss ich auf ein anderes Problem aus reduzieren? und genau bei 2. stehe ich echt auf dem Schlauch. Schon mal vielen Dank im voraus

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »