MPCP

Das Modifizierte PCP ist eine Einschränkung des PCP, bei der die Indexfolge zwingend mit dem Index 1 beginnen muss ( $i_{1} = 1$ ).

M P C P := {K \in P C P ∣ \exists i_{2}, \dots, i_{n} : x_{1} \cdot x_{i_{2}} \dots x_{i_{n}} = y_{1} \cdot y_{i_{2}} \dots y_{i_{n}}}