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. Universität Stuttgart, Stuttgart
  2. Universität Passau, Passau
  3. TGW Software Services GmbH, Regensburg, Teunz
  4. Bosch Gruppe, Leonberg

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. (reduzierte Überstände, Restposten & Co.)
  2. 119,90€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Gigabit: 5G-Planungen gehen völlig an den Nutzern vorbei
Gigabit
5G-Planungen gehen völlig an den Nutzern vorbei

Fast täglich hören wir Erklärungen aus der Telekommunikationsbranche, was 5G erfüllen müsse und warum sonst das Ende der Welt drohe. Wir haben die Konzerngruppen nach Interessenlage kartografiert.
Ein IMHO von Achim Sawall

  1. Bundesnetzagentur Regierung will gemeinsames 5G-Netz auf dem Land durchsetzen
  2. Mobilfunk Telekom will 5G-Infrastruktur mit anderen gemeinsam nutzen
  3. Fixed Wireless Access Nokia bringt mehrere 100 MBit/s mit LTE ins Festnetz

Mate 20 Pro im Hands on: Huawei bringt drei Brennweiten und mehr für 1.000 Euro
Mate 20 Pro im Hands on
Huawei bringt drei Brennweiten und mehr für 1.000 Euro

Huawei hat mit dem Mate 20 Pro seine Dreifachkamera überarbeitet: Der monochrome Sensor ist einer Ultraweitwinkelkamera gewichen. Gleichzeitig bietet das Smartphone zahlreiche technische Extras wie einen Fingerabdrucksensor unter dem Display und einen sehr leistungsfähigen Schnelllader.
Ein Hands on von Tobias Költzsch

  1. Keine Spionagepanik Regierung wird chinesische 5G-Ausrüster nicht ausschließen
  2. Watch GT Huawei bringt Smartwatch ohne Wear OS auf den Markt
  3. Ascend 910/310 Huaweis AI-Chips sollen Google und Nvidia schlagen

Probefahrt mit Tesla Model 3: Wie auf Schienen übers Golden Gate
Probefahrt mit Tesla Model 3
Wie auf Schienen übers Golden Gate

Die Produktion des Tesla Model 3 für den europäischen Markt wird gerade vorbereitet. Golem.de hat einen Tag in und um San Francisco getestet, was Käufer von dem Elektroauto erwarten können.
Ein Erfahrungsbericht von Friedhelm Greis

  1. 1.000 Autos pro Tag Tesla baut das hunderttausendste Model 3
  2. Goodwood Festival of Speed Tesla bringt Model 3 erstmals offiziell nach Europa
  3. Elektroauto Produktionsziel des Tesla Model 3 erreicht

  1. Windows 10: Retpoline-Patch gegen Spectre verbessert CPU-Leistung
    Windows 10
    Retpoline-Patch gegen Spectre verbessert CPU-Leistung

    In der kommenden Version von Windows 10 will Microsoft Retpoline gegen Spectre einführen. Das verlangsame das System nicht mehr so stark und bringe gerade auf älteren PCs eine spürbare Verbesserung. Allerdings dauert die Einführung noch ein wenig.

  2. Richard Stallman: GNU-Projekt bekommt Richtlinien für gute Kommunikation
    Richard Stallman
    GNU-Projekt bekommt Richtlinien für gute Kommunikation

    Ausgelöst durch die Diskussionen um den Code-of-Conduct in Linux und anderen Projekten erhält nun auch das GNU-Projekt Richtlinien zur Kommunikation. Strikte Vorschriften sollen aber explizit nicht gemacht werden, entschied Projektgründer Richard Stallman.

  3. Fertigungsprozess: Intel soll 10-nm-Node eingestampft haben
    Fertigungsprozess
    Intel soll 10-nm-Node eingestampft haben

    Abseits eines einzelnen Prozessors aus der Cannon-Lake-Serie hat Intel bisher keine 10-nm-Chips vorzuweisen. Das soll auch so bleiben: Angeblich hat der Hersteller die erfolglose Fertigung komplett eingestellt und wechselt direkt auf 7 nm samt extrem-ultravioletter Strahlung.


  1. 17:58

  2. 17:50

  3. 17:42

  4. 17:14

  5. 16:47

  6. 16:33

  7. 13:53

  8. 13:33