This question has recently occurred to me as I was working on an implementation of the (Bounded) Post's Correspondence Problem. Basically, which method is generally best for PCP? Breadth-first or depth-first search? Or is this question, well, undecidable?
I understand the basic difference between the two approaches, but I am not on their benefits with regards to PCP. I imagine BFS is good for simple instances, and DFS is good for hard instances. But again, how do we KNOW if a given instance is hard in the first place?