|
| |
|
|
Statistical Physics of Hard Optimization Problems
Zdeborová, Lenka ; Janiš, Václav (advisor) ; Mertens, Stephan (referee) ; Zecchina, Riccardo (referee)
Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly dicult, it is believed that the number of operations required to minimize the cost function is in the most dicult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named "locked" constraint...
|
|
| |
|
|
Statistická fyzika frustrovaných evolučních her
Pištěk, Miroslav ; Janiš, Václav (referee) ; Slanina, František (advisor)
1 Title: Statistical Physics of Frustrated Evolutionary Games Author: Miroslav Pištěk Department: Institute of Theoretical Physics Supervisor: RNDr. František Slanina, CSc. Supervisor's e-mail address: slanina@fzu.cz Abstract: In last two decades, the effort devoted to interdisciplinary research of bounded sources allocation is growing, examining complex phenomena as stock markets or traffic jams. The Minority Game is a multiple-agent model of inevitable frus- tration arising in such situations. It is analytically tractable using the replica method originated in statistical physics of spin glasses. We generalised the Mi- nority Game introducing heterogenous agents. This heterogeneity causes a con- siderable decrease of an average agent's frustration. For many configurations, we achieve even a positive-sum game, which is not possible in the original game variant. This result is in accordance with real stock market data. Keywords: frustrated evolutionary games, Minority Game, Replica method
|
|
|
Influence of a weak electron correlation on electron properties of disordered condensed systems
Šopík, Břetislav ; Janiš, Václav (advisor) ; Drchal, Václav (referee)
Mean-field theory for disordered systems of correlated electrons is constructed, where correlations caused by Hubbard's interaction are included in the Hartree aproximation. This theory is then used to describe influence of electron correlations on density of states and also to describe impact of disorder on a phase diagram of ferromagnetic order. Further the theory is used to obtain a two-particle vertex. Influence of a strength of electron correlations on analycity and behaviour of the two-particle vertex is studied.
|
|
| |
|
| |
guest ::
RSS feed.