Transfer theorems via sign conditions

Abstract : We show that P = PSPACE implies the collapse of the boolean polynomial hierarchy over any structure which admits ``efficient enumeration of sign conditions''. This fairly rich class of structures contains in particular R and C.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101937
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:14 AM
Last modification on : Friday, May 17, 2019 - 1:39:20 AM

File

RR2000-13.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101937, version 1

Collections

Citation

Pascal Koiran. Transfer theorems via sign conditions. [Research Report] LIP RR-2000-13, Laboratoire de l'informatique du parallélisme. 2000, 2+7p. ⟨hal-02101937⟩

Share

Metrics

Record views

6

Files downloads

21