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. Robert Bosch GmbH, Leonberg
  2. DomainFactory GmbH, Ismaning
  3. über MAISEL CONSULTING GmbH & Co. KG, Raum Nürnberg
  4. UnternehmerTUM GmbH, Garching bei München

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Spiele-Angebote
  1. 26,99€
  2. 39,99€
  3. (-75%) 14,99€
  4. (-50%) 29,99€


Haben wir etwas übersehen?

E-Mail an news@golem.de


PC Building Simulator im Test: Wenn's doch nur in der Realität so einfach wäre
PC Building Simulator im Test
Wenn's doch nur in der Realität so einfach wäre
  1. Apple iOS 11.3.1 behebt Probleme mit Austausch-Displays
  2. Patterson und Hennessy ACM zeichnet RISC-Entwickler aus
  3. Airtop2 Inferno Compulab kühlt GTX 1080 und i7-7700K passiv

Hyundai Ioniq im Test: Mit Hartmut in der Sauna
Hyundai Ioniq im Test
Mit Hartmut in der Sauna
  1. Byton Maos Staatslimousine soll zum Elektroauto werden
  2. ISO 15118 Elektroautos ohne Karte oder App laden
  3. MW Motors Elektroauto im Retro-Look mit Radnabenmotoren

P20 Pro im Hands on: Huawei erhöht die Anzahl der Kameras - und den Preis
P20 Pro im Hands on
Huawei erhöht die Anzahl der Kameras - und den Preis
  1. Android Huawei präsentiert drei neue Smartphones ab 120 Euro
  2. P20 Pro im Kameratest Huaweis Dreifach-Kamera schlägt die Konkurrenz
  3. Wie Samsung Huawei soll noch für dieses Jahr faltbares Smartphone planen

  1. FRK: Verkauf von Unitymedia an Vodafone nur bei Öffnung der Netze
    FRK
    Verkauf von Unitymedia an Vodafone nur bei Öffnung der Netze

    Ein kleinerer Kabelnetzbetreiberverband ist nicht gegen ein Zusammengehen von Unitymedia mit Vodafone. Aber dann sollten die Netze nach dem Open-Access-Prinzip geöffnet werden.

  2. Dell: Neue Optiplex-Systeme in drei Größen und mit Dual-GPUs
    Dell
    Neue Optiplex-Systeme in drei Größen und mit Dual-GPUs

    Dell stellt gleich drei neue Optiplex-Serien in jeweils drei Größen vor. Dazu zählen Minirechner und Midi-Tower, in die gleich zwei Grafikkarten hineinpassen. Die Auswahl an Prozessoren reicht vom kleinsten Celeron bis zum Core-i7-Sechskerner - allerdings ohne Ryzen-Alternative.

  3. Jakarta EE: Enterprise-Java soll besser in der Cloud laufen
    Jakarta EE
    Enterprise-Java soll besser in der Cloud laufen

    Das von Oracle an die Eclipse-Foundation übertragene Enterprise-Java soll künftig besser mit Cloud- und Containertechnologie wie Docker und Kubernetes genutzt werden können. Der Code soll außerdem schneller gemeinsam mit der Community weiterentwickelt werden.


  1. 14:26

  2. 12:45

  3. 12:30

  4. 12:10

  5. 11:52

  6. 11:45

  7. 11:30

  8. 11:15