The hardness of polynomial equation solving (Q1430505): Difference between revisions
From MaRDI portal
Created a new Item |
Normalize DOI. |
||
| (5 intermediate revisions by 5 users not shown) | |||
| Property / DOI | |||
| Property / DOI: 10.1007/s10208-002-0065-7 / rank | |||
| Property / describes a project that uses | |||
| Property / describes a project that uses: Kronecker / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2088922099 / rank | |||
Normal rank | |||
| Property / arXiv ID | |||
| Property / arXiv ID: math/0301194 / rank | |||
Normal rank | |||
| Property / DOI | |||
| Property / DOI: 10.1007/S10208-002-0065-7 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 20:16, 10 December 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The hardness of polynomial equation solving |
scientific article |
Statements
The hardness of polynomial equation solving (English)
0 references
27 May 2004
0 references
The authors prove that the nonpolynomial complexity character of the symbolic geometric elimination procedures is a consequence of the information encoded by the particular data structures. The main result is the following. Let be given an arbitrary continuous data structure encoding input and output objects of elimination theory and a universal elimination algorithm solving arbritrary parametric polynomial equation systems. Supposing that the algorithm avoids unnecessary branchings and admits the efficient computation of certain natural limit objects, then the algorithm cannot be a polynomial time one.
0 references
polynomial equations
0 references
elimination
0 references
complexity
0 references
data stuctures
0 references
continuous encoding
0 references
