You are currently browsing the tag archive for the ‘Computational Complexity’ tag.

Figure – Attractor basins (fig.2 pp.6 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Mária Ercsey-Ravasz and Zoltán Toroczkai have proposed a way of mapping satisfiability problems to differential equations and a deterministic algorithm that solves them in polynomial continuous time at the expense of exponential energy functions (so the discrete approximation of the algorithm does not run in polynomial time, and an analogue system would need exponential resources).

The map assigns a phase space to a problem; the algorithm chooses random initial conditions from within that phase space.  In the graphs above and below, they pick a 2-d subspace of the phase space and for each initial point in that space they illustrate 1) the particular solution the algorithm finds, 2) the corresponding “solution cluster”, an equivalence class of solutions that identifies two solutions if they differ in exactly one variable assignment, and 3) the time it takes to solve the problem.  Each row adds another clause to satisfy.

The especially interesting part of the paper is the notion of an escape rate,  the proportion of the trajectories still searching for a solution after a time t.  In a companion paper, they show that the escape rate for Sudoku combinatorial instances (The Chaos Within Sudoku, Nature, August 2012)  correlates strongly with human judgements of hardness. This escape rate is similar to the Kolmogorov complexity in that it gives a notion of hardness to individual problem instances rather than to classes of problems. Full paper could be retrieved from arXiv: Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011. (at arXiv on August 2012).

Figure – Attractor basins for 3-XORSAT (fig.8 pp.18 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)

Figure (click to enlarge) – Orders of common functions (via Wikipedia): A list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a constant and n increases without bound. The slower-growing functions are generally listed first. For each case, several examples are given.

Figure – A comic strip by Randall Munroe (at – a webcomic of romance, sarcasm, math, and language) about Computational Complexity, the Travelling Salesman (TSP) problem, and – last, but not least – about crowd-sourcing the whole thing into ebay! … LOL

… hey wait, just before you ROTFL yourself on the floor, just check this out. For some problem cases it might just work. Here is one of those  recent cases: Interactive, online games are being used to crack complex scientific conundrums, says a report in Nature. And the wisdom of the ‘multiplayer’ crowd is delivering a new set of search strategies for the prediction of protein structures. The problem at hands is nothing less than protein folding, not an easy one. You can check Nature‘s journal video here. While the online game in question is known as Foldit (link – image below).

Figure – Solving puzzle #48 with FOLDIT, the online game.

There are a lot of consequences with this approach. Here from an article of the Spanish El Pais newspaper (in, Malen Ruiz de Elvira, “Los humanos ganan a los ordenadores – Un juego en red para resolver un problema biológico obtiene mejores resultados que un programa informático“, El Pais, Madrid – August 8, 2010):

[…] Miles de jugadores en red, la mayoría no especializados, han demostrado resolver mejor la forma que adoptan las proteínas que los programas informáticos más avanzados, han hallado científicos de la Universidad de Washington (en Seattle). Averiguar cómo se pliegan las largas cadenas de aminoácidos de las proteínas en la naturaleza -su estructura en tres dimensiones- es uno de los grandes problemas de la biología actual, al que numerosos equipos dedican enormes recursos informáticos. […] Sin embargo la predicción por ordenador de la estructura de una proteína representa un desafío muy grande porque hay que analizar un gran número de posibilidades hasta alcanzar la solución, que se corresponde con un estado óptimo de energía. Es un proceso de optimización. […] Para comprobar su pericia, los científicos plantearon a los jugadores 10 problemas concretos de estructuras de proteínas que conocían pero que no se habían hecho públicas. Encontraron que en algunos de estos casos, concretamente cinco, el resultado alcanzado por los mejores jugadores fue más exacto que el de Rosetta. En otros tres casos las cosas quedaron en tablas y en dos casos ganó la máquina. […] Además, las colaboraciones establecidas entre algunos de los jugadores dieron lugar a todo un nuevo surtido de estrategias y algoritmos, algunos de los cuales se han incorporado ya al programa informático original. “Tan interesantes como las predicciones de Foldit son la complejidad, la variedad y la creatividad que muestra el proceso humano de búsqueda”, escriben los autores del trabajo, entre los que figuran, algo insólito en un artículo científico, “los jugadores de Foldit”. […] “Estamos en el inicio de una nueva era, en la que se mezcla la computación de los humanos y las máquinas”, dice Michael Kearns, un experto en el llamado pensamiento distribuido. […]

Video – Matthew Todd lecture at Google Tech Talk April, 2010 – Open Science: how can we crowdsource chemistry to solve important problems?

The idea of course, is not new. All these distributed human learning systems, started with the SETI at home project (link), originally launched in 1999, by the Berkeley University in California. But I would like to drawn your attention, instead, to some other works on it. First is a video by Matthew Todd (School of Chemistry, University of Sydney). His question his apparently simple: how can we crowdsource chemistry to solve important problems? (above). Second, a well known introductory paper on Crowd-Sourcing by Daren C. Brabham (2008), with several worldwide examples:

[…] Abstract: Crowdsourcing is an online, distributed problem-solving and production model that has emerged in recent years. Notable examples of the model include Threadless, iStockphoto, Inno-Centive, the Goldcorp Challenge, and user-generated advertising contests. This article provides an introduction to crowdsourcing, both its theoretical grounding and exemplar cases, taking care to distinguish crowdsourcing from open source production. This article also explores the possibilities for the model, its potential to exploit a crowd of innovators, and its potential for use beyond for-profit sectors. Finally, this article proposes an agenda for research into crowdsourcing. […] in Daren C. Brabham, “Crowdsourcing as a Model for Problem Solving – An Introduction and Cases“, Convergence: The International Journal of Research into New Media Technologies, London, Los Angeles, New Delhi and Singapore Vol 14(1): 75-90, 2008.

[...] People should learn how to play Lego with their minds. Concepts are building bricks [...] V. Ramos, 2002.

@ViRAms on Twitter

Error: Twitter did not respond. Please wait a few minutes and refresh this page.


Blog Stats

  • 244,343 hits