𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the polynomial IO-complexity

✍ Scribed by JoséD.P. Rolim

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
808 KB
Volume
33
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The complexity of the characteristic and
The complexity of the characteristic and the minimal polynomial
✍ Thanh Minh Hoang; Thomas Thierauf 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 188 KB

We investigate the complexity of (1) computing the characteristic polynomial, the minimal polynomial, and all the invariant factors of an integer matrix, and of (2) verifying them, when the coe cients are given as input. It is known that each coe cient of the characteristic polynomial of a matrix A

Some Complexity Results for Polynomial I
Some Complexity Results for Polynomial Ideals
✍ Ernst W. Mayr 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 184 KB

In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the rationals. For instance, a polynomial ideal membership problem is a (w + 1)-tuple P = ( f, g 1 , g 2

On the Deterministic Complexity of Facto
On the Deterministic Complexity of Factoring Polynomials
✍ Shuhong Gao 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 345 KB

The paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the works of and , the general problem reduces deterministically in polynomial time to finding a proper factor of any squarefree and completely splitting