Skip to main content

Questions tagged [post-correspondence]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers

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 ...
assafisr's user avatar
5 votes
0 answers

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 ...
Raphael's user avatar
  • 4,565
2 votes
0 answers

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_{...
anacrusis's user avatar