Wie würde man das darstellen wenn der NEA in deiner Übungsaufgabe am Ende mehrere Endzustände haben soll? Müsste man hier dann nicht den Eingabegraphen erstmal erweitern?
Ich verstehe nicht, worauf Du hinaus möchtest. Warum sollte der NEA mehrere Endzustände haben sollen? Beim Erreichbarkeitsproblem gibt es nur einen Zielknoten t, daher eignet sich ein NEA mit einem einzigen Endzustand hier am besten.
@@NLogSpace Naja ich meine wenn L2 jetzt ein NEA mit mehreren Endzuständen wäre und L1 ein Graph mit s und t, und man reduziert von L1 auf L2 wie ließe sich dass dann durch Reduktion darstellen?
@@Themogawave Die Eingabe für unsere Reduktion ist nur der Graph mit s und t, also nur eine Eingabe für das Problem L1. In der Reduktion konstruieren wir dann die Eingabe für L2, in diesem Fall einen NEA. Der NEA ist also nicht gegeben, wir können uns selbst aussuchen, wie er aussehen soll.
Ein Verifizierer ist eine DTM, die zwei Eingaben bekommt: Zusätzlich zum nornalen Eingabewort w erhält er auch noch ein "Zertifikat" z. Der Verifizierer muss die Eingabe bestehend aus w und z genau dann akzeptieren, wenn w in der Sprache liegt und z ein Beweis dafür ist. Bei 3COL könnte das Zertifikat z.B. die Färbung der Knoten angeben, bei SAT eine erfüllende Belegung der Formel. Wenn es einen solchen Verifizierer gibt, der in Polyzeit läuft, dann ist die Sprache in NP. Diese Definition von NP mittels Zertifikaten haben ich auch in einem eigenen Video thematisiert
Danke für die Erklärung! Ich muss sagen dass mich diese Notation A =_p B heißen, weil A ein polynomiell "größeres" Problem ist als B, oder? Und die "Reduktion" endet damit dass A auf ein "kleineres" Problem B abgebildet wird.
@@NLogSpace hahaha, bin gerade nochmal zurückgekehrt, um zu sagen "Warte, jetzt bin ich total verwirrt" und dann gabs schon die Antwort! Das mit der oberen Schranke hat mir ein Licht aufgehen lassen. danke danke danke!
Zu der letzten Aufgabe die du gestellt hast. Wenn wir eine feste reguläre Sprache L2 hätten, die beschreibt wann ein wort w zur Sprache gehört, könnten wir die Abbildung vom Graphen auf den Automaten nicht mehr machen.Die übergänge des Automaten müssten doch dann genau die Symbole enthalten die bestimmen ob w ∈ L2, also man könnte nicht irgendwelche Symbole wählen oder?
Wenn ich jedes Problem in P in auf jedes andere in Polytime reduzieren kann, ist dann überhaupt die Reduktionsrichtung relevant um zu zeigen, dass ein Problem in P ist?
@@NLogSpace Ja, so ist auch intuitiv Thanks again. Ich denke, ich hätte es verstanden und dann wehrt sich mein Hirn doch wieder dagegen. :/ ^^ Aber wenn zwei Probleme in der gleichen Komplexitätsklasse lägen, dann könnte man sie mit entsprechenden Aufwand (vielleicht ist in höheren Komplexitätsklassen ja auch ein höherer Reduktionsaufwand legitim) jeweils aufeinander reduzieren, oder?
@@josh19889 Das kommt dann wie Du schon sagst auf die Art der Reduktion an. Es ist z.B. nicht der Fall, dass man je zwei Probleme aus ExpTime mit einer Polyzeitreduktion aufeinander reduzieren kann, denn Komplexitätsklassen sind "nach unten abgeschlossen", d.h. ExpTime enthält auch Probleme, die man mit viel weniger Zeit lösen kann. Also wenn A ein sehr schwieriges Problem aus ExpTime ist und B ein Problem in P ist, was ja auch innerhalb von ExpTime liegt, dann ist es womöglich nicht der Fall, dass man A auf B reduzieren kann. Aber wenn man "ExpTime-Reduktionen" erlaubt, dann wäre es wieder der Fall, dass man jedes Problem aus ExpTime auf jedes anderen Problem in ExpTime reduzieren kann.
@@NLogSpace Ahh ok, danke. Das hilft mir weiter und das Video zur NP-Vollständigkeit ist auch essentiell^^ Da wird es glatt mal Zeit für eine PayPal-Spende bei all dem Herzblut, das du reinsteckst um das Thema für notorische Langsamdenker wie mir begreifbar zu machen :D
![Aufgaben zu Entscheidbarkeit und Satz von Rice [Klausuraufgaben Berechenbarkeit #03]](http://i.ytimg.com/vi/jpbGGNbpYzM/mqdefault.jpg)
Gut gemacht! Bitte mehr
Exzellent. Danke!
Wie würde man das darstellen wenn der NEA in deiner Übungsaufgabe am Ende mehrere Endzustände haben soll? Müsste man hier dann nicht den Eingabegraphen erstmal erweitern?
Ich verstehe nicht, worauf Du hinaus möchtest. Warum sollte der NEA mehrere Endzustände haben sollen? Beim Erreichbarkeitsproblem gibt es nur einen Zielknoten t, daher eignet sich ein NEA mit einem einzigen Endzustand hier am besten.
@@NLogSpace Naja ich meine wenn L2 jetzt ein NEA mit mehreren Endzuständen wäre und L1 ein Graph mit s und t, und man reduziert von L1 auf L2 wie ließe sich dass dann durch Reduktion darstellen?
@@Themogawave Die Eingabe für unsere Reduktion ist nur der Graph mit s und t, also nur eine Eingabe für das Problem L1. In der Reduktion konstruieren wir dann die Eingabe für L2, in diesem Fall einen NEA. Der NEA ist also nicht gegeben, wir können uns selbst aussuchen, wie er aussehen soll.
Was genau ist ein Verifizierer?
Ist das das wenn bei NP was geraden wird und man überprüfung mus in polinomieller zeit ob das stimmt?
Ein Verifizierer ist eine DTM, die zwei Eingaben bekommt: Zusätzlich zum nornalen Eingabewort w erhält er auch noch ein "Zertifikat" z. Der Verifizierer muss die Eingabe bestehend aus w und z genau dann akzeptieren, wenn w in der Sprache liegt und z ein Beweis dafür ist. Bei 3COL könnte das Zertifikat z.B. die Färbung der Knoten angeben, bei SAT eine erfüllende Belegung der Formel.
Wenn es einen solchen Verifizierer gibt, der in Polyzeit läuft, dann ist die Sprache in NP. Diese Definition von NP mittels Zertifikaten haben ich auch in einem eigenen Video thematisiert
@@NLogSpace Ok verstehe ich schon, vielen dank
Danke für die Erklärung!
Ich muss sagen dass mich diese Notation A =_p B heißen, weil A ein polynomiell "größeres" Problem ist als B, oder?
Und die "Reduktion" endet damit dass A auf ein "kleineres" Problem B abgebildet wird.
Ja das ist erstmal ein bisschen verwirrend. Aber letztendlich gibt die Reduktion A
@@NLogSpace hahaha, bin gerade nochmal zurückgekehrt, um zu sagen "Warte, jetzt bin ich total verwirrt" und dann gabs schon die Antwort! Das mit der oberen Schranke hat mir ein Licht aufgehen lassen. danke danke danke!
In welchem Semester bist du aktuell?
Oder bist du schon fertig?
Er ist seit ein paar Jahren Doktorand
@@DoktoreBlah quelel?
Zu der letzten Aufgabe die du gestellt hast. Wenn wir eine feste reguläre Sprache L2 hätten, die beschreibt wann ein wort w zur Sprache gehört, könnten wir die Abbildung vom Graphen auf den Automaten nicht mehr machen.Die übergänge des Automaten müssten doch dann genau die Symbole enthalten die bestimmen ob w ∈ L2, also man könnte nicht irgendwelche Symbole wählen oder?
Auf welches Problem möchtest Du denn genau reduzieren? Nicht mehr auf das Leerheitsproblem von NEAs?
Wenn ich jedes Problem in P in auf jedes andere in Polytime reduzieren kann, ist dann überhaupt die Reduktionsrichtung relevant um zu zeigen, dass ein Problem in P ist?
Ja, die Reduktionsrichtung ist relevant. Wenn man A
@@NLogSpace Ja, so ist auch intuitiv Thanks again. Ich denke, ich hätte es verstanden und dann wehrt sich mein Hirn doch wieder dagegen. :/ ^^
Aber wenn zwei Probleme in der gleichen Komplexitätsklasse lägen, dann könnte man sie mit entsprechenden Aufwand (vielleicht ist in höheren Komplexitätsklassen ja auch ein höherer Reduktionsaufwand legitim) jeweils aufeinander reduzieren, oder?
@@josh19889 Das kommt dann wie Du schon sagst auf die Art der Reduktion an. Es ist z.B. nicht der Fall, dass man je zwei Probleme aus ExpTime mit einer Polyzeitreduktion aufeinander reduzieren kann, denn Komplexitätsklassen sind "nach unten abgeschlossen", d.h. ExpTime enthält auch Probleme, die man mit viel weniger Zeit lösen kann. Also wenn A ein sehr schwieriges Problem aus ExpTime ist und B ein Problem in P ist, was ja auch innerhalb von ExpTime liegt, dann ist es womöglich nicht der Fall, dass man A auf B reduzieren kann. Aber wenn man "ExpTime-Reduktionen" erlaubt, dann wäre es wieder der Fall, dass man jedes Problem aus ExpTime auf jedes anderen Problem in ExpTime reduzieren kann.
@@NLogSpace Ahh ok, danke. Das hilft mir weiter und das Video zur NP-Vollständigkeit ist auch essentiell^^
Da wird es glatt mal Zeit für eine PayPal-Spende bei all dem Herzblut, das du reinsteckst um das Thema für notorische Langsamdenker wie mir begreifbar zu machen :D