Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Elimination of parameters in the polynomial hierarchy
Autore:
Koiran, P;
Indirizzi:
Ecole Normale Super Lyon, CNRS, LIP, F-69364 Lyon 07, France Ecole NormaleSuper Lyon Lyon France 07 RS, LIP, F-69364 Lyon 07, France
Titolo Testata:
THEORETICAL COMPUTER SCIENCE
fascicolo: 1-2, volume: 215, anno: 1999,
pagine: 289 - 304
SICI:
0304-3975(19990228)215:1-2<289:EOPITP>2.0.ZU;2-0
Fonte:
ISI
Lingua:
ENG
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
18
Recensione:
Indirizzi per estratti:
Indirizzo: Koiran, P Ecoleceormale Super Lyon, CNRS, LIP, 46 Allee Italie, F-69364 Lyon 07, Fran Ecole Normale Super Lyon 46 Allee Italie Lyon France 07 7, Fran
Citazione:
P. Koiran, "Elimination of parameters in the polynomial hierarchy", THEOR COMP, 215(1-2), 1999, pp. 289-304

Abstract

Blum, Cucker, Shub and Smale have shown that the problem "P =NP?" has the same answer in all algebraically closed fields of characteristic 0. We generalize this result to the polynomial hierarchy: if it collapses over an algebraically closed field of characteristic 0, then it must collapse at the same level over all algebraically closed fields of characteristic 0. The main ingredient of their proof was a theorem on the elimination of parameters,which we also extend to the polynomial hierarchy. Similar but somewhat weaker results hold in positive characteristic. The present paper updates a technical report (LIP Research Report 97-37) with the same title, and in particular includes new results on interactive protocols and boolean parts. (C) 1999-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 30/03/20 alle ore 13:26:24