0
$\begingroup$

I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a collection, if someone permutes using the algorithm:

try every single permutation of the collection:
    if it is a match return True
If nothing was found after trying all permutation return False

This should decide if there is a match in $O(n!)$ as I understand the problem, is there something I am missing?

$\endgroup$

2 Answers 2

1
$\begingroup$

Yes. You are missing the fact that the indices that you need to select do not need to be a permutation. In fact you can use the same index multiple times (or never).

$\endgroup$
1
$\begingroup$

It turns out you can use the same domino multiple times, thanks myself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.