Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2502.05278 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911060967030784 |
|---|---|
| author | Kayser, Leonie |
| author_facet | Kayser, Leonie |
| contents | The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980s. In recent years, the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms. We investigate the computational complexity of the subalgebra membership problem and degree bounds. In particular, we show completeness for the complexity class EXPSPACE and prove PSPACE-completeness for homogeneous algebras. We highlight parallels and differences compared to the settings of ideals, and also look at important classes of polynomials such as monomial algebras. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05278 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Polynomial Subalgebras Kayser, Leonie Computational Complexity Commutative Algebra Algebraic Geometry 08A30, 13P10, 14Q20 F.3.2; I.1.3 The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980s. In recent years, the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms. We investigate the computational complexity of the subalgebra membership problem and degree bounds. In particular, we show completeness for the complexity class EXPSPACE and prove PSPACE-completeness for homogeneous algebras. We highlight parallels and differences compared to the settings of ideals, and also look at important classes of polynomials such as monomial algebras. |
| title | Computational Complexity of Polynomial Subalgebras |
| topic | Computational Complexity Commutative Algebra Algebraic Geometry 08A30, 13P10, 14Q20 F.3.2; I.1.3 |
| url | https://arxiv.org/abs/2502.05278 |