Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Persistente Transinformation in SAT-Lösungsalgorithmen
Autor
Kein bestimmter Bereich Persistente Transinformation in SAT-Lösungsalgorithmen
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 36
  Themenstart: 2021-07-23

Hallo Leute, Hier stellte ich ein Maß für Emergenz vor, die Persistente Transinformation (Peristent Mutual Information) und wendete sie auf die Logistic Map an. Ich wollte ursprünglich aber Komplexitätsklassen, also P und NP Probleme danach absuchen Hier der Hintergrund meiner Überlegungen, eine Diskussion auf dem Forum. Deshalb suchte ich nach einer für informationstheoretische Messungen wie die Persistente Transinformation geeignete Darstellung von SAT Problemen. Ich fand ein zeit-kontinuierliches deterministisches dynamische System das das Lösen von SAT-Problemen analog simuliert. Hier im Forum bat ich nach Unterstützung für das Reverse Engineering dieses Algorithmus bekam aber letztlich von einem der Autoren von diesem Werk hier einen Python-Code zugesendet. Ich fuhr fort und ließ unterschiedliche SAT-Probleme laufen (2,3,4,5,10) mit jeweils verschiedener clause-to-variable-ratio. Ausgabe waren jeweils die kontinuierlichen Werte unter einen Spin gesetzter Variablen auf dem Weg zu einer Lösung (-1=False,1=True), ähnlich dem linken Diagramm: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_spin_variable.jpg (Rechtes Diagramm zeigt die zur Berechnung benötigten Lagrange-Multiplikatoren) Ich nahm nun für jedes k-SAT Problem mit spezifischer clause-to-variable-ratio den Output jeder Variable und wendete den eingangs erwähnten Algorithmus zum Messen des emergenten Informationsgehalts eines Systems an und plottete das Ergebnis jeder Variable auf ein gemeinsames Diagramm. Hier die Ergebnisse für 3SAT unterschiedlicher clause-to-variable-ratio: (x-Achse ist der Weg zu einer Lösung, y-Achse der Gehalt an persistenter Transinformation, jeder farbige Punkt repräsentiert jeweils eine Variable) https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_3SAT_Figure_1.0.png https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_3SAT_Figure_2.2.png https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_3SAT_Figure_4.2.png https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_3SAT_Figure_8.0.png Andere SAT-Klassen (2,4,5,10) zeigten identische Muster, sodass ich erst enttäuscht war, keine großen Unterschiede zwischen Problemen in P und NP zu finden, doch: Vergleicht man die Ergebnisse mit der Phasenverschiebung bei einem 3SAT unter unterschiedlichen clause-to-variable-ratios https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_slide_4.jpg zeigt sich fast eine simultane 1:1 Übereinstimmung. Bei genauerem hinschauen wurde auch deutlich, dass die SAT-Klassen jeweils unterschiedliche Stärke der Dynamik zeigen, hier zur Verdeutlichung ein 2SAT und ein 5SAT jeweils an der clause-to-variable-ratio 2.2 und 3.2: Clause-to-variable-ratio 2.2: 2SAT: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_2SAT_Figure_2.2.png 5SAT: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_5SAT_Figure_2.2.png Clause-to-variable-ratio 3.2: 2SAT: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_2SAT_Figure_3.2.png 5SAT: https://matheplanet.com/matheplanet/nuke/html/uploads/b/50876_5SAT_Figure_3.2.png Ich bin überrascht von dem Ergebniss. Zum einen sagt es auf den ersten Blick nichts über eine Grenze zwischen P und NP aus (alle SAT-Klassen zeigen ein ähnliches Schema), andererseits wird ein Muster deutlich, dass genau dem ersten SAT-Problem in NP, dem 3SAT entspricht. Emergente Eigenschaften sind Eigenschaften von dynamischen Systemen, die man nicht auf Eigenschaften der Teile des zugrundeliegenden Systems ableiten kann ("Die Summe ist mehr wie ihre Teile"). Das es solche Vorgänge überhaupt gibt, ist extrem umstritten, obwohl es in unterschiedlichen Wissenschaftsfeldern Ansätze gibt. Auch mathematisch kann man zum Beispiel Eigenschaften eines Zellulären Automat als emergent betrachten, weil das (komplexere) Verhalten nicht in jede einzelne Zelle einprogrammiert wurde. Was meint Ihr dazu? Sind die Berechnungen falsch? Handelt es sich um Artefakte des zugrundeliegenden Algorithmus (der ja immerhin ein Analog Computer simuliert)? Ist das Konzept der Persistenten Transinformation an sich inkonsistent, aber warum zeigen sich dann die Übereinstimmung mit der Commputational Hardness von 3SAT-Problemen?


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1741
  Beitrag No.1, eingetragen 2021-07-24

Hallo Nunie! Ich werde wenn es meine Zeit zulässt mal Deine Gedankengänge nachvollziehen. Ich habe mich hier auf dem Matheplaneten (a) mit dem Rundreiseproblem (TSP) und dem Ameisenalgorithmus beschäftigt Dort ist ein für mich schwieriges Problem die 96 Städte Tour durch Frankreich "Tour de France". (b) mit Job Shop Scheduling Dort ist für mich ein schwieriges Problem z.B. das 15x15 Problem LA40. Wenn Du für (a) oder (b) schnelle Algorithmen finden würdest, könnte ich Dir sagen, dass Deine Ansätze gut sind. Viele Grüße Ronald


   Profil
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 36
  Beitrag No.2, vom Themenstarter, eingetragen 2021-07-24

Hallo Ronald, gut das du nach einer Anwendung fragst. Ich kenne nur das TSP von dem angenommen wird, es liegt in NP. Man würde es wie in meinem Beispiel in ein analoges System übersetzen (eventuell indem man es erst in ein 3SAT Problem übersetzt) um einfacher die statistischen und informationstheoretischen Gegebenheiten zeitkontinuierlich zu studieren um eine optimale Lösung zu finden. Mein Ansatz suggeriert aber eine untere Grenze, da sich Lösungen von NP Problemen übersetzt in statistische Mechanik auf einer "komplexen Zeitebene" befinden könnten (siehe Imaginary timehier), was der Ansatz Persistenter Transinformation nahe legt, das lässt sich nur bedingt (verlustfrei) reduzieren (ähnlich den reelen oder komplexen Zahlen, die man nur nährungsweise in rationale Zahlen umwandeln kann). Vielleicht könnte man mit diesem Ansatz ja heuristische Methoden verbessern indem man mithilfe (natürlich dann NP schweren) Algorithmen eine grobe "Topographie" erstellt zum Beispiel für die TSP, aber wie das ganze dann aussehen soll, hab ich noch weniger Ahnung.


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1741
  Beitrag No.3, eingetragen 2021-07-25

Hallo Nunie! Eventuell könnte man die gelösten SAT-Probleme vergleichen mit schnellen SAT-Lösern. (Lösungszeit, Qualität der Lösung) Ich weiß momentan nur nicht wie man SAT-Probleme schnell löst... Vielleicht mittels lokaler Suche. Ich würde versuchen (Lokale Suche): 1.Idee erstelle eine Zufallsbelegung. Nachbarschaft? Variable k an/aus Viele Grüße Ronald


   Profil
Nunie
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.12.2018
Mitteilungen: 36
  Beitrag No.4, vom Themenstarter, eingetragen 2021-07-25

Um das nochmal klar zu stellen: Ich habe mit dem Algorithmus nichts zu tun. Ich verwende ihn nur, um Komplexität zu untersuchen. Wenn du Vergleiche zwischen diesem Algorithmus und anderen schon etablierten SAT-Solvern sehen möchtest, lies bitte hier das entsprechende Paper. Da wird auf deine Frage eingegangen. Es zeigt sich und das ist faszinierend: Der emulierte Analog-SAT Solver hat die gleiche Performance wie ein nicht-emulierter (nicht-analoger) SAT-Solver (z.B. MiniSAT).


   Profil
Nunie hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]