Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » PSPACE-vollständigkeit

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

PSPACE-vollständigkeit

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

joho
Grünschnabel

Dabei seit: 21.01.2017
Beiträge: 4

PSPACE-vollständigkeit

Zitatantwort auf diesen Beitrag erstellen

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

21.01.2017 22:30

Nehmen Sie joho in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » PSPACE-vollständigkeit