On randomized semi-algebraic test complexity (Q1260656): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
| (One intermediate revision by one other user not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1006/jcom.1993.1016 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2032022602 / rank | |||
Normal rank | |||
Latest revision as of 23:31, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On randomized semi-algebraic test complexity |
scientific article |
Statements
On randomized semi-algebraic test complexity (English)
0 references
24 August 1993
0 references
The influence of randomization on the complexity of deciding the membership to semi-algebraic set is discussed. In some cases when a probability error in the answer is allowed, the complexity decreases. A general lower bound on the randomized decision complexity is obtained in the case of an irreducible algebraic set and extended to the case of generic complete intersections of polynomials with the same degree. Some applications to non generic cases (in particular to symmetric functions) are also given. In the introduction various examples are discussed, the next section is devoted to a precise definition of randomized decision trees, then a general lower bound is given and various applications are presented.
0 references
randomized decision complexity
0 references
randomized decision trees
0 references
