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. Encory GmbH, Unterschleissheim
  2. Rabobank International Frankfurt Branch, Frankfurt am Main
  3. MTU Friedrichshafen GmbH, Friedrichshafen
  4. via 3C - Career Consulting Company GmbH, Home-Office

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. 334,00€
  2. 83,90€
  3. 259€ + Versand oder kostenlose Marktabholung (aktuell günstigste GTX 1070 Mini)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Mobile-Games-Auslese: Games-Kunstwerke für die Hosentasche
Mobile-Games-Auslese
Games-Kunstwerke für die Hosentasche

Cultist Simulator, Photographs, Dungeon Warfare 2 und mehr: Diesen Monat lockt eine besonders hochkarätige Auswahl an kniffligen, gruseligen und komplexen Games an die mobilen Spielgeräte.
Von Rainer Sigl

  1. Spielebranche Auch buntes Spieleblut ist in China künftig verboten
  2. Remake Agent XIII kämpft wieder um seine Identität
  3. Workers & Resources im Test Vorwärts immer, rückwärts nimmer

Lightyear One: Luxus-Elektroauto fährt auch mit Solarstrom
Lightyear One
Luxus-Elektroauto fährt auch mit Solarstrom

Ein niederländisches Jungunternehmen hat ein ungewöhnliches Fahrzeug entwickelt, das Luxus und Umweltfreundlichkeit kombiniert. Solarzellen auf dem Dach erhöhen die Reichweite um bis zu 220 Kilometer.
Von Wolfgang Kempkens

  1. EZ-Pod Renault-Miniauto soll Stadtverkehr in Kolonne fahren
  2. Elektromobilität EnBW will weitere 2.000 Schnellladepunkte errichten
  3. Elektromobilität Verkehrsminister will Elektroautos länger und mehr fördern

Azure Speech Service: Microsofts Demos entstehen im fensterlosen Nerd-Keller
Azure Speech Service
Microsofts Demos entstehen im fensterlosen Nerd-Keller

Build 2019 Moderne Architektur, große Fenster, ein Zen-Garten: Microsofts Campus wirkt außen modern und aufgeräumt. Präsentationen entstehen trotzdem in einem fensterlosen Raum, in dem sich Hardware und Werkzeug stapeln. Microsoft zeigt dort auch eine ungeskriptete Version seiner Spracherkennungssoftware.
Von Oliver Nickel

  1. Beta Writer Algorithmus schreibt wissenschaftliches Buch
  2. Google Neuer KI-Rat soll Googles ethische Richtlinien umsetzen
  3. Affectiva KI erkennt die Gefühle von Autofahrern

  1. Customer First: SAP-Anwender sind in der Landschaft gefangen
    Customer First
    SAP-Anwender sind in der Landschaft gefangen

    SAP-Kunden sind treu, weil sie die eingeführte SAP-Landschaft nicht so einfach ablösen können. Doch sie bleiben auch deswegen, weil die Geschäftsprozesse gut unterstützt werden.

  2. Konsolenleak: Microsoft stellt angeblich nur Specs der nächsten Xbox vor
    Konsolenleak
    Microsoft stellt angeblich nur Specs der nächsten Xbox vor

    Die Veröffentlichungstermine von Spielen wie Cyberpunk 2077 und Gears 5, dazu die wichtigsten Spezifikationen der nächsten Xbox möchte Microsoft laut einem Leak während der Pressekonferenz auf der E3 vorstellen. Gerüchte gibt es auch über die Streamingpläne von Nintendo.

  3. FCC: Regulierer für Übernahme von Sprint durch T-Mobile US
    FCC
    Regulierer für Übernahme von Sprint durch T-Mobile US

    Nach offenbar weitgehenden Zugeständnissen beim Netzausbau auf dem Land und bei 5G hat der Regulierer in den USA dem Kauf von Sprint zugestimmt. Für die Telekom steigen damit die Kosten.


  1. 18:21

  2. 18:06

  3. 16:27

  4. 16:14

  5. 15:59

  6. 15:15

  7. 15:00

  8. 14:38