Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Transfer theorems via sign conditions
Autore:
Koiran, P;
Indirizzi:
Ecole Normale Super Lyon, LIP, F-69364 Lyon, France Ecole Normale Super Lyon Lyon France F-69364 , LIP, F-69364 Lyon, France
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 2, volume: 81, anno: 2002,
pagine: 65 - 69
SICI:
0020-0190(20020131)81:2<65:TTVSC>2.0.ZU;2-S
Fonte:
ISI
Lingua:
ENG
Soggetto:
QUANTIFIER ELIMINATION; COMPLEXITY; DIMENSION; MACHINES; REALS;
Keywords:
computational complexity; algebraic complexity; polynomial hierarchy; transfer theorems; sign conditions;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
19
Recensione:
Indirizzi per estratti:
Indirizzo: Koiran, P Ecole Normale Super Lyon, LIP, 46 Allee Italie, F-69364 Lyon, France Ecole Normale Super Lyon 46 Allee Italie Lyon France F-69364 ce
Citazione:
P. Koiran, "Transfer theorems via sign conditions", INF PROCESS, 81(2), 2002, pp. 65-69

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. (C) 2002 Elsevier Science B.V All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 25/01/20 alle ore 01:14:06