Could you give me examples of polynomial-time algorithms that must compute a global property over their entire input? A purely illustrative example of this might be a graph algorithm that somehow must count the total number of nodes before computing its final answer.
A silly example: Checking if a graph has more than m nodes. :-)
Some more interesting examples: