Complexity of Solution of Simultaneous Multivariate Polynomial Equations

Duggirala Meher Krishna; Duggirala Ravi

doi:https://doi.org/10.14445/22315373/IJMTT-V67I5P503

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 67 | Issue 5 | Year 2021 | Article Id. IJMTT-V67I5P503 | DOI : https://doi.org/10.14445/22315373/IJMTT-V67I5P503

Complexity of Solution of Simultaneous Multivariate Polynomial Equations

Duggirala Meher Krishna, Duggirala Ravi

Citation :

Duggirala Meher Krishna, Duggirala Ravi, "Complexity of Solution of Simultaneous Multivariate Polynomial Equations," International Journal of Mathematics Trends and Technology (IJMTT), vol. 67, no. 5, pp. 27-32, 2021. Crossref, https://doi.org/10.14445/22315373/IJMTT-V67I5P503

Abstract

In this paper, an original reduction algorithm for solving simultaneous multivariate polynomial equations is presented. The algorithm is exponential in complexity, but the well-known algorithms, such as the extended Euclidean algorithm and Buchberger's algorithm, are superexponential. The superexponential complexity of the well-known algorithms is due to their not being “minimal” in a certain sense. Buchberger's algorithm produces a Grӧbner basis. The proposed original reduction algorithm achieves the required task via computation of determinants of parametric Sylvester matrices, and produces a Rabin basis, which is shown to be minimal, when two multivariate polynomials are reduced at a time. The minimality of Rabin basis allows us to prove exponential lower bounds for the space complexity of an algebraic proof of certification, for a specific computational problem in the computational complexity class PSPACE, showing that the complexity classes PSPACE and P cannot be the same. It is also shown that the class of languages decidable by probabilistic algorithms with (probabilistic) polynomial time proofs for the membership of input words is not the same as the complexity class P.

Keywords

Extended Euclidean algorithm; Buchberger's algorithm and Grӧbner basis; Parametric Sylvester matrices, Minimality and Rabin basis; Algebraic complexity theory.

References

[1] Bruno Buchberger, An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal, Ph. D. Thesis, University of Innsbruck (1965), English translation by M. Abramson in Journal of Symbolic Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions, 41(3) (2006) 475-511.
[2] D. Castro, M. Giusti, J. Heintz, G. Matera, and L. M. Pardo, The Hardness of Polynomial Equation Solving, Foundations of Computational Mathematics, 3(4) (2003), 347-420.
[3] J.-C. Faugère, A New Efficient Algorithm for Computing Grӧbner Bases (F4), Journal of Pure and Applied Algebra, 139(1) (1999), 61-88.
[4] J.-C. Faugère, A New Efficient Algorithm for Computing Grӧbner Bases without Reduction to Zero (F5), Proc. International Symposium on Symbolic and Algebraic Computation, ACM Press (2002) 75-83.
[5] J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Education (2007).
[6] Adi Shamir, IP = PSPACE, Journal of the ACM, 39(4) (1992), 869-877.
[7] André Weil, Number of Solutions of Equations in Finite Fields, Bulletin of the American Mathematical Society, 55(5) (1949), 497-508.