« Smart Mailbox limitations in OS X Tiger | Main | Tracking Bees with Radar »
May 12, 2005
What does P-Complete mean?
[NC-Reducibility and P-Completeness] It seemed odd to me to define P-completeness. But I think I get it now.
The class NC is the class of problems that are solvable "efficiently" by a polynomial number of processors. The more precise definition is on the webpage.
The class P is what you'd think it would be, the class of problems that are solvable in polynomial time (and space) on a deterministic Turing machine. The question here is , are all problems in P in NC? That is, are all problems that can be effiicently solved by a deterministic Turing machine efficiently parallelizable?
The answer to that question is not clear, but, you can take the hardest problems in P and show that if one of them is in NC, then all of P is in NC. That is, if one of these hardest problems is efficiently parallelizable, then everything in P is efficiently parallelizatable.
So you'd expect some kind of reduction for showing that problem is P-complete by reducing a known P-complete problem to it. Its in the linked page.
Posted by jones at May 12, 2005 08:31 PM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)