Yahoo Clever wird am 4. Mai 2021 (Eastern Time, Zeitzone US-Ostküste) eingestellt. Ab dem 20. April 2021 (Eastern Time) ist die Website von Yahoo Clever nur noch im reinen Lesemodus verfügbar. Andere Yahoo Produkte oder Dienste oder Ihr Yahoo Account sind von diesen Änderungen nicht betroffen. Auf dieser Hilfeseite finden Sie weitere Informationen zur Einstellung von Yahoo Clever und dazu, wie Sie Ihre Daten herunterladen.
Beweis das Clique polynomial reduzierbar auf Subgraph Iso ist?
könnte mir das jemand formal zeigen und schritt für Schritt erklären? :/
2 Antworten
- vor 4 Jahren
Hier in diesem link gibt es eine Analyse der Seite auf Wikipedia.
https://cs.stackexchange.com/questions/64509/subgr...
Darin heisst es allerdings auch, dass die Gruppen H und Kk identisch sind, da H die komplette Masse der Individuen von Kk ist.
Daher ist das Problem von den Gruppen G und H das gleiche, wie das Problem der Gruppe G und k was für mich ehrlich gesagt ziemlich einleuchtend klingt. H und k sind ja in der gleichen Gruppe enthalten.
Im Isomorphen Subgraphen hingegen sind G und H nicht miteinander bekannt und H ist auch nicht bekannt mit sämtlichen Graphen sodass daraus erfolgt, dass H eigentlich nur dann mit allen Graphen bekannt sein kann, wenn daraus erfolgt, dass H die komplette Gruppe Kk aufweist.
Eigentlich finde ich das nicht so schwer zu verstehen, aber vielleicht ein einfaches Beispiel:
Du kennst fünf Leute mit den Namen Heinz, Karl, Detlef, Moritz und Falco.
Heinz und Karl kennen sich gegenseitig, Detlef und Moritz kennen sich gegenseitig und Falco kennt Detlef und Karl. Er ist praktisch das Bindeglied, der es ermöglichen kann, dass nicht nur DU die gesamte Gruppe kennst, sondern auch Falco kann unter Umständen Heinz und Moritz kennen, oder zumindest von den beiden mal irgendwas erzählt bekommen haben. Daher ist das Cliquenproblem reduzierbar auf Subgraph Iso, denn Falco ist praktisch Iso und Iso ist praktisch der unbekannte Faktor, den niemand einschätzen kann, weil keiner wirklich was genaues über ihn weiss.
Allerdings ist das eigentlich höhere Mathematik und naja, ich habs jetzt einfach mal auf ne Gruppe von Menschen umgelegt, um dir das Problem zu verdeutlichen.
P.S.: In der Programmierung soll das wohl ähnlich sein hab ich mal irgendwo gelesen. Es gibt immer wieder Fehler, die sich daraus berechnen, dass irgendwo in der Programmstruktur ein ganz bestimmter Bekannter Fehler auftaucht, der nur in bestimmten Situationen anfällt. Dieser Fehler kann aber ein Programm so derartig behindern, dass es irgendwann einfach nicht mehr starten kann und daher neu auf einen Rechner aufgespielt werden muss. Eigentlich ganz simpel, wenn Du mich fragst.
P.S.: Ich hoffe, ich habe jetzt niemanden komplett verwirrt mit meinen Ausführungen...
