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. amedes Medizinische Dienstleistungen GmbH, Hamburg
  2. Württembergische Versicherung AG, Stuttgart
  3. Eckelmann AG, Wiesbaden
  4. SSA SoftSolutions GmbH, Augsburg

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Blu-ray-Angebote
  1. 4,25€
  2. (2 Monate Sky Ticket für nur 4,99€)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Elektromobilität: Regierung bremst bei Anspruch auf private Ladesäulen
Elektromobilität
Regierung bremst bei Anspruch auf private Ladesäulen

Die Anschaffung eines Elektroautos scheitert häufig an der fehlenden Lademöglichkeit am heimischen Parkplatz. Doch die Bundesregierung will vorerst keinen eigenen Gesetzesentwurf für einen Anspruch von Wohnungseigentümern und Mietern vorlegen.
Ein Bericht von Friedhelm Greis

  1. ID Buzz und Crozz Volkswagen will Elektroautos in den USA bauen
  2. PFO Pininfarina plant Elektrosupersportwagen mit 400 km/h
  3. Einride Holzlaster T-Log fährt im Wald elektrisch und autonom

Krankenversicherung: Der Papierkrieg geht weiter
Krankenversicherung
Der Papierkrieg geht weiter

Die Krankenversicherung der Zukunft wird digital und direkt, aber eine tiefgreifende Disruption des Gesundheitswesens à la Amazon wird in Deutschland wohl ausbleiben. Die Beharrungskräfte sind zu groß.
Eine Analyse von Daniel Fallenstein

  1. Imagen Tech KI-System Osteodetect erkennt Knochenbrüche
  2. Medizintechnik Implantat wird per Ultraschall programmiert
  3. Telemedizin Neue Patienten für die Onlinepraxis

Battlefield 5 Closed Alpha angespielt: Schneller sterben, länger tot
Battlefield 5 Closed Alpha angespielt
Schneller sterben, länger tot

Das neue Battlefield bekommt ein bisschen was von Fortnite und wird allgemein realistischer und dynamischer. Wir konnten in der Closed Alpha Eindrücke sammeln und erklären die Änderungen.
Von Michael Wieczorek

  1. Battlefield 5 Mehr Reaktionsmöglichkeiten statt schwächerer Munition
  2. Battlefield 5 Closed Alpha startet mit neuen Systemanforderungen
  3. Battlefield 5 Schatzkisten und Systemanforderungen

  1. Satelliteninternet: Fraunhofer erreicht hohe Datenrate mit Beam Hopping
    Satelliteninternet
    Fraunhofer erreicht hohe Datenrate mit Beam Hopping

    Satelliteninternet kann mit DVB-S2X und Beam Hopping sehr viel mehr als bisher. Das will das Fraunhofer IIS bewiesen haben.

  2. Yager: Berliner Entwicklerstudio stellt Actionspiel The Cycle vor
    Yager
    Berliner Entwicklerstudio stellt Actionspiel The Cycle vor

    In 20 Minuten so viel erledigen wie möglich, Koop-Partnerschaften schließen - und überleben: Das ist das Grundprinzip von The Cycle. Hinter dem Shooter steckt das Entwicklerstudio Yager, vor allem für Spec Ops: The Line und Dreadnought bekannt ist.

  3. Macbook Pro: Apple kann den Core i9 nicht kühlen
    Macbook Pro
    Apple kann den Core i9 nicht kühlen

    Wird auf dem Macbook Pro ein längeres Videoprojekt exportiert, ist das Modell mit Core i9 langsamer als das von 2017, da die CPU unter den Basistakt drosselt. Apple könnte per Firmware-Update eingreifen.


  1. 18:05

  2. 17:46

  3. 17:31

  4. 17:15

  5. 17:00

  6. 15:40

  7. 15:16

  8. 15:00