Physics – Condensed Matter – Other Condensed Matter
Scientific paper
2005-11-14
Physics
Condensed Matter
Other Condensed Matter
22 pages, latex, 12 eps figs
Scientific paper
10.1063/1.2194471
We apply a probabilistic approach to study the computational complexity of analog computers which solve linear programming problems. We analyze numerically various ensembles of linear programming problems and obtain, for each of these ensembles, the probability distribution functions of certain quantities which measure the computational complexity, known as the convergence rate, the barrier and the computation time. We find that in the limit of very large problems these probability distributions are universal scaling functions. In other words, the probability distribution function for each of these three quantities becomes, in the limit of large problem size, a function of a single scaling variable, which is a certain composition of the quantity in question and the size of the system. Moreover, various ensembles studied seem to lead essentially to the same scaling functions, which depend only on the variance of the ensemble. These results extend analytical and numerical results obtained recently for the Gaussian ensemble, and support the conjecture that these scaling functions are universal.
Avizrats Yaniv
Feinberg Joshua
Fishman Shmuel
No associations
LandOfFree
Scaling and Universality of the 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 Scaling and Universality of the Complexity of Analog Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaling and Universality of the Complexity of Analog Computation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-7944