PHASETRANS · Phase transitions in computational complexity and formal verification: towards generic and realistic approaches
6РП — Действия „Мария Кюри“
- Период
- 2007-03-01 → 2009-02-28
- Финансиране от ЕС
- 80 000 €
- Участници
- 1
- Схема
- IRG
Линиите свързват координатора с партньорите. За проекти отпреди 2014 г. CORDIS не винаги дава точни координати. Тези точки са на ниво град или държава.
Накратко на български
Методи от статистическата физика се прилагат върху проблеми от компютърните науки, като например разделянето на мрежа на две равни части. Това помага да се разбере защо някои алгоритми изискват много време за работа и как да се подобри тяхното изпълнение.
Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.
Резултати накратко
Final Activity Report Summary - PHASETRANS (Phase transitions in computational complexity and formal verification: towards generic and realistic approaches)
This project dealt with applying methods from Statistical Physics to problems from Computer Science. This is an exciting area at the crossroads of the two disciplines that provides a great understanding of the reasons for which some of the problem take a long time when solved on a computer. Our research contributions comprised on one hand the theory of such phase transitions. We studied phenomena (such as 'clustering' of solutions, or 'first-order phase transitions') that have implications for the running time of several algorithms, and the extent to which they have. We developed notions of 'reducing' one problem to another, and offered examples of such reductions. We developed mathematical methods (based on concepts from Statistical Physics) to analyse the performance of several existing algorithms from the literature, and developed new ones. We studied the applicability of such methods to problems of practical impact such as dividing a network into two equal parts while cutting the minimum number of links (a problem that appears in parallel computing) and in problems of grouping a set of items into clusters in the most natural way (an approach from data analysis and mining known as correlation clustering).
Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз
Цел на проекта
Phase transitions in combinatorial optimization is a new, exciting research direction at the crossroads of statistical mechanics, combinatorial optimization and artificial intelligence.Its goals are to use intuitions from statistical physics to shed light on the underlying reasons for computational intractability, thus complementing computational complexity theory. Despite significant progress, phase transitions are still largely a case-by-case approach, with few connections to computational complexity theory.We propose:- to develop the phase transition approach into a systematic theory, related to Computational Complexity, using insights and methods from Computational Complexity theory; and - to increase the practicality of this approach, by investigating phase transitions for instances with a regular structure, with a special focus on those arising from problems in formal verification.A benefit of this approach (if successful) would be bringing the algorithmic advances experienced in the area of satisfiability solving by the definition of the survey propagation algorithm to the area of formal verification.
Оригинален текст от CORDIS (на английски).
Участници
- INSTITUTUL E-AUSTRIA TIMISOARA · TIMISOARAКоординаторНиво градРумъния
Връзки
Данни: CORDIS, © Европейски съюз