0 Daumen
15 Aufrufe

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.

vor von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community