A Universal Scaling Theory for Complexity of Analog Computation

Details A Universal Scaling Theory for Complexity of Analog Computation A Universal Scaling Theory for Complexity of Analog Computation

2005-08-05

arxiv.org/abs/cond-mat/0508152v1

Physics

Condensed Matter

Other Condensed Matter

4 pages, 2 eps figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Universal Scaling Theory for Complexity of Analog Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Universal Scaling Theory for Complexity of Analog Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Universal Scaling Theory for Complexity of Analog Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-248765