The complexity of analog computation

DOI10.1016/0378-4754(86)90105-9zbMath0594.68040OpenAlexW2084237314MaRDI QIDQ1077163

Kenneth Steiglitz, Bradley W. Dickinson, Anastasios Vergis

Publication date: 1986

Published in: Mathematics and Computers in Simulation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0378-4754(86)90105-9

zbMATH Keywords

combinatorial optimizationordinary differential equationsspin glassesNP-complete problemsanalog computers3-SATstrong version of Church's thesis

Mathematics Subject Classification ID

Related Items (19)

An analog characterization of the Grzegorczyk hierarchy ⋮ Analog computation via neural networks ⋮ A neural sorting network with O(1) time complexity ⋮ Checking local optimality in constrained quadratic programming is NP- hard ⋮ On the global minimization of a convex function under general nonconvex constraints ⋮ Some mathematical limitations of the general-purpose analog computer ⋮ Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation ⋮ The nature of the extended analog computer ⋮ Physical Computational Complexity and First-order Logic ⋮ Iteration, inequalities, and differentiability in analog computers ⋮ Unconventional complexity measures for unconventional computers ⋮ Solving the generalized subset sum problem with a light based device ⋮ On the computational power of molecular heat engines ⋮ How much can analog and hybrid systems be proved (super-)Turing ⋮ Exact cover with light ⋮ Solving the subset-sum problem with a light-based device ⋮ Digital simulation of analog computation and Church's thesis ⋮ How quantum is the speedup in adiabatic unstructured search? ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• ``Neural computation of decisions in optimization problems
• The wave equation with computable initial data such that its unique solution is not computable
• Noncomputability in models of physical phenomena
• The differential analyzer. A new machine for solving differential equations
• Collective Computation With Continuous Variables
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• The NP-completeness column: An ongoing guide
• Link-Length Minimization in Networks
• On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
• Mathematical Theory of the Differential Analyzer

This page was built for publication: The complexity of analog computation