Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids
type: Item
instance of: scholarly article
title: Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids
zbMATH Open document ID: 0844.05091
DOI: 10.1016/0304-3975(94)00061-1
published in: Theoretical Computer Science
publication date: 1994-12-19T00:00:00Z
review text: The main result (see also the above abstract) of the paper states that if two different functions \(f_1\), \(f_2\) are computed by means of sigmoids with the parallel complexity \(d\), then the difference \(|f_1- f_2|\) grows not slower than \((\exp^{(d)}(p))^{- 1}\) (and not faster than \(\exp^{(d)}(p))\), where \(\exp^{(d)}\) is the \(d\) times iteration of the exponential function and \(p\) is a certain polynomial, thus one cannot rather good approximate \(f_1\) with a precise parallel complexity \(d\) by means of a function \(f_2\) with a less parallel complexity. The number of zeros in the intervals of a function computed by sigmoids is estimated and all the obtained bounds are sharp.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 34A30
zbMATH DE Number: 695890
zbMATH Keywords: differential equations
zbMATH Keywords: derivation theorem
zbMATH Keywords: sigmoids
zbMATH Keywords: parallel complexity
author: Dima Grigoriev
reviewed by: Mykola Grygorenko
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)00061-1
OpenAlex ID: W2167314331
cites work: Q5822220
cites work: Siegel normality
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Complexity of factoring and calculating the GCD of linear ordinary differential operators
cites work: Q5330830
cites work: Q3255437
cites work: Q3999699
cites work: Liouvillian Solutions of n-th Order Homogeneous Linear Differential Equations
Wikidata QID: Q127065836
description: scientific article; zbMATH DE number 695890