Complexity subsets pspace

Autor/Urheber:

Hand drawn in Inkscape Qef

Shortlink:

https://dewiki.de/b/25689

Quelle:

Wikimedia Commons

Größe:

485 x 441 Pixel (17316 Bytes)

Beschreibung:

A representation of the relation among complexity classes, which are subsets of each other.

Lizenz:

Public domain

Credit:

Own work by uploader, intended to replace bitmap image illustrating same thing

Bild teilen:

         

Weitere Informationen zur Lizenz des Bildes finden Sie hier. Letzte Aktualisierung: Tue, 09 Aug 2022 13:36:24 GMT

Relevante Artikel

In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands. Bei Problemen wird dabei stets das „kostengünstigste“ Lösungsverfahren angenommen. Der Aufwand ist im Allgemeinen abhängig von der „Größe“ der Eingabe, wie viele Elemente sie umfasst. Abgeschätzt wird der asymptotische Aufwand, also für sehr viele Eingabeelemente. Dabei zeigt sich, dass die Probleme bzgl. ihres Aufwands Gruppen bilden, deren Aufwand für große Eingabemengen auf ähnliche Weise anwächst; diese Gruppen werden Komplexitätsklassen genannt. Eine Komplexitätsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschränkten Berechnungsmodell berechnen lassen. .. weiterlesen

In der Komplexitätstheorie steht EXPTIME für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch beschränkter Zeit entschieden werden können. ist dabei ein beliebiges Polynom in der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also: .. weiterlesen

In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können. .. weiterlesen