Hier hab ich ein Paar Fragen zu F3:
-Sind alle Probleme in NP entscheidbar? Warum?
-Was ist die Komplexität einer DTM, einer NTM?
-Wie kann man zeigen, das L1 echt kleiner ist als L0?
Sind alle Probleme in NP entscheidbar? Warum?
Ein Problem ist in NP, wenn es eine NTM gibt, die es in polynomialer Zeit
löst. D.h. es gibt ein Polynom P derart, dass, wenn die Eingabe die Länge n hat, die Turing-Maschine nach P(n) Schritten hält. Entweder in einem Endzustand oder eben nicht.
Was ist die Komplexität einer DTM, einer NTM?
Im Skript werden die Klassen NTime, DTime, NSpace, DSpace definiert (sowie darauf aufbauend P, NP, PSpace und NPSpace). Meinst du etwas anderes?
Wie kann man zeigen, das L1 echt kleiner ist als L0?
Skript S. 92. Verstehst du dort einen bestimmten Schritt nicht? Oder möchtest du eine generelle Erklärung der Beweisidee?
Genauere Fragen bitte, sonst muss ich mir ja die Finger wund tippen [img]
http://www.fb18.de/gfx/24.gif[/img]
Cheers,
Frank
Sind alle Probleme in NP entscheidbar? Warum?
Ein Problem ist in NP, wenn es eine NTM gibt, die es in polynomialer Zeit löst. D.h. es gibt ein Polynom P derart, dass, wenn die Eingabe die Länge n hat, die Turing-Maschine nach P(n) Schritten hält. Entweder in einem Endzustand oder eben nicht.
ähm, das beantwort ob alle Probleme in NP entscheidbar sind?
heißt nicht entscheidbar = Problem liegt in P?
und ist das nicht wieder die berühmte Frage zu der die Antwort lautet:
'es ist nicht entschieden ob NP = P'
insofern weiß man nicht ob alle Probleme in NP entscheidbar sind,
einige (die auch in P liegen) sind klar entscheidbar,
bei Rest kann das niemand sagen
Genauere Fragen bitte, sonst muss ich mir ja die Finger wund tippen [img]http://www.fb18.de/gfx/24.gif[/img]
ich hab das Gefühl dass sind mal wieder wahllos aus Prüfungsprotokollen abgetippte Fragen,
zu denen die Antwort (und überhaupt das Verständnis worum es geht) eben fehlt
(nix für ungut @ Anonyme/r User/Userin ;) )
Sind alle Probleme in NP entscheidbar? Warum?
Ein Problem ist in NP, wenn es eine NTM gibt, die es in polynomialer Zeit löst. D.h. es gibt ein Polynom P derart, dass, wenn die Eingabe die Länge n hat, die Turing-Maschine nach P(n) Schritten hält. Entweder in einem Endzustand oder eben nicht.
ähm, das beantwort ob alle Probleme in NP entscheidbar sind?
heißt nicht entscheidbar = Problem liegt in P?
entscheidbar = es gibt eine TM, die das Problem entscheidet. Über eine Zeitbeschränkung sagt der Begriff nichts aus.
Ich haette auch nochmal ne frage. man kann sich ueber die online-anmeldung nicht fuer F3 - Uebungen anmelden. Ab wann und wo kann man das machen???
Als Informatikstudent meldet man sich für F3-Übungen garnicht an - die sind nur für Wiinfs
Ok, ich haette das vielleicht noch etwas ausfuehrlicher Erklaeren sollen [img]
http://www.fb18.de/gfx/25.gif[/img]
Also: Wenn die NTM nach (spaetestens) P(n) Schritten (P ein Polynom, n die Laenge der Angabe) anhaelt (und zwar in jedem ihrer Rechnungszweige - sie hat ja meist Wahlmoeglichkeiten), dann ist das Problem doch entscheidbar, denn wenn sie dabei (in einem ihrer Rechnungszweige) in einen Endzustand geraet, so akzeptiert sie. Tut sie das nicht, so akzeptiert sie folglich nicht, hat aber auch angehalten.
Etwas intuitiver: Nehmen wir mal so ein Problem wie SAT (Bestimmung einer erfuellenden Belegung fuer eine aussagenlogische Formel). Man wuerde wohl kaum davon sprechen, dass man einen loesenden Algorithmus fuer dieses Problem hat, wenn dieser bei einigen Eingaben einfach weiterlaeuft (dann weiss man ja gerade nicht, ob die Formel, die man eingegeben hat ein Modell hat (und dieses nur noch nicht bestimmt ist) oder ob keines exisitert).
Cheers,
Frank
