Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Emergenter Ansatz für P versus NP
Autor
Kein bestimmter Bereich Emergenter Ansatz für P versus NP
Nunie
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.12.2018
Mitteilungen: 39
  Themenstart: 2020-06-27

Innerhalb meines Studiums bin ich mit P versus NP konfrontiert und musste dabei an einen Artikel von 2018 im Spektrum denken, welcher sich mit emergenten Systemen auseinandersetzt. Grundlage war eine Arbeit von Mathematikern und Neurologen 2013. Darin wird gezeigt, dass die Existenz fixierter (=determinierten) mikroskopischer Teile in einem System nicht zwangsläufig zur Determiniertheit aller weiteren (makroskopischen) Teile führen muss. Ein Beispiel war, dass wenn man die Moleküle des Gehirns einer Person X untersucht, man sehr viel schwerer auf den zukünftigen Ort derselben kommen würde als wenn man die Lebensrealität dieser Person ("Makroebene") miteinbeziehen würde, in der sich die sehr viel effektivere Information befindet, nämlich dass Person X gerade gegessen hat und langsam müde wird, es schon spät ist und sich deshalb die Moleküle vermutlich bald in dessen Bett aufhalten werden. Da man die Ebene des Maximums effektiver Information gefunden hat, wird es so sehr einfach sein, diese Lösung auf Korrektheit zu prüfen. Was hat das jetzt mit P versus NP zu tun? Nimmt man das System eines NP vollständigen Problems kommt man nach Definition schwerer auf die Lösung, als diese zu überprüfen. Somit gibt es eine Klasse in diesem System, deren kausale Struktur einfacher zu überprüfen, also stärker sein muss, als andere. Nach Hoel, dem Autor der genannten Arbeit hätte diese Klasse das Maximum effektiver Information in diesem System. Nach Shannon könnte man das System dieses NP vollständigen Problems maximal auf diese Klasse komprimieren. Irgendetwas in mir findet gefallen daran, sich mit dieser Herangehensweise zu beschäftigen. Da diese Art Grundlagenforschung aber soviele Themen und Momente streift, die erstmal nichts mit dem konkreten Studienalltag zu tun haben, würde ich euch aus Mangel an eigener Expertise bitten, schnell einen Bullshit-Test durchzuführen, damit ich mich auf andere Dinge konzentrieren kann 😉. vielen dank


   Profil
Informatik-Rentner
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 29.10.2015
Mitteilungen: 62
Wohnort: Essen
  Beitrag No.1, eingetragen 2020-07-21

Meine rein persönliche Meinung: Ein interessanter Gedankengang. Allerdings kann man mit diesem Thema sehr viel Zeit verschwenden ohne ein Ergebnis zu bekommen und wenn du Student bist, solltest du dich mit diesem Thema nur in deiner Freizeit auseinandersetzen ... Habe selber während meines Studiums einen Gedanken zu dem Thema gehabt und verfolgt und dadurch 1 Jahr verschenkt.


   Profil
Nunie
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.12.2018
Mitteilungen: 39
  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-21

Hey Informatik-Rentner, kurz vorweg zu deinem Rat zum Studium: Ich bin Frührentner aufgrund einer chronischen Erkrankung, das Studium ist also eher Hobby, da wirtschaftliche Karriere gar nicht angstrebt wird. Es sind diese Knobeleien und philosophischen Fragen, die mich am Leben halten ;-). Ich habe herausgefunden, dass es in den letzten zehn Jahren zumindest theoretisch gelungen ist, Emergenz zu messen: Mit der sogenannten Persistant Mutual Information, eine Variante der Multivariate Mutual Information ( https://en.wikipedia.org/wiki/Multivariate_mutual_information ). Man hat Anstäze von emergentem Verhalten in der logistischen Gleichung entdeckt (https://warwick.ac.uk/fac/sci/physics/staff/academic/rball/pmi/quantifying_emergence_11.04.16.pdf Seite 11). Es wäre jetzt zu zeigen, dass ein Algorithmus zum Lösen eines 2SAT-Problems (der ein 3SAT-Problem nicht lösen kann), keine Persistant Mutual Information erzeugt. Man kann 2SAT durch ein übereinander gelagertes 2 Dimensionales Venn-Diagramm darstellen, bei einem 3SAT Problem bräuchte man 3 Dimensionales Venn-Diagramm für die Transinformation. Interessanterweise braucht ein emergentes System auch ein 3 Dimensionales Diagramm für die Darstellung von Information im temporalen Kontext ( https://journals.aps.org/pre/abstract/10.1103/PhysRevE.93.022143 ). Nachtrag und Vorschlag einer Herangehensweise: Da jedes nichtlineare System das in Abhängigkeit eines Parameters chaotisches oder reguläres Verhalten zeigt mit einer Feigenbaum-Konstante dargestellt werden kann, würde das bedeuten, wenn wir Probleme in P und NP so formulieren, wäre es möglich, ein Feigenbaum-Diagramm dieser Systeme abzubilden. Dann könnten wir die Persistan Mutual Information auslesen und eventuell zeigen, dass Lösungen von P-Probleme im Gegensatz zu NP-Problemen unabhängig dieser wäre.


   Profil
willyengland
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 01.05.2016
Mitteilungen: 339
  Beitrag No.3, eingetragen 2020-07-21

Nur zur allgemeinen Info: Es gibt anscheinend neue Erkenntnisse zum P/NP ... Problem. Im Spektrum Heft 7/2020 ist ein Artikel dazu. "Kann ein Computer die Lösung eines Problems immer in vertretbarer Zeit überprüfen, egal wie schwierig es ist? Ja, sagt ein neuer Beweis – und widerlegt damit eine ganze Reihe etablierter Vermutungen aus der Mathematik und Physik." arxiv.org Artikel dazu: https://arxiv.org/abs/2001.04383


   Profil
Nunie
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.12.2018
Mitteilungen: 39
  Beitrag No.4, vom Themenstarter, eingetragen 2020-07-21

Danke für den Tip. hier der Artikel März 2020. Dieses Ergebniss ist wirklich genial: 1. Komplexitätstheorie scheint in der Lage zu sein, ein Link zwischen dynamischer Quantenmechanik und statischer Mathematik/Logik mit Hilfe der Informatik herzustellen. Wir kommen einer Quanten-Mathematik näher. Das wäre dringend nötig und könnte uns bei weiteren "Millenium-Problemen" weiterhelfen (Riemann Hypothese). 2. "Anders als häufig angenommen, kann man ein unendliches System nicht immer beliebig genau durch ein endliches annähern" Besser könnte man Emergenz wie man sie im modernen Kontext definiert nicht formulieren. Und: Gödels Unvollständigkeitssatz (->Halte-Problem, Kolmogorov-Komplexität) gilt also auch im MIP*. Dieser beschreibt ja eben, das ein (unendliches) System sich selbst von innen heraus nicht vollständig abdecken kann oder der Versuch unendlich lange dauern würde. Eventuell schauen wir mit den Komplexitätsklassen schon auf eine Quanten-Mathematik ohne uns dem bewusst zu sein.


   Profil
Nunie
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 03.12.2018
Mitteilungen: 39
  Beitrag No.5, vom Themenstarter, eingetragen 2021-07-23

Hier findet ihr einige meiner Berechnungen zu dem Thema. (Ich konnte es nicht lassen....)


   Profil
Nunie hat die Antworten auf ihre/seine Frage gesehen.
Nunie wird per Mail über neue Antworten informiert.

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]