In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic estimate h(n) and actual cost h*(n) to never be different by more than O(log(h*(n)), i.e.:
|h(n) - h*(n)| <= O(log(h*(n)))
The textbook mentions this result without proof. I am looking for the proof. Does anyone know where I can find this result proven?
Edit: I discovered that the proof is most likely available in Judea Pearl's textbook "Heuristics: Intelligent Search Strategies for Computer Problem Solving" (http://www.amazon.com/exec/obidos/ASIN/0201055945/acmorg-20) (I should have guessed that this was by Pearl). It appears that the textbook is not available except through pay walls.
I do not want anyone to violate copyright laws and post the content, but if someone can validate that the proof is in this text, I will happily go out and buy the textbook (or get it from the university library).