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 : Thursday, November 21, 2019 - 2:38:40 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

11

Files downloads

36