A theory of strict P-completeness |
| |
| Authors: | Anne Condon |
| |
| Affiliation: | (1) Computer Sciences Department, University of Wisconsin at Madison, 1210 West Dayton St, 53706 Madison, WI, USA |
| |
| Abstract: | A serious limitation of the theory of P-completeness is that it fails to distinguish between those P-complete problems that do have polynomial speedup on parallel machines from those that don't. We introduce the notion of strict P-completeness and develop tools to prove precise limits on the possible speedups obtainable for a number of P-complete problems. |
| |
| Keywords: | Parallel computation P-completeness |
| 本文献已被 SpringerLink 等数据库收录！ |
