Re: Reductions in P

as far as i know the most important thing if you prove and use
P-completeness is to show that a ploblem may be intrinsically
sequential
For instance as we know sorting problem is O(nlogn) and also the
computation of a convex hull of n point is O(nlogn).We can find a
reduction from the one problem to another,and as we know the
computation of convex hull is sequential,as is sorting (by comparison)
which has as aforementioned complexity O(nlogn).
Cheers
Yannis

.