Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
A WEAK VERSION OF THE BLUM, SHUB, AND SMALE MODEL
Autore:
KOIRAN P;
Indirizzi:
ECOLE NORMALE SUPER LYON,CNRS,LAB INFORMAT PARALLELISME F-69364 LYON FRANCE
Titolo Testata:
Journal of computer and system sciences
fascicolo: 1, volume: 54, anno: 1997,
pagine: 177 - 189
SICI:
0022-0000(1997)54:1<177:AWVOTB>2.0.ZU;2-C
Fonte:
ISI
Lingua:
ENG
Soggetto:
SEMI-ALGEBRAIC SETS; COMPUTATION; COMPLEXITY; NUMBERS;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Science Citation Index Expanded
Citazioni:
24
Recensione:
Indirizzi per estratti:
Citazione:
P. Koiran, "A WEAK VERSION OF THE BLUM, SHUB, AND SMALE MODEL", Journal of computer and system sciences, 54(1), 1997, pp. 177-189

Abstract

We propose a weak version of the Blum-Shub-Smale model of computationover the real numbers. In this weak model only a ''moderate'' usage of multiplications and divisions is allowed. The class of boolean languages recognizable in polynomial rime is shown to be the complexity class P/poly. The main tool is a result on the existence of small rational points in semi-algebraic sets which is of independent interest. As an application, we generalize recent results of Siegelmann and Sonlag on recurrent neural networks, and of Maass on feedforward nets. A preliminary version of this paper was presented at the 1993 IEEE Symposium on Foundations of Computer Science. Additional results include: an efficient simulation of order-free real Turing machines by probabilistic Turing machines in the full Blum-Shub-Smale model; the strict inclusion of the real polynomial hierarchy in weak exponential time. (C) 1997 Academic Press.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 02/04/20 alle ore 05:56:04