A universal scaling theory for complexity of analog computation

DOI10.1016/J.PHYSLETA.2007.06.032MaRDI QIDQ716028zbMATH OpenOpenAlexFDO

Authors Yaniv S. Avizrats, Shmuel Fishman, Joshua Feinberg

Publication date 19 April 2011

Published in Physics Letters. A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0508152

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We discuss the computational complexity of solving linear programming problems by means of an analog computer. The latter is modeled by a dynamical system which converges to the optimal vertex solution. We analyze various probability ensembles of linear programming problems. For each one of these we obtain numerically the probability distribution functions of certain quantities which measure the complexity. Remarkably, in the asymptotic limit of very large problems, each of these probability distribution functions reduces to a universal scaling function, depending on a single scaling variable and independent of the details of its parent probability ensemble. These functions are reminiscent of the scaling functions familiar in the theory of phase transitions. The results reported here extend analytical and numerical results obtained recently for the Gaussian ensemble.

Recommendations

• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
• Probabilistic analysis of a differential equation for linear programming
• The complexity of analog computation
• An analog solution of programming problems
• Analog computation with dynamical systems

Cites work

• A theory of complexity for continuous time systems
• Dynamical Systems which Solve Optimization Problems with Linear Constraints
• Hamiltonian structure of dynamical systems which solve linear programming problems
• scientific article; zbMATH DE number 420918 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1324524 (Why is no real title available?)
• scientific article; zbMATH DE number 1738652 (Why is no real title available?)
• scientific article; zbMATH DE number 194534 (Why is no real title available?)
• Probabilistic analysis of a differential equation for linear programming
• Probabilistic Models for Linear Programming
• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
• The Efficiency of the Simplex Method: A Survey

Cited in

(6)

• The complexity of analog computation
• Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
• An analog solution of programming problems
• Linear growth of circuit complexity from Brownian dynamics
• Probabilistic analysis of a differential equation for linear programming
• Computability of analog networks

This page was built for publication: A universal scaling theory for complexity of analog computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716028)