Die Klausur ist jetzt fast 4 Monate her. Da gab es die Aufgabe, zu zeigen, dass 4 verschiedene Probleme nicht in P liegen, indem man das Zertifikat angibt. Da so gut wie niemand wusste, wie so ein Zertifikat aussehen soll, hat so gut wie jeder 0 Punkte bekommen. Jetzt, dank deiner Videos, fange ich langsam an, es zu verstehen.
Sollte man dort wirklich zeigen, dass gewisse Probleme "nicht in P liegen", indem man Zertifikate angibt? Das ergibt keinen Sinn. Wenn man für ein Problem zeigt, dass es ein polynomielles Zertifikat-System gibt, dann ist das Problem in NP. Aber es ist unbekannt, ob P=NP, also sagendie Zertifikate erstmal nichts darüber aus, ob das Problem in P liegt oder nicht.
@@NLogSpace Ich habe das etwas übermüdet aus dem Kopf geschrieben. Hier ist die richtige Aufgabenstellung: "Zeigen Sie, dass folgende Probleme in NP sind, und geben Sie jeweils das Zertifikatskriterium an. Vergessen Sie nicht, zu beweisen, dass das Zertifikatskriterium in polynomieller Zeit ̈uberprüfbar ist."
Ich bin grad im 2. Semester und das ist und P und NP sind unsere aktuellen Themen, tolles Video :) Kannst du mal eine formale Reduktion auf das Halteproblem zeigen, auf das sich nicht der Satz von Rice anwenden lässt? Konkret hätt ich da jetzt zum Beispiel an den fleißigen Biber gedacht, bei dem die TM gesucht ist, die am meisten Schritte auf dem Arbeitsband macht.
Ich habe auf meinem Kanal schon einige Videos zu Reduktionen vom Halteproblem (nicht *auf* das Halteproblem, sondern *vom* Halteproblem, aber ich denke das meintest Du). Die findest Du in der Playlist über Berechenbarkeit.
Die Klausur ist jetzt fast 4 Monate her. Da gab es die Aufgabe, zu zeigen, dass 4 verschiedene Probleme nicht in P liegen, indem man das Zertifikat angibt. Da so gut wie niemand wusste, wie so ein Zertifikat aussehen soll, hat so gut wie jeder 0 Punkte bekommen.
Jetzt, dank deiner Videos, fange ich langsam an, es zu verstehen.
Sollte man dort wirklich zeigen, dass gewisse Probleme "nicht in P liegen", indem man Zertifikate angibt? Das ergibt keinen Sinn. Wenn man für ein Problem zeigt, dass es ein polynomielles Zertifikat-System gibt, dann ist das Problem in NP. Aber es ist unbekannt, ob P=NP, also sagendie Zertifikate erstmal nichts darüber aus, ob das Problem in P liegt oder nicht.
@@NLogSpace Ich habe das etwas übermüdet aus dem Kopf geschrieben. Hier ist die richtige Aufgabenstellung:
"Zeigen Sie, dass folgende Probleme in NP sind, und geben Sie jeweils das Zertifikatskriterium an. Vergessen Sie nicht, zu beweisen, dass das Zertifikatskriterium in polynomieller Zeit ̈uberprüfbar ist."
@@TheDarkOne629 Ja, so ergibt die Aufgabe Sinn. Zu der Definition von NP mittels Zertifikaten habe ich auch Videos auf meinem Kanal.
Ich bin grad im 2. Semester und das ist und P und NP sind unsere aktuellen Themen, tolles Video :) Kannst du mal eine formale Reduktion auf das Halteproblem zeigen, auf das sich nicht der Satz von Rice anwenden lässt? Konkret hätt ich da jetzt zum Beispiel an den fleißigen Biber gedacht, bei dem die TM gesucht ist, die am meisten Schritte auf dem Arbeitsband macht.
Ich habe auf meinem Kanal schon einige Videos zu Reduktionen vom Halteproblem (nicht *auf* das Halteproblem, sondern *vom* Halteproblem, aber ich denke das meintest Du). Die findest Du in der Playlist über Berechenbarkeit.