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. Notion Systems GmbH, Schwetzingen
  2. ACS PharmaProtect GmbH, Berlin
  3. SEG Automotive Germany GmbH, Stuttgart-Weilimdorf
  4. Deutsches Komitee für UNICEF e. V., Köln

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. täglich neue Deals bei Alternate.de
  2. 119,90€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Apple Mac Mini (Late 2018) im Test: Tolles teures Teil - aber für wen?
Apple Mac Mini (Late 2018) im Test
Tolles teures Teil - aber für wen?

Der Mac Mini ist ein gutes Gerät, wenngleich der Preis für die Einstiegsvariante von Apple arg hoch angesetzt wurde und mehr Speicher(platz) viel Geld kostet. Für 4K-Videoschnitt eignet sich der Mac Mini nur selten und generell fragen wir uns, wer ihn kaufen soll.
Ein Test von Marc Sauter

  1. Apple Mac Mini wird grau und schnell
  2. Neue Produkte Apple will Mac Mini und Macbook Air neu auflegen

Need for Speed 3 Hot Pursuit (1998): El Nino, Polizeifunk und Lichtgewitter in Rot-Blau
Need for Speed 3 Hot Pursuit (1998)
El Nino, Polizeifunk und Lichtgewitter in Rot-Blau

Golem retro_ Electronic Arts ist berühmt und berüchtigt für jährliche Updates und Neuveröffentlichungen. Was der Publisher aber 1998 für digitale Raser auffuhr, ist in puncto Dramatik bei Verfolgungsjagden bis heute unerreicht.
Von Michael Wieczorek


    Requiem zur Cebit: Es war einmal die beste Messe
    Requiem zur Cebit
    Es war einmal die beste Messe

    Nach 33 Jahren ist Schluss mit der Cebit und das ist mehr als schade. Wir waren dabei, als sie noch nicht nur die größte, sondern auch die beste Messe der Welt war - und haben dann erlebt, wie Trends verschlafen wurden. Ein Nachruf.
    Von Nico Ernst

    1. IT-Messe Die Cebit wird eingestellt

    1. Epic Games Store: Fortnite allein reicht (noch) nicht gegen Steam
      Epic Games Store
      Fortnite allein reicht (noch) nicht gegen Steam

      Regelmäßig kostenlose Spiele, bessere Bedingungen für Entwickler und Publisher und Fortnite als Verkaufsschlager: Der Games Store von Epic könnte zur ernsthaften Konkurrenz für Steam werden. Dafür muss das Angebot aber noch deutlich ausgebaut werden.

    2. T-Mobile Polska: Telekom verspricht flächendeckendes 5G-Netz in Polen
      T-Mobile Polska
      Telekom verspricht flächendeckendes 5G-Netz in Polen

      Während es in Deutschland nicht möglich sein soll, wird im Zentrum von Warschau ein 5G-Netz gestartet und die Telekom-Tochter T-Mobile Polska verspricht "5G-Netzabdeckung für das ganze Land".

    3. Kollaboration: Nextcloud 15 mit Mastodon und mehr Sicherheit
      Kollaboration
      Nextcloud 15 mit Mastodon und mehr Sicherheit

      In der neuen Version der freien Kollaborationsplattform Nextcloud können Nutzer direkt in den Twitter-Konkurrenten Mastodon posten und Admins Zwei-Faktor-Authentifizierung erzwingen. Außerdem wurde das gemeinsame Bearbeiten von Dokumenten mit Videochat angereichert.


    1. 14:00

    2. 13:39

    3. 12:55

    4. 12:36

    5. 12:06

    6. 11:30

    7. 11:15

    8. 11:00