Zertifikat

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Zertifikat

Beitrag von sqrt(2) » 10. Sep 2016 22:22

Hallo,

ich verstehe die Funktion von Zertifikaten im Zusammenhang von N und NP noch nicht so ganz.

Zitate sind aus dem Drehbuch Komplexität algorithmischer Probleme.pdf

Frage 1: Zertifikatbeispiel IBAN
- Ist hier die Checksumme das Zertifikat? (Meine ja...)
- Der Prüfualgorithmus nimmt sich die Checksumme (das Zertifikat) und den restl. Input (weitere Zahlen bestehend aus Länderkennung, Bankleitzahl, Kontonr.) her und prüft ob es sich um einen korrekten Input handelt? (Meine ja...)

Frage 2: TSP Beispiel
- Der Prüfalgo würde jetzt die Rundtour (also Zertifikat) hernehmen und prüfen dass "dass diese Sequenz tatsächlich genau Länge n hat, dass jeder einzelne Punkt in der Sequenz vorkommt und dass die Sequenz keine Duplikate enthält". Der Output sollte dann JA sein.

Frage 3: Zitat: Es muss keinen polynomiellen Algorithmus geben, der das Problem löst, sondern es reicht, wenn es ein Zertifikat mit einem Prüfalgorithmus gibt, dessen Komplexität im Worst Case durch ein Polynom nach oben abschätzbar ist.
- P ist die Menge der Entscheidungsprobleme für die es ein Algorithmus gibt der dieses Entscheidungsproblem polynomiell löst mit beliebigen Exponenten => (mathemat. Implikation) Es existiert ein Prüfualgorithmus dessen Komplexität durch ein Polynom nach oben abgeschätzt werden kann. (Meine ja...)
- Ich kann mir das mit dem Prüfalgorithmus so schwer vorstellen, weil ich irgendwie denke: Gibt es einen Prüfalgorithmus der Input und Zertifikat auswerten kann dann hat man doch schon den "richtigen" Algorithmus gefunden der das Problem löst... (Verstehen Sie was ich meine?) - Im Prinzip verstehe ich P = NP weil ein Prüfalgorithmus schon ein korrekter Algorithmus ist und sehe daher nicht das Problem. Was natürlich falsch ist

Frage 4: Reduktion algorithmischer Probleme
- Reduktion hört sich für mich direkt nach geringere Komplexität wenn man X nach Y transformiert. Was ja definitiv falsch ist. (Was mir aber nicht klar ist aber an folgenden Punkten verdeutlicht werden soll)
- DNA Beispiel:
a. Wieso lösen wir das Problem mit dem DNA Vergleich nicht direkt statt es zu transformieren? Ich mein warum mehr Arbeit machen als Nötig (im Sinne von höhere Komplexität)
b. Quasi Antwort auf a? Da wir nicht wissen wie wir DNA's effizient vergleichen können, aber einen Algorithmus kennen der das Problem für kürzeste Pfade löst können wir das Problem auf das Problem für kürzeste Pfade transformieren und erhalten dann unsere Lösung.
c. Woher wissen wir jetzt das die Y (Transformation auf kürzeste Pfade) eine höhere Komplexität als X (das DNA Problem "so" lösen) hat? Was macht uns da so sicher, das ist was ich nicht verstehe... Irgendwie kommt mir das eher wie eine wage Vermutung vor

Frage 5: Eine Polynomielle Reduktion
- Hier muss lediglich die Transformation von X nach Y polynomiell sein, oder? (Meine, ja...)

Frage 6: Definition: Ein Entscheidungsproblem X in NP ist auch in NPC, wenn alle Probleme in NP sich auf X polynomiell reduzieren lassen.
- Wie ist diese harte Definition motiviert? Verstehe ich es so richtig:
Sei X ein beliebiges Entscheidungsproblem aus NP. X ist genau dann in NPC wenn für alle Probleme Y aus NP gilt, dass Y polynomiell zu X transformiert werden kann. (ABER das Lösen des Entscheidungsproblems muss nicht polynomiell sein, oder? [Meine ja...])

Frage 7: Aufbauend auf Frage 6 (Folie 33)
- Gilt P n NPC != {} (Leere Menge) dann bedeutet das, es gibt ein X aus NP das in NPC ist, weshalb sich alle Entscheidungsprobleme Y aus NP polynomiell auf X reduzieren (bzw. transformieren) lassen. (ABER das Lösen von X mus ja nicht Polynomiell erfolgen, oder?)
Da es jetzt dieses X gibt muss P = NP sein, da alle Probleme aus NP sich auf dieses X in polynomieller Zeit reduzieren lassen und dadurch das Entscheidungsproblem aller Probleme Y aus NP polynomiell gelöst werden können? (ABER die Transformation ist ja nur polynomiell und nicht das eigentliche Lösen des Entscheidungsproblems oder?)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Zertifikat

Beitrag von Prof. Karsten Weihe » 11. Sep 2016 06:22

sqrt(2) hat geschrieben: Frage 1: Zertifikatbeispiel IBAN
- Ist hier die Checksumme das Zertifikat? (Meine ja...)
- Der Prüfualgorithmus nimmt sich die Checksumme (das Zertifikat) und den restl. Input (weitere Zahlen bestehend aus Länderkennung, Bankleitzahl, Kontonr.) her und prüft ob es sich um einen korrekten Input handelt? (Meine ja...)
Stimme zu.
sqrt(2) hat geschrieben: Frage 2: TSP Beispiel
- Der Prüfalgo würde jetzt die Rundtour (also Zertifikat) hernehmen und prüfen dass "dass diese Sequenz tatsächlich genau Länge n hat, dass jeder einzelne Punkt in der Sequenz vorkommt und dass die Sequenz keine Duplikate enthält". Der Output sollte dann JA sein.
Höchstens Länge n, ansonsten stimme ich zu.
sqrt(2) hat geschrieben: Frage 3: Zitat: Es muss keinen polynomiellen Algorithmus geben, der das Problem löst, sondern es reicht, wenn es ein Zertifikat mit einem Prüfalgorithmus gibt, dessen Komplexität im Worst Case durch ein Polynom nach oben abschätzbar ist.
Ja, das gilt für algorithmische Probleme in NP.
sqrt(2) hat geschrieben: - P ist die Menge der Entscheidungsprobleme für die es ein Algorithmus gibt der dieses Entscheidungsproblem polynomiell löst mit beliebigen Exponenten => (mathemat. Implikation) Es existiert ein Prüfualgorithmus dessen Komplexität durch ein Polynom nach oben abgeschätzt werden kann. (Meine ja...)
Der erste Satz ist die Definition von P, korrekt. Den zweiten Satz kann man sehen als eine stark verkürzt formulierte Definition von NP oder als eine Aussage über P: Wenn es einen polynomiellen Lösungsalgorithmus gibt, dann gibt es auch einen polynomiellen Prüfalgorithmus. Was meinten Sie?

BTW: Wie üblich in der Mathematik würde ich klarer schreiben: mit beliebigem, aber festem Exponenten.
sqrt(2) hat geschrieben: - Ich kann mir das mit dem Prüfalgorithmus so schwer vorstellen, weil ich irgendwie denke: Gibt es einen Prüfalgorithmus der Input und Zertifikat auswerten kann dann hat man doch schon den "richtigen" Algorithmus gefunden der das Problem löst...
Bei Problemstellungen wie dem TSP, wo eine Lösung das Zertifikat ist, kann der Prüfalgorithmus eine bekannte Lösung überprüfen, aber damit noch lange nicht eine unbekannte Lösung konstruieren. Ein Algorithmus, der letzteres kann, ist ein Lösungsalgorithmus.

Der Checksummenüberprüfer für die IBAN konstruiert ja auch keine Checksumme für gegebene Kontonummer und Bankleitzahl.
sqrt(2) hat geschrieben: Frage 4: Reduktion algorithmischer Probleme
a. Wieso lösen wir das Problem mit dem DNA Vergleich nicht direkt statt es zu transformieren? Ich mein warum mehr Arbeit machen als Nötig (im Sinne von höhere Komplexität)
Wie würden Sie es denn direkt lösen wollen?
sqrt(2) hat geschrieben: b. Quasi Antwort auf a? Da wir nicht wissen wie wir DNA's effizient vergleichen können, aber einen Algorithmus kennen der das Problem für kürzeste Pfade löst können wir das Problem auf das Problem für kürzeste Pfade transformieren und erhalten dann unsere Lösung.
Ja, das würde ich unterschreiben.
sqrt(2) hat geschrieben: c. Woher wissen wir jetzt das die Y (Transformation auf kürzeste Pfade) eine höhere Komplexität als X (das DNA Problem "so" lösen) hat? Was macht uns da so sicher, das ist was ich nicht verstehe... Irgendwie kommt mir das eher wie eine wage Vermutung vor
Die Reduktion von X auf Y ist ein möglicher Algorithmus zur Lösung von X. Sei C die Komplexität dieses Algorithmus. Dann ist die Komplexität von X definitionsgemäß höchstens C.

Wenn die asymptotische Komplexität der Hin- und Rücktransformation vernachlässigbar ist, dann resultiert C aus der Lösung der Y-Instanz, auf die die X-Instanz reduziert wurde. Es gibt also Y-Instanzen mit Komplexität C, und daher muss die Komplexität von Y mindestens C sein. Transitivität ergibt: Y hat eine mindestens so hohe (nicht unbedingt höhere) Komplexität wie X.
sqrt(2) hat geschrieben: Frage 5: Eine Polynomielle Reduktion
- Hier muss lediglich die Transformation von X nach Y polynomiell sein, oder? (Meine, ja...)
Wir betrachten ja nur Entscheidungsprobleme, da ist die Rücktransformation trivial und schnell.
sqrt(2) hat geschrieben: Frage 6: Definition: Ein Entscheidungsproblem X in NP ist auch in NPC, wenn alle Probleme in NP sich auf X polynomiell reduzieren lassen.
- Wie ist diese harte Definition motiviert?
Sie ist dadurch motiviert, dass sie funktioniert: Die interessantesten "schweren" Probleme sind tatsächlich in NPC.
sqrt(2) hat geschrieben: Verstehe ich es so richtig:
Sei X ein beliebiges Entscheidungsproblem aus NP. X ist genau dann in NPC wenn für alle Probleme Y aus NP gilt, dass Y polynomiell zu X transformiert werden kann. (ABER das Lösen des Entscheidungsproblems muss nicht polynomiell sein, oder? [Meine ja...])
Ja, ob das Lösen polynomiell sein muss oder nicht, ist ja gerade die offene Frage P=NP.
sqrt(2) hat geschrieben: Frage 7: Aufbauend auf Frage 6 (Folie 33)
- Gilt P n NPC != {} (Leere Menge) dann bedeutet das, es gibt ein X aus NP das in NPC ist
Nein, es bedeutet doch nach Definition der Schnittmenge: Es gibt ein X aus P, das in NPC ist. Ihre Aussage, dass es ein X aus NP gibt, das in NPC ist, ist äquivalent dazu, dass NPC nicht leer ist, da NPC Teilmenge von NP ist.

Klarer geworden?

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Zertifikat

Beitrag von sqrt(2) » 11. Sep 2016 13:43

Prof. Karsten Weihe hat geschrieben: Wenn es einen polynomiellen Lösungsalgorithmus gibt, dann gibt es auch einen polynomiellen Prüfalgorithmus. Was meinten Sie?
Ja das habe ich probiert zu sagen, passt (:
Prof. Karsten Weihe hat geschrieben: Bei Problemstellungen wie dem TSP, wo eine Lösung das Zertifikat ist, kann der Prüfalgorithmus eine bekannte Lösung überprüfen, aber damit noch lange nicht eine unbekannte Lösung konstruieren.
TSP ist ein Optimierungsproblem. Demnach ist das Entscheidungsproblem JA oder NEIN für gegebenes Zertifikat einfach zu lösen (Prüfalgo in polynomieller Zeit). ABER das Optimierungsproblem bleibt trotzdem schwer, wofür ein geeigneter Lösungsalgorithmus fehlt. Heißt das jedes Entscheidungsproblem ist in P? - Nein. Aber Entscheidungsprobleme sind die einfachsten und deshalb kümmern wir uns um diese.
Prof. Karsten Weihe hat geschrieben: Wie würden Sie es denn direkt lösen wollen?
(...)
Ja, das würde ich unterschreiben.
Alles klar, verstanden.
Prof. Karsten Weihe hat geschrieben: Die Reduktion von X auf Y ist ein möglicher Algorithmus zur Lösung von X. Sei C die Komplexität dieses Algorithmus. Dann ist die Komplexität von X definitionsgemäß höchstens C.
Wo haben wir die Definition?
Prof. Karsten Weihe hat geschrieben: Wenn die asymptotische Komplexität der Hin- und Rücktransformation vernachlässigbar ist, dann resultiert C aus der Lösung der Y-Instanz, auf die die X-Instanz reduziert wurde. 1.Es gibt also Y-Instanzen mit Komplexität C, und daher muss die Komplexität von Y mindestens C sein. 2.Transitivität ergibt: Y hat eine mindestens so hohe (nicht unbedingt höhere) Komplexität wie X.
1. Warum mindestens und nicht maximal oder ungefähr? Kann ja sein das Y die Variante mit der aller höchsten Komplexität war, oder...? (Hier fehlt mir noch der Aha-Effekt mit dem "mindestens".
2. Die Komplexität von Y ist mindestens C. Nach Definition gilt das die Komplexität von X höchstens C ist. Demnach muss Y mindestens so komplex wie X sein. > Verstanden.
Prof. Karsten Weihe hat geschrieben: Nein, es bedeutet doch nach Definition der Schnittmenge: Es gibt ein X aus P, das in NPC ist.
Ist X aus P dann kann man das Entscheidungsproblem von X polynomiell schnell lösen. Das heißt existiert solch ein X und lassen sich alle Probleme in NP auf X polynomiell reduzieren (gemäß der Definition) so gilt P = NP

Beantworten Sie das eig. alles aus dem Stehgreif? (Meine ja ^^)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Zertifikat

Beitrag von Prof. Karsten Weihe » 11. Sep 2016 14:07

sqrt(2) hat geschrieben:
Prof. Karsten Weihe hat geschrieben: Die Reduktion von X auf Y ist ein möglicher Algorithmus zur Lösung von X. Sei C die Komplexität dieses Algorithmus. Dann ist die Komplexität von X definitionsgemäß höchstens C.
Wo haben wir die Definition?
Die Komplexität einer algorithmischen Problemstellung ist die bestmögliche Komplexität irgendeines Algorithmus für diese Problemstellung, also definitionsgemäß nicht größer als die Komplexität irgendeines Algorithmus dafür.
sqrt(2) hat geschrieben:
Prof. Karsten Weihe hat geschrieben: Wenn die asymptotische Komplexität der Hin- und Rücktransformation vernachlässigbar ist, dann resultiert C aus der Lösung der Y-Instanz, auf die die X-Instanz reduziert wurde. 1.Es gibt also Y-Instanzen mit Komplexität C, und daher muss die Komplexität von Y mindestens C sein. 2.Transitivität ergibt: Y hat eine mindestens so hohe (nicht unbedingt höhere) Komplexität wie X.
1. Warum mindestens und nicht maximal oder ungefähr?
Ich hatte in meiner vorherigen Antwort nicht ausformuliert, dass es für mich um die Worst-Case-Komplexität geht. Diese wird determiniert durch die Instanzen mit der höchsten Komplexität. Die Instanzen mit der höchsten Komplexität haben aber naturgemäß mindestens so hohe Komplexität wie irgendwelche anderen Instanzen.
sqrt(2) hat geschrieben: Beantworten Sie das eig. alles aus dem Stehgreif? (Meine ja ^^)
Nein, ich muss manchmal doch recht lange darüber grübeln, was mit der einen oder anderen Frage gemeint sein könnte. :wink:

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Zertifikat

Beitrag von sqrt(2) » 11. Sep 2016 15:26

Prof. Karsten Weihe hat geschrieben: Die Komplexität einer algorithmischen Problemstellung ist die bestmögliche Komplexität irgendeines Algorithmus für diese Problemstellung, also definitionsgemäß nicht größer als die Komplexität irgendeines Algorithmus dafür.
Okay notiert. Dann ist mir das irgendwie durch die Lappen gegangen diese Definition, habe die nirgends so explizit wahrgenommen.
Prof. Karsten Weihe hat geschrieben: Ich hatte in meiner vorherigen Antwort nicht ausformuliert, dass es für mich um die Worst-Case-Komplexität geht. Diese wird determiniert durch die Instanzen mit der höchsten Komplexität. Die Instanzen mit der höchsten Komplexität haben aber naturgemäß mindestens so hohe Komplexität wie irgendwelche anderen Instanzen.
Okay, es ist noch nicht 100% klar, aber ich lasse die Information nochmal sacken, denke in Ruhe drüber nach und komme ggf. nochmal darauf zurück.
Prof. Karsten Weihe hat geschrieben: Nein, ich muss manchmal doch recht lange darüber grübeln, was mit der einen oder anderen Frage gemeint sein könnte.
Okay (:

Vielen Dank für Ihre Ausführliche Antwort.

Antworten

Zurück zu „Archiv“