Abo
  1. Foren
  2. Kommentare
  3. Wissenschaft
  4. Alle Kommentare zum Artikel
  5. › Quantencomputer: Alleskönner mit…

Komplexitätsklasse nach PSPACE

  1. Thema

Neues Thema Ansicht wechseln


  1. Komplexitätsklasse nach PSPACE

    Autor: johnsonmonsen 25.04.17 - 16:38

    Hallo zusammen!

    Im Artikel wurde als Komplexitätsklasse für Schach & Go PSPACE genannt, bei der die Speichermenge polynominal anwächst. Das kann ich mir gut vorstellen, da sich der Spielbaum mit der Fläche auffächert, während alle möglichen Kombinationen von Zuständen als Exponenten eingehen, wie beim Rundreiseproblem.

    Leider konnte ich keine Komplexitätsklasse finden, bei welcher auch der Speicherplatz exponentiell ansteigt. Ein entsprechendes Beispiel fände ich auch sehr interessant, was könnte das sein? Meine Kenntnisse in Berechenbarkeitstheorie sind bestenfalls rudimentär.

    Vielen Dank für Eure Antworten :-)!

  2. Re: Komplexitätsklasse nach PSPACE

    Autor: DerSchildkrötenmann 25.04.17 - 17:02

    Wie wäre es mit der Komplexitätsklasse EXPSPACE? :)
    Die Definition werde ich hier nichtnocheinmal runter rattern, die sollte es z.B. auf Wikipedia zum nachlesen geben.
    Eine Möglichkeit EXPSPACE Probleme zu erhalten ist, sich ein beliebiges PSPACE Problem zu nehmen und die Inputs semantisch äquivalent "aufzublähen". Das ist zwar ein bisschen hingetrickst, ändert aber am Ergebnis nichts. (Außer dass mehr Platz für die Berechnung benötigt wird :)

    Ein Beispiel ist das Problem festzustellen, ob zwei gegebene reguläre Ausdrücke die gleiche Sprache erzeugen, wobei die Ausdrücke nur die Operatoren Vereinigung, Verkettung, Kleenesche Hülle und Verdopplung enthalten.

  3. Re: Komplexitätsklasse nach PSPACE

    Autor: johnsonmonsen 25.04.17 - 17:21

    Hallo DerSchildkrötenmann,

    vielen Dank für den Hinweis, ich war mir nicht sicher. Gerade die Wikipedia-Einträge überforden mich bezüglich des mathematischen Verständnissen teils recht schnell. Daher bin ich immer auf der Suche nach nachvollziehbaren Beispielen. Für die Komplexitätsklassen darunter gibt es ja einige.

    Wenn ich richtig verstanden habe, gibt es für EXPSPACE gar keine "klassischen" Beispiele aus dem Alltag, wie es z.B. bei der Spiel-Komplexität der Fall ist. Vielleicht am ehesten noch in der Biologie, bei der Erforschung der Proteinfaltung. Hier ist der gesuchte Ausdruck quasi das niedrigste Energieniveau. Vielleicht ist das Durchprobieren der Zustände aber auch nur eine Permutation. Keine Ahnung.

    Jedenfalls besten Dank und viele Grüße :-)!

  4. Re: Komplexitätsklasse nach PSPACE

    Autor: DerSchildkrötenmann 25.04.17 - 17:40

    Mit dem Gefühl überfordert zu sein bezogen auf die Komplexitätstheorie sind sie nicht alleine. Das geht (aus persönlicher Erfahrung nach bestem Wissen und Gewissen) geschätzt 75% der Informatik Studenten so. Es ist leider ein sehr schwer greifbares Thema.
    Nichtsdestotrotz bitte nicht damit aufhöhren den eigenen Horizont zu erweitern.
    Viele Grüße

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Zum Login

Stellenmarkt
  1. CHEFS CULINAR West GmbH & Co. KG, Weeze
  2. DomainFactory GmbH, Ismaning
  3. Heraeus infosystems GmbH, Hanau
  4. L-Bank Staatsbank für Baden-Württemberg, Karlsruhe

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Blu-ray-Angebote
  1. 29,97€
  2. (Blu-rays, 4K UHDs, Box-Sets und Steelbooks im Angebot)
  3. 24,99€ (Vorbesteller-Preisgarantie)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Microsoft: Großer Widerstand gegen US-Zugriff auf weltweite Cloud-Daten
Microsoft
Großer Widerstand gegen US-Zugriff auf weltweite Cloud-Daten
  1. Newsletter-Dienst Mailchimp verrät E-Mail-Adressen von Newsletter-Abonnenten
  2. Marktforschung Viele Android-Apps kollidieren mit kommendem EU-Datenschutz
  3. Loki App zeigt Inhalte je nach Stimmung des Nutzers an

Updates: Wie man Spectre und Meltdown loswird
Updates
Wie man Spectre und Meltdown loswird
  1. Hacker One Nur 20 Prozent der Bounty-Jäger hacken in Vollzeit
  2. Wallet Programmierbare Kreditkarte mit ePaper, Akku und Mobilfunk
  3. Fehlalarm Falsche Raketenwarnung verunsichert Hawaii

Ein Jahr Trump: Der Cheerleader der deregulierten Wirtschaft
Ein Jahr Trump
Der Cheerleader der deregulierten Wirtschaft
  1. US-Wahl 2016 Twitter findet weitere russische Manipulationskonten
  2. F-52 Trump verkauft Kampfjets aus Call of Duty
  3. Raumfahrtpolitik Amerika will wieder zum Mond - und noch viel weiter

  1. Festnetz und Mobilfunk: Telekom kämpft mit Zerstörungen durch den Orkan Friederike
    Festnetz und Mobilfunk
    Telekom kämpft mit Zerstörungen durch den Orkan Friederike

    Trotz großem Einsatz vieler Techniker sind einige Tausend Kunden der Telekom nach dem Orkan Friederike noch ohne Netzversorgung. Eine ganze Reihe der Schadensstellen sind noch nicht erreichbar.

  2. God of War: Papa Kratos kämpft ab April 2018
    God of War
    Papa Kratos kämpft ab April 2018

    Sony hat den Veröffentlichungstermin für das nächste God of War bekanntgegeben: Ende April 2018 wird sich Hauptfigur Kratos auf der Playstation 4 in Kämpfe mit anderen Göttern stürzen - und versuchen, seinem Sohn ein guter Papa zu sein.

  3. Domain: Richard Gutjahr pfändet Compact-online.de
    Domain
    Richard Gutjahr pfändet Compact-online.de

    Wegen ausstehender Kosten für eine einstweilige Verfügung hat Richard Gutjahr die Domain Compact-online.de pfänden lassen. Das Magazin hatte wahrheitswidrige Behauptungen über den Journalisten verbreitet.


  1. 18:19

  2. 18:08

  3. 17:53

  4. 17:42

  5. 17:33

  6. 17:27

  7. 17:14

  8. 16:14