Jabarkan Geometri aljabar komputasi dari Geometri aljabar

Kompleksitas asimtotik vs. efisiensi praktis

Algoritme umum dasar dari geometri komputasi memiliki kasus terburuk eksponensial ganda kompleksitas. Lebih tepatnya, jika  adalah derajat maksimal dari polinomial masukan dan  jumlah variabel, kompleksitasnya paling banyak.  untuk beberapa konstanta , dan, untuk beberapa masukan, paling tidak kompleksitasnya  untuk konstanta  lainnya.

Selama 20 tahun terakhir abad ke-20, berbagai algoritme telah diperkenalkan untuk menyelesaikan sub-masalah tertentu dengan kompleksitas yang lebih baik. Sebagian besar algoritme ini memiliki kompleksitas .

Di antara algoritme ini yang memecahkan submasalah dari masalah yang dipecahkan oleh basis Gröbner, salah satunya dapat mengutip  pengujian jika varietas afin kosong  dan  menyelesaikan sistem polinomial takhomogen. Algoritme semacam itu jarang diterapkan karena, pada sebagian besar entri Algoritme F4 dan F5 Faugère memiliki efisiensi praktis yang lebih baik dan mungkin kompleksitas yang serupa atau lebih baik (mungkin karena evaluasi kompleksitas algoritma dasar Gröbner pada kelas entri tertentu adalah tugas yang sulit yang telah dilakukan hanya dalam beberapa kasus khusus).

Algoritme utama geometri aljabar real yang memecahkan masalah yang diselesaikan dengan CAD berhubungan dengan topologi himpunan semi-aljabar. Salah satunya mungkin mengutip menghitung jumlah komponen yang terhubung, menguji jika dua titik berada dalam komponen yang sama atau menghitung stratifikasi Whitney dari himpunan aljabar real . Mereka memiliki kompleksitas , tetapi konstanta yang terlibat oleh notasi  begitu tinggi sehingga menggunakannya untuk memecahkan masalah taktrivial yang secara efektif diselesaikan oleh CAD, tidak mungkin bahkan jika salah satunya dapat menggunakan semua daya komputasi yang ada. Oleh karena itu, algoritme ini belum pernah diimplementasikan dan ini merupakan area penelitian aktif untuk mencari algoritme yang memiliki kompleksitas asimtotik yang baik dan efisiensi praktis yang baik.