We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [post-correspondence]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
488 views

Prove Post Correspondence Problem Non-Recursive Without Reduction

Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...
5
votes
0answers
1k views

Bounded Post Correspondence Problem NP-Complete Proof

I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so. It is clear to me that the problem is decidable but I cannot find any reduction ...
2
votes
0answers
391 views

Post Correspondence Problem “binary” variant

Bounded Post Correspondence Problem is defined as follows: given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...