Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » PSPACE-vollständigkeit » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Der letzte Beitrag
joho 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 [latex]PSPACE-schwer[/latex] 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