×

zbMATH — the first resource for mathematics

The complexity of analog computation. (English) Zbl 0594.68040
Summary: 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 efficienty (in polynomial time) by a digital computer. From this assumption and the assumption that \(P\neq NP\) we can draw conclusions about the operation of physical devices used for computation.
An NP-complete problem, 3-SAT, is reduced to the problem of checking whether a feasible point is a local optimum of an optimization problem. A mechanical device is proposed for the solution of this problem. It encodes variables as shaft angles and uses gears and smooth cams. If we grant strong Church’s thesis, that \(P\neq NP\), and a certain ”downhill principle” governing the physical behavior of the machine, we conclude that it cannot operate successfully while using only polynomial resources. We next prove strong Church’s thesis for a class of analog computers described by well-behaved ordinary differential equations, which we can take as representing part of classical mechanics. We conclude with a comment on the recently discovered connection between spin glasses and combinatorial optimization.

MSC:
68Q25 Analysis of algorithms and problem complexity
68N99 Theory of software
68U20 Simulation (MSC2010)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barahona, F., On the computational complexity of Ising spin Glass models, J. phys., A 15, 3241-3253, (1982)
[2] Bennet, C.H., The thermodynamics of computation—a review, Internat. J. theoret. phys., 21, 905-940, (1982)
[3] C.H. Bennett, On the logical ‘depth’ of sequences and their reducibilities to random sequences, Inform. and Control, to appear.
[4] Bush, V., The differential analyzer, J. franklin inst., 212, 447-488, (1931) · Zbl 0003.06504
[5] Chua, L.O.; Lin, G-N., Nonlinear programming without computation, IEEE trans. circuits and systems, 31, 182-188, (1984)
[6] Church, A., An unsolvable problem of elementary number theory, Amer. J. math., 58, 345-363, (1936), (Reprinted in [7].) · JFM 62.0046.01
[7] Davis, M., The undecidable, (1965), Raven Press Hewlett, NY
[8] Feynman, R.P., Simulating physics with computers, Internat. J. theoret. phys., 21, 467-488, (1982)
[9] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[10] Geman, S.; Geman, D., Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE trans. pattern analysis machine intell., 6, 721-741, (1984) · Zbl 0573.62030
[11] Henrici, P., Discrete variable methods in ordinary differential equations, (1962), Wiley New York · Zbl 0112.34901
[12] Hopfield, J.J.; Tank, D.W., ‘neural’ computation of decisions in optimization problems, Biol. cybernet., 52, 1-12, (1985) · Zbl 0572.68041
[13] J.J. Hopfield and D.W. Tank, Collective computation with continuous variables, in: Disordered Systems and Biological Organization, to appear. · Zbl 1356.92005
[14] Jackson, A., Analog computation, (1960), McGraw-Hill New York · Zbl 0098.10406
[15] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 4, 87-100, (1983) · Zbl 0509.68034
[16] Karplus, W.; Soroka, W., Analog methods, (1959), McGraw Hill New York
[17] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[18] Miehle, W., Link-length minimization in networks, Oper res., 6, 232-243, (1958) · Zbl 1414.90068
[19] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[20] Phelan, R.M., Fundamentals of mechanical design, (), 433-434
[21] Plaisted, D., Some polynomial and integer divisibility problems are NP-hard, Proc. 17th ann, symp. on foundations of computer science, 264-267, (1976)
[22] Pour-El, M.B., Abstract computability and its relation to the general purpose analog computer (some connections between logic, differential equations, and analog computers), Trans. amer. math. soc., 199, 1-28, (1974) · Zbl 0296.02022
[23] Pour-El, M.B.; Richards, I., The wave equation with computable initial data such that its unique solution is not computable, Adv. in math., 39, 215-239, (1981) · Zbl 0465.35054
[24] Pour-El, M.B.; Richards, I., Noncomputability in models of physical phenomena, Internat. J. theoret. phys., 21, 553-555, (1982) · Zbl 0493.35057
[25] Pyne, I.B., Linear programming on an electronic analogue computer, Trans. AIEE, part 1, 75, 139-143, (1956)
[26] Shannon, C.E., Mathematical theory of the differential analyzer, J. math. phys., 20, 337-354, (1941) · Zbl 0061.29410
[27] Tank, D.W.; Hopfield, J.J., Simple ‘neural’ optimization networks: an A/D converter, signal decision circuit and a linear programming circuit, (1985), preprint · Zbl 0572.68041
[28] Turing, A.M., On computable numbers, with an application to the entscheidungsproblem, Proc. London math. soc., series 2, Proc. London math. soc., series 2, 43, 544-546, (1937), (Reprinted in [7].) · Zbl 0018.19304
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.