Not logged in. · Lost password · Register

Page:  previous  1  2  3  4 
MarryLookAhead
Member since Mar 2015
12 posts
In reply to post ID 150086
Das ist tatsächlich egal, wegen Savitch's theorem. Kurz gesagt kann eine nicht deterministische Turingmaschine etwas mit polynomiellen Platz entscheiden genau dann wenn es eine deterministische Turingmaschine mit polynomiellen Platz entscheiden kann.
Jo, klar, steht ja darunter aber PSPACE ist halt an sich falsch definiert :P Es besteht ja die Moeglichkeit, dass eine Klausurfrage zu der Definition kommt.
Vvalter
Member since Dec 2012
119 posts
Quote by MarryLookAhead:
Jo, klar, steht ja darunter aber PSPACE ist halt an sich falsch definiert :P Es besteht ja die Moeglichkeit, dass eine Klausurfrage zu der Definition kommt.

Ist ja dann nicht wirklich eine falsche Definition. Es ist nur eine andere Definition, welche aber äquivalent zu der "offiziellen" ist und damit genauso richtig. Das sollte in der Klausur auch keine Probleme machen.

Schöner wäre es aber wahrscheinlich schon wenn es mit einer normalen Turingmaschine definiert wird.
MarryLookAhead
Member since Mar 2015
12 posts
Quote by Vvalter:
Ist ja dann nicht wirklich eine falsche Definition. Es ist nur eine andere Definition, welche aber äquivalent zu der "offiziellen" ist und damit genauso richtig. Das sollte in der Klausur auch keine Probleme machen.

Schöner wäre es aber wahrscheinlich schon wenn es mit einer normalen Turingmaschine definiert wird.
Es waere schoener, weil eben erst im Absatz danach das mit der Simulation erwaehnt wird. Davor ist es ja nicht klar, dass die Problemklassen gleich sind.
Matombo
Member since Aug 2014
30 posts
nur ne kleinigkeit: in übungsblatt 7 aufgabe 2 fehlt ne klammer bei einer der formeln
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  previous  1  2  3  4 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen