Timeline for The limits of parallelism
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2010 at 20:15 | comment | added | Ross Snider | While each state of the evolving system might be computed in parallel, physical systems can only be computed in parallel and the amount of time it takes for the electron calculations in the antiferromagnet to settle take time exponential in the base (as would be expected). Of course this doesn't count as a proof until we are certain that physics computations DO require serial computations. Right now we only have good reason to believe. | |
| Mar 31, 2010 at 20:15 | comment | added | Ross Snider | Oh okay. I misunderstood. I have an anecdotal example then... physical calculations can be done in parallel but only to a certain extent. Each "state" of a physical system depends on the full configuration of the previous state. There is a way to encode the partition problem (NP-Complete) into a physics calculation of electron spins in an infinite-range antiferromagnet [due to Stephan Mertens]. | |
| Mar 30, 2010 at 19:00 | comment | added | AVS | We don't know that every problem in TIME(n!) can necessarily be solved by checking n! cases in parallel. The key question here is whether there exist problems that are "inherently sequential" (i.e. can't be sped up with parallelism). This question is essentially orthogonal to the question of what can be computed efficiently. | |
| Mar 30, 2010 at 18:41 | history | answered | Ross Snider | CC BY-SA 2.5 |