This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 16th 2007, 5:13pm)
Quoted
Original von Currywurst mit Pommes
In Aufgabe 9 wird gezeigt, dass
A element von TIME(f(n)) <=> (Strich über) A element von TIME(f(n)) ist.
Logisch, denn eine TM kann A in O(f(n)) entscheiden.
D.h. ist ein Wort element von A, so akzeptiert die TM dies in O(f(n)) Zeit.
Ist ein Wort Element von (Strich über) A, also NICHT Element von A, so verwirft die TM dies ebenfalls in O(f(n)).
Ich muss also nur eine TM' entwickeln, die TM simuliert und das Ergebnis "akzeptieren/ablehnen" vertauscht.
Warum aber gilt dies nicht für
A element von NTIME(f(n)) <=> (Strich über) A element von NTIME(f(n)) ?
Mir ist klar, dass es bei nicht-determ. Algorithmen mehrere akzeptierende Zustände, etc. gibt. Aber is das nicht egal ?
Denn auch hier gilt doch: Eine NTM kann A entscheiden in O(f(n))
-> Ist ein Wort element von A, so akzeptiert eine NTM dies in O(f(n))
-> Ist ein Wort element von (Strich über) A, also NICHT in A, so verwirft eine NTM dies in O(f(n)).
Jetzt kann ich doch auch hier wieder einen Schritt anhängen, in dem ich akzeptieren/ablehnen vertausche. Somit bleibt es weiterhin O(f(n)).
Oder liegts an der Mitschrift ?
Danke!
Quoted
Original von Currywurst mit Pommes
Hier nun der offizielle Thread
Gibt's eigentlich Lösungen für Aufgabe 4 und 5 der Übungen ?
Quoted
Original von Currywurst mit Pommes
Ach ja, und zu 6) Besucht eine TM nicht n+1 Bandzellen bei n Rechenschritten ? In der Übungslösung war nur von n die Rede.
Quoted
Original von Arne
Hat das geholfen?
Quoted
Kommt darauf an, wie man Rechenschritt definiert. Aber macht das bei Aufgabe 6 jetzt so viel aus?
This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 18th 2007, 11:14am)
Quoted
Original von Jojo
Es ist folgende Aufg gegeben:
Nehmen Sie an, dass Sie drei Turingmaschinen M1, M2 und M3 vorliegen haben, die jeweils
eine Menge L entscheiden. Bei Eingabelänge n arbeite die Maschine M1 in Zeit O(n_hoch_2), die
Maschine M2 in Zeit O(2_hoch_n) und die Maschine M3 in Zeit O(n + 5).
Sei nun x eine Eingabe der Länge 12. Läßt sich mit den obigen Informationen feststellen,
welcher der drei Algorithmen die Zugehörigkeit von x zur Menge L mit der geringsten Anzahl
an Rechenschritten entscheidet? Falls ja: Welcher dieser Algorithmen ist es? Begründen Sie
Ihre Antworten.
wuerde es reichen wenn man O(n+5) waehlt und sagt da 12+5< als die anderen Alternativen od muss man wieder formal irgendwie bescreiben
This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 18th 2007, 2:18pm)
Quoted
Original von Currywurst mit Pommes
So, nach mehreren Versuchen habe ich verschiedene Algorithmen die zwar lustige Dinge tun, aber kurz vor Schluss merke ich immer, dass er doch nicht ganz das tut was ich will (n*k, oder k*n^n oder so , ...)
Dies wäre wieder ein Fall, wo ich für eine offizielle Lösung dankbar wäre. Hab leider nur welche für a) und b).
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Andersrum ist es vielleicht einfacher: Mache Dir zunächst klar, warum kein NP-vollständiges Problem (also z. B. SAT) auf Sigma^* und \emptyset reduziert werden kann.Quoted
Original von Arne
Tipp: zeig erstmal, dass alle anderen Sprachen (außer Sigma* und Emptyset) NP-hart sind. Dann überleg, warum das auf die beiden nicht zutrifft.
This post has been edited 2 times, last edit by "Jojo" (Sep 21st 2007, 12:30pm)
Source code |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Eine Sprache A ist NP-vollständig wenn 1) A in NP 2) A NP-hart ist, also alle Sprachen aus NP auf A polynonminell reduziert werden können Zu 1) Dies ist als Vorraussetzung durch die Aufgabe gegeben Zu 2) Es ist zu zeigen, dass jede beliebige Sprache X aus NP auf A reduziert werden kann. Dazu muss eine Funktion bzw. ein Algorithmus bekannt sein, der Reduktion in poly. Zeit ermöglicht. Es gilt bei dieser Aufgabe NP = P, also kann X in poly. Zeit entschieden werden. Die Reduktion erfolgt also so: * Entscheide X * Wird X akzeptiert/(abgelehnt), so probiere solange alle Wörter aus dem Alphabet der Sprache von A aus, bis A akzeptiert(/ablehnt). Gib dieses Wort aus. Der Suchvorgang kann in endlicher Zeit geschehen, da die Anzahl der Wörter in A endlich ist. Bei leerer Menge gäbe es kein Wort, das für Akzeptieren ausgegeben werden könnte. Ist A = Sigma*, so wäre kein Wort für Ablehnen zu finden. |