On the Complexity of Toric Ideals
Published in preprint, 2019
Recommended citation: Diego Cifuentes, Shmuel Onn (2019). "On the Complexity of Toric Ideals." arXiv:1902.01484. https://arxiv.org/abs/1902.01484
We investigate the computational complexity of problems on toric ideals such as normal forms, Gröbner bases, and Graver bases. We show that all these problems are strongly NP-hard in the general case. Nonetheless, we can derive efficient algorithms by taking advantage of the sparsity pattern of the matrix.