003 – P versus NP

In der dritten Folge des Formeltier-Podcasts ist jetzt endlich mal der Informatiker am Wort und überfällt uns gleich mit einer Formel, die eigentlich gar keine Formel ist. Es geht um  “P versus NP”; um das berühmte mathematische Problem das immer noch ungelöst ist und die Frage stellt, wie groß der Aufwand sein muss, wenn Computer Probleme lösen. Oder ist das vielleicht durch nur eine Ausrede, wenn die Programmierer keine komplizierten Programme schreiben wollen? Darüber haben wir diskutiert und auch über die Folgen die eine Lösung des P-NP-Problems mit sich bringen würde. Und natürlich über jede Menge andere Themen.

Da steht nix von P-NP drin!

5 thoughts on “003 – P versus NP

  1. kleiner technischer Kommentar: wäre es möglich, einfach einen stinknormalen link auf das mp3 unter den player zu schreiben? aus irgendeinem Grund ist es so wie es jetzt ist unter Android krampfig, die Datei zu saugen. Und eine Auswahlbox mit genau einem Eintrag ist ja auch aweng seltsam.

    bedankt!

  2. Ich finde den Podcast ein echt schönes Format.

    Als jemand, der sich im Studium etwas intensiver mit der Problematik auseinander gesetzt hat, hab ich einige inhaltliche Anmerkungen.
    Zum Einen zur Definition von NP. Im Podcast kam es ein wenig so rüber, als ob alle Probleme mit exponentieller Laufzeit in NP liegen würden. Das ist ja nicht unbedingt so. Wir kennen Probleme, deren Laufzeit nach oben durch einen exponentiellen Ausdruck beschränkt sind, von denen wir jedoch nicht wissen, ob sie in NP liegen (und bei vielen auch annehmen, dass dies nicht der Fall ist). Hier fällt so weit ich weiß z.B. die Frage nach der Existenz einer Gewinnstrategie bei Schach oder ähnlichem rein.

    Zudem wurde angesprochen, dass P!=NP nicht gezeigt werden könnte. Das ist so nicht ganz richtig. Was stimmt, ist dass (fast) allen Beweistechniken, die in der Komplexitätstheorie angewendet werden, und mit denen andere Dinge, wie zum Beispiel die nicht Entscheidbarkeit/Berechenbarkeit von Sprachen gezeigt werden nicht verwendet werden können. Das Stichwort hier sind die sogenannten “relativierend Beweise”, also alle Beweise, die auch mit den sogenannten Orakelturingmaschinen noch funktionieren. Mit diesen kann P!=NP nicht gezeigt werden, da mit Orakelturingmaschinen sowohl P=NP, als auch P!=NP gezeigt werden kann.

  3. Könnte es sich bei dem kurz angerissenen Rechner, bei dem das Gravitationsgesetz schon fest verdrahtet ist, um einen Analogrechner handeln? Die bilden ja physikalische Gesetzmäßigkeiten nach, indem man diese auf elektrische Schaltungen (oder gar mechanische Vorrichtungen) mit analogen (sic!) Eigenschaften zum Problem überträgt, und dann das Ergebnis quasi instantan als Analogwert am Ausgang der Schaltung erhält.

    Analogrechner sind allerdings kein Thema in der Informatik, die sich ausschließlich mit Digitalrechnern beschäftigt.

    Vielleicht war aber auch dieser Ansatz gemeint: einen FPGA (frei programmierbare Logik-Schaltung) auf das Lösen von bestimmten Gleichungen wie etwa denen der Gravitation zu programmieren. Da werden Logikschaltungen zur Lösung solcher Gleichungen fest verdrahtet. Ein FPGA kann wie ein EPROM beschrieben und wieder gelöscht werden, wobei man beim Beschreiben eine bestimmte Schaltung der Logikbausteine (Addierer, Multiplizierer, Speicher etc.) generieren kann. Man kann FPGAs mit ein paar hundert MHz takten. Hier wird in der Tat digital gerechnet.

    http://hackaday.com/2017/01/02/gravity-simulations-with-an-fpga/

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.