Schnelle probabilistische Algorithmen zur Verifikation polynomialer Identitäten

Der durchschlagende Erfolg des Rabin-Strassen-Solovay-Primzahl-Algorithmus, zusammen mit der faszinierenden grundlegenden Möglichkeit, dass Axiome der Zufälligkeit eine nützliche fundamentale Quelle mathematischer Wahrheit unabhängig von der standardmäßigen axiomatikanischen Struktur der Mathematik darstellen könnten, legt eine rigorose Suche nach probabilistischen Algorithmen nahe. Zur Veranschaulichung dieser Beobachtung werden verschiedene schnelle probabilistische Algorithmen präsentiert, deren Korrektheitswahrscheinlichkeit a priori garantiert ist, um polynomiale Identitäten und Eigenschaften von Polynomsystemen zu testen. Hilfsalgorithmen zur Berechnung von Resultanten und Sturmfolgen werden ebenfalls gegeben. Die probabilistische Berechnung in der reellen Arithmetik, die zuvor von Davis betrachtet wurde, wird rigoros, jedoch nur in einem speziellen Fall, gerechtfertigt. Sätze der elementaren Geometrie können mit den vorgestellten Techniken wesentlich effizienter bewiesen werden als mit bekannten Ansätzen der künstlichen Intelligenz.