Können Differentialgleichungen in ihre eigenen Komplexitätsklassen eingeteilt werden?

10

Dank der Komplexität der Berechnungen wurden die Probleme insgesamt klassifiziert. Aber ist es in Differentialgleichungen möglich, Differentialgleichungen in Abhängigkeit von ihrer Rechenstruktur zu klassifizieren?

Wenn beispielsweise eine inhomogene Gleichung erster Ordnung vergleichsweise schwer zu lösen ist als eine homogene Gleichung 100. Ordnung, können sie dann als separate Konvexitätsklassen klassifiziert werden, wenn die zu lösende Methode dieselbe war? Wenn wir den Lösungsprozess variieren, wie zufällig sollen die Lösungen, ihre Existenz und Stabilität sowie andere Eigenschaften variieren?

Ich würde annehmen, dass ich teilweise davon überzeugt bin, dass das Lösen von Differentialgleichungen NP-schwer sein könnte:

/mathpro/158068/simple-example-of-why-differential-equations-can-be-np-hard

Dieser Artikel:

http://www.cs.princeton.edu/~ken/MCS86.pdf

hat mich gezwungen, nach dem Umfang der rechnerischen Komplexität gemäß der Solvabalität von Differentialgleichungen zu fragen. Ausgehend von gewöhnlichen Differentialgleichungen könnten wir Teil-, Verzögerungs-, Differenzgleichungen usw. klassifizieren.

Ich hatte einmal daran gedacht, dynamische Programmierung unter Verwendung der Iterationen zu integrieren, die berechnet wurden, während eine Lösung angenähert wurde, verlor mich aber irgendwo.

Sonamtex
quelle
1
Angesichts der Tatsache, dass (Lösen) von Diophantin-Gleichungen ein rechnerisches Komplexitätsmodell haben kann und dass mehrere Klassen von ODEs (z. B. ODEs mit konstantem Koeffizienten) auf Diophantin-Gleichungen abgebildet werden können, gibt dies einen Hinweis, der getan werden kann
Nikos M.

Antworten:

5

Eine erste Beobachtung in Richtung der Entscheidbarkeit von ODEs ist dieses Papier von Avigad, Clarke und Gao, das die Komplexität der Entscheidbarkeit klassifiziert , bei der Lösungen innerhalb eines bestimmten begrenzten Fehlers (das "Delta") in einem zu finden sind Richtung.δ

Eines der Hauptergebnisse ist, dass die Lösbarkeit von ( Lipschitz-kontinuierlichen ) ODEs -vollständig ist.δPSPACE

Cody
quelle
Vielen Dank. Was ich aber suche, ist ein System zur Klassifizierung aller Differentialgleichungen in eine bestimmte Art von Komplexitätsklassen; wo das Reduzieren von Problemen bedeuten würde: Eine Differentialgleichung kann gelöst werden, wenn (und nur wenn) es eine andere gibt, die gelöst werden kann.
Sonamtex