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

Komplexitätsklasse nach PSPACE

Anzeige
  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

Anzeige
Stellenmarkt
  1. Sky Deutschland GmbH, Unterföhring bei München
  2. GIGATRONIK Stuttgart GmbH, Stuttgart
  3. weil engineering gmbh, Müllheim
  4. Bonitas Holding GmbH, Herford

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. (reduzierte Überstände, Restposten & Co.)
  2. und Destiny 2 gratis erhalten
  3. und Assassin´s Creed Origins gratis downloaden


Haben wir etwas übersehen?

E-Mail an news@golem.de


Smartphoneversicherungen im Überblick: Teuer und meistens überflüssig
Smartphoneversicherungen im Überblick
Teuer und meistens überflüssig
  1. Winphone 5.0 Trekstor will es nochmal mit Windows 10 Mobile versuchen
  2. Librem 5 Das freie Linux-Smartphone ist finanziert
  3. Aquaris-V- und U2-Reihe BQ stellt neue Smartphones ab 180 Euro vor

Erneuerbare Energien: Siemens leitet die neue Steinzeit ein
Erneuerbare Energien
Siemens leitet die neue Steinzeit ein
  1. Siemens und Schunk Akkufahrzeuge werden mit 600 bis 1.000 Kilowatt aufgeladen
  2. Parkplatz-Erkennung Bosch und Siemens scheitern mit Pilotprojekten

Cubesats: Startup steuert riesigen Satellitenschwarm von Berlin aus
Cubesats
Startup steuert riesigen Satellitenschwarm von Berlin aus
  1. Arkyd-6 Planetary Resources startet bald ein neues Weltraumteleskop
  2. SAEx Internet-Seekabel für Südatlantikinsel St. Helena
  3. Sputnik Piep, piep, kleiner Satellit

  1. SuperSignal: Vodafone Deutschland schaltet Smart-Cells ab
    SuperSignal
    Vodafone Deutschland schaltet Smart-Cells ab

    Nutzer können die von Vodafone zugelassenen Smart-Cells Supersignal nicht mehr betreiben. Zum Jahresende werden die Femtozellen technisch abgeschaltet. Wi-Fi Calling soll hier der Ersatz sein.

  2. Top Gun 3D: Mit VR-Headset kostenlos ins Kino
    Top Gun 3D
    Mit VR-Headset kostenlos ins Kino

    Oculus Rift oder ein anderes VR-Headset aufgesetzt - und ab ins virtuelle Kino: Zusammen mit Paramount Pictures zeigt ein Startup im Dezember 2017 kostenlos den Actionfilm Top Gun 3D.

  3. Übernahme: Marvell kauft Cavium für 6 Milliarden US-Dollar
    Übernahme
    Marvell kauft Cavium für 6 Milliarden US-Dollar

    Konkurrenz für AMD und Intel: Der Chiphersteller Marvell übernimmt Cavium und hat künftig Zugiff auf die ThunderX2 genannten ARM-Server-CPUs. Zudem sollen Synergien unter anderem bei Netzwerk- und Storage-Lösungen entstehen.


  1. 17:26

  2. 17:02

  3. 16:21

  4. 15:59

  5. 15:28

  6. 15:00

  7. 13:46

  8. 12:50