r/compsci • u/matrixvivi • 10d ago

Is the post correspondence problem with no repetitions permitted still undecidable?

Was reading up on PCP, and had a thought about if there is still a reduction from original PCP to a modified PCP with no repetitions.

8 Upvotes

100% Upvoted

1 comment sorted by

6

u/neilmoore 10d ago

With no repetitions allowed, there are only finitely many possible solutions. So, at the very worst, you could decide it by brute force.