The complexity of irreducible components

Abstract : We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP-complete problem for every fixed d in the Blum-Shub-Smale model of computation over the complex numbers (and is in the Arthur-Merlin class if we assume a bit model of computation). This is the first part of a paper which will eventually provide similar results for semi-algebraic sets.
Document type :
Reports
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101815
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:01 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:16 AM

File

RR1998-10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101815, version 1

Collections

Citation

Pascal Koiran. The complexity of irreducible components. [Research Report] LIP RR-1998-10, Laboratoire de l'informatique du parallélisme. 1998, 2+5p. ⟨hal-02101815⟩

Share

Metrics

Record views

15

Files downloads

9