Masalah telah, secara keseluruhan, diklasifikasikan, berkat Kompleksitas Komputasi. Tetapi, dalam persamaan diferensial, apakah mungkin untuk mengklasifikasikan persamaan diferensial tergantung pada struktur komputasinya?
Sebagai contoh, jika persamaan non-homogen orde pertama secara komparatif sulit untuk diselesaikan daripada, katakanlah, persamaan homogen urutan ke-100, dapatkah mereka digolongkan sebagai kelas konveksitas yang terpisah, mengingat metode untuk menyelesaikannya sama? Jika kita memvariasikan proses penyelesaian, seberapa acak solusinya, keberadaan dan stabilitasnya, dan sifat-sifat lainnya berbeda?
Saya akan berasumsi bahwa saya sebagian yakin bahwa menyelesaikan persamaan diferensial mungkin NP-Hard:
/mathpro/158068/simple-example-of-why-differential-equations-can-be-np-hard
Artikel ini:
http://www.cs.princeton.edu/~ken/MCS86.pdf
telah memaksa saya meminta ruang lingkup kompleksitas komputasi sesuai dengan solvabality dari Persamaan Diferensial. Dimulai dengan persamaan diferensial biasa, kita bisa mengklasifikasikan sebagian, menunda, persamaan perbedaan dll.
Saya pernah berpikir untuk menggabungkan pemrograman dinamis menggunakan iterasi yang dihitung saat mendekati solusi, tetapi kehilangan diri saya di suatu tempat.
Jawaban:
Pengamatan pertama ke arah decidability dari ODE adalah makalah ini oleh Avigad, Clarke dan Gao, yang mengklasifikasikan kompleksitas -decidability , di mana solusi dapat ditemukan dalam kesalahan terikat tertentu ("delta") dalam satu arah.δ
salah satu hasil utama adalah bahwa solvabilitas ODE ( Lipschitz-continuous ) adalah -complete.P S P A C Eδ PSPACE
sumber