Timeline for The limits of parallelism
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2010 at 19:58 | answer | added | Ryan Williams | timeline score: 4 | |
| Mar 30, 2010 at 18:41 | answer | added | Ross Snider | timeline score: 0 | |
| Mar 30, 2010 at 15:18 | answer | added | AVS | timeline score: 4 | |
| Mar 30, 2010 at 14:23 | comment | added | AVS | @rgrig: I don't think this is what psihodelia is asking. Any problem solvable by a polynomial number of processors in deterministic polynomial time already lies in P, which is properly contained in EXPTIME $\subset$ TIME(n!). I think the question is whether you can solve any problem in TIME(n!) using an arbitrary number of processors (say n! of them), in deterministic polynomial time. | |
| Mar 30, 2010 at 13:41 | comment | added | rgrig | In other words, I think a better question would be along the lines: "Which problems can be solved in deterministic worst-case poly time given a poly number of processors on a PRAM machine?" | |
| Mar 30, 2010 at 13:37 | comment | added | rgrig | I didn't link to NP. Roughly, problems in NC are those that can be done really fast with many processors. It's not really an answer to what you ask, because the polylog time is low enough to make NC not bigger than P. You probably want something like PT/WK(poly,poly), but I don't know much about such a complexity class. | |
| Mar 30, 2010 at 13:07 | comment | added | psihodelia | @rgrig: thanks, I know already well enough about NP theory :) | |
| Mar 30, 2010 at 12:54 | comment | added | rgrig | You may want to see en.wikipedia.org/wiki/NC_(complexity) | |
| Mar 30, 2010 at 12:50 | history | asked | psihodelia | CC BY-SA 2.5 |