|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Universal Scaling Theory for Complexity of Analog Computation | | Yaniv S. Avizrats
; Joshua Feinberg
; Shmuel Fishman
; | | Date: |
5 Aug 2005 | | Subject: | Other; Computational Complexity | cond-mat.other cs.CC | | 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. | | Source: | arXiv, cond-mat/0508152 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER