Algebraische Rechenmodelle

Algebraische Rechenmodelle sind in der theoretischen Informatik, insbesondere in der Komplexitätstheorie, solche Versuche, den Begriff des Berechenbaren formell zu fassen, die davon ausgehen, dass exakte Operationen auf den reellen oder auch den komplexen Zahlen durchführbar sind. Aufgrund dieser anspruchsvollen Voraussetzung handelt es sich um rein abstrakte Rechenmodelle, ohne Möglichkeiten einer physikalischen Realisierung.

Analog zu der Theorie von Automaten, die auf diskreten Strukturen operieren, ergeben sich dann ausgehend von den algebraischen Modellen ganz ähnliche Fragen:

Gibt es in algebraischen Rechenmodellen unentscheidbare Probleme? (Ja)
Wie sehen die analog erklärten Komplexitätsklassen der P, NP und NP-vollständigen Probleme (etc.) in diesem Rechenmodellen aus? (Diese drei Klassen lassen sich jeweils sinnvoll erklären, aber sie fallen nicht mit den diskreten Klassen zusammen. Das analog gestellte P-NP-Problem ist auch für algebraische Rechenmodelle derzeit offen)
Welche Struktur haben entscheidbare Probleme? (Führt über $\mathbb {R}$ zum Begriff der semi-algebraischen Mengen)

BSS-Maschinen

Ein kanonischer Ansatz, sich algebraischen Rechenmodellen zu nähern, sind die nach ihren Beschreibern[1] benannten Blum-Shub-Smale-Maschinen (BSS-Maschinen). Eine Maschine dieser Klasse ist darüber definiert, dass sie genau die folgenden Operationen gestattet:

Die arithmetischen Operationen zwischen zwei Registern auf der zugrunde liegenden Struktur: +, -, ×, ÷.
Zuweisung einer von endlich vielen Konstanten.
Kopierbefehle zweier fester Register.
Vergleiche mit der Null, also „= 0“ über $\mathbb {C}$ und „ $\geq 0$ “ über $\mathbb {R}$ .
Ein Haltebefehl.

Eine BSS-Maschine lässt sich dann angeben durch einen geordneten Satz von Anweisungen dieser Art, sowie endlich vielen vorgegebenen Konstanten. In der Semantik einer solchen Maschine werden die Anweisungen der Reihe nach ausgeführt, es sei denn, es liegt der Haltebefehl vor – in dem Fall bricht die Rechnung ab – oder eine Vergleichsbedingung ist erfüllt. In diesem Fall springt man zu einem Befehl mit der entsprechenden Nummer, die in dem Vergleichsbefehl mit angegeben ist.

Es gibt noch weitere Versuche, algebraische Rechenmodelle zu erklären, die beispielsweise auch die Wurzelfunktion, oder trigonometrische Operationen zulassen und zu anderen Ergebnissen führen, als die Komplexitätstheorie für BSS-Maschinen.

Literatur

Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale: Complexity and Real Computation, 1998 edition. Auflage, Springer, New York 30. Oktober 1997, ISBN 978-0-387-98281-6.

Saugata Basu, Richard Pollack, Marie-Françoise Coste-Roy: Algorithms in Real Algebraic Geometry, 2nd edition. Auflage, Springer, Berlin ; New York 21. August 2006, ISBN 978-3-540-33098-1.

Peter Bürgisser, Michael Clausen, Amin Shokrollahi, T. Lickteig: Algebraic Complexity Theory, 1997 edition. Auflage, Springer, Berlin ; New York 16. Dezember 1996, ISBN 978-3-540-60582-9.

Einzelnachweise

Lenore Blum, Mike Shub, Steve Smale, others: On a theory of computation and complexity over the real numbers: $ NP $-completeness, recursive functions and universal machines. In: Bulletin (New Series) of the American Mathematical Society. 21, Nr. 1, 1989, S. 1–46.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Lenore Blum, Mike Shub, Steve Smale, others: On a theory of computation and complexity over the real numbers: $ NP $-completeness, recursive functions and universal machines. In: Bulletin (New Series) of the American Mathematical Society. 21, Nr. 1, 1989, S. 1–46.