The complexity of analog computation

We ask if analog computers can solve NP-complete problems efficiently. Regarding this as unlikely, we formulate a strong version of Church's Thesis: that any analog computer can be simulated efficiently (in polynomial time) by a digital computer. From this assumption and the assumption that P ≠ NP we can draw conclusions about the operation of physical devices used for computation.

MoreLess

Year of publication:	1986
Authors:	Vergis, Anastasios ; Steiglitz, Kenneth ; Dickinson, Bradley
Published in:	Mathematics and Computers in Simulation (MATCOM). - Elsevier, ISSN 0378-4754. - Vol. 28.1986, 2, p. 91-113
Publisher:	Elsevier

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10011050319