Well there's two problems there: you can easily "reduce" a P problem to an NP-complete one; it's when you do it the other way around (reduce graph coloring to a

Well there's two problems there: you can easily "reduce" a P problem to an NP-complete one; it's when you do it the other way around (reduce graph coloring to an instance of problem X) that you even have anything to worry about. But yes, worst time bounds for many problems are devilishly hard to achieve even when you're trying.