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. PSI Energie Gas & Öl, Essen
  2. Lotum GmbH, Bad Nauheim
  3. ENERCON GmbH, Aurich
  4. Dataport, verschiedene Standorte (Home-Office)

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Spiele-Angebote
  1. für 2€ (nur für Neukunden)
  2. 59,99€ mit Vorbesteller-Preisgarantie (Release 26.02.)
  3. (-55%) 8,99€
  4. 23,49€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Magnetfeld: Wenn der Nordpol wandern geht
Magnetfeld
Wenn der Nordpol wandern geht

Das Erdmagnetfeld macht nicht das, was Geoforscher erwartet hatten - Nachjustierungen am irdischen Magnetmodell sind erforderlich.
Ein Bericht von Dirk Eidemüller

  1. Ökostrom Wie Norddeutschland die Energiewende vormacht
  2. Computational Periscopy Forscher sehen mit einfacher Digitalkamera um die Ecke
  3. Optoakustik US-Forscher flüstern per Laser ins Ohr

Ottobock: Wie ein Exoskelett die Arbeit erleichtert
Ottobock
Wie ein Exoskelett die Arbeit erleichtert

Es verleiht zwar keine Superkräfte. Bei der Arbeit in unbequemer Haltung zum Beispiel mit dem Akkuschrauber unterstützt das Exoskelett Paexo von Ottobock aber gut, wie wir herausgefunden haben. Exoskelette mit aktiver Unterstützung sind in der Entwicklung.
Ein Erfahrungsbericht von Werner Pluta


    Karma-Spyware: Wie US-Auftragsspione beliebige iPhones hackten
    Karma-Spyware
    Wie US-Auftragsspione beliebige iPhones hackten

    Eine Spionageabteilung im Auftrag der Vereinigten Arabischen Emirate soll die iPhones von Aktivisten, Diplomaten und ausländischen Regierungschefs gehackt haben. Das Tool sei wie Weihnachten gewesen, sagte eine frühere NSA-Mitarbeiterin und Ex-Kollegin von Edward Snowden.
    Ein Bericht von Friedhelm Greis

    1. Update O2-Nutzer berichten über eSIM-Ausfälle beim iPhone
    2. Apple iPhone 11 soll Trio-Kamerasystem erhalten
    3. iPhone mit eSIM im Test Endlich Dual-SIM auf dem iPhone

    1. Uploadfilter: EU-Kommission bezeichnet Reformkritiker als "Mob"
      Uploadfilter
      EU-Kommission bezeichnet Reformkritiker als "Mob"

      In der Debatte über die Reform des EU-Urheberrechts verschärft sich der Ton. Während die EU-Kommission Vergleiche mit dem Brexit-Referendum zieht und Unions-Politiker von Fake-Kampagnen sprechen, gehen Tausende Gegner von Uploadfiltern in Köln auf die Straße.

    2. Datenschutz: 18.000 Android-Apps spionieren Nutzer unzulässig aus
      Datenschutz
      18.000 Android-Apps spionieren Nutzer unzulässig aus

      Selbst populäre Apps mit Hunderten Millionen Nutzern verstoßen gegen die Werberichtlinien von Google. Das Unternehmen reagierte monatelang nicht auf die Vorwürfe.

    3. Erneuerbare Energien: Shell übernimmt Heimakku-Hersteller Sonnen
      Erneuerbare Energien
      Shell übernimmt Heimakku-Hersteller Sonnen

      Der Erdölkonzern Shell setzt sein Engagement im Bereich erneuerbare Energien fort. Nun kauft das Unternehmen einen Konkurrenten für Teslas Powerwalls aus dem Allgäu.


    1. 16:51

    2. 13:16

    3. 11:39

    4. 09:02

    5. 19:17

    6. 18:18

    7. 17:45

    8. 16:20