Sei $$X=(x_1,...,x_n) , Y=(y_1,...,y_n) \text{ mit } |x_i|=|y_i|=|x_{i+1}|=|y_{i+1}|=... \text{ für alle } i+1 \leq n$$
Ist PKP nun entscheidbar ?
Ansatz:
$$\text{ PKP ist mit dieser Modifizierung entscheidbar, weil man jetzt nur } x_i \text{ finden muss,}\\ \text{ das äquivalent zu }x_{i+1} \text{ ist und } y_i =y_{i+1}$$.
Also:
$$\text{Suche für jedes }i \leq n. \text{ Für } x_i \text{ ein äquivalentes } x_{i+1} \text{ und für } y_i \text{ ein äquivalentes } y_{i+1}.$$
Sobald 2 solches Sets existieren, akzeptiere, wenn nicht rejecte.
Hält nach endlich vielen Schritten also maximal nach n Schritten und hält somit immer.
Daraus folgt, dass diese Modifizierung entscheidbar ist.
