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?

  • $\begingroup$ Can you elaborate on what you mean by using "breadth-first search" for this problem? Also, what do you mean by "generally best"? I am skeptical that there will be any single best answer; probably some techniques will better on some instances, and others will work better on other instances, so then it's not clear what kind of answer you're looking for. Finally, why do you think that BFS is better for simple instances and DFS is better for hard instances? And what do you mean by simple/hard? $\endgroup$ – D.W. Nov 22 '16 at 6:19
  • $\begingroup$ @D.W. I've had more time to think about it and I do think it's probably dependent on the instance. A simple PCP instance is one that has a short solution, and a hard one is one that has a long solution. A short solution will be closer to the root of the search tree and as such I think BFS is best for simple instances, whereas a long solution will be further down the search tree, in which case a DFS would probably be faster. But again, that's just my own conjecture based on what I've learned while coding the problem. $\endgroup$ – Fiery Phoenix Nov 22 '16 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.