Il problema del post corrispondenza con più di due righe più duramente della variante standard a due righe?

Question

Il problema della corrispondenza post standard riguarda le tessere con due file di simboli e se è possibile effettuare una disposizione delle piastrelle in modo che la sequenza dei simboli superiori delle piastrelle sia uguale a quella inferiore.

Let $ \ text {n-pcp}, \ text {n}> 0 $ una generalizzazione del problema del post corrispondenza in cui le piastrelle contengono $ \ testo {n} $ righe e le sequenze dei simboli devono essere uguali per tutte queste righe.

Ovviamente $ \ Text {1-PCP} $ è decidabile (infatti è banale perché la risposta al problema è sempre vera). $ \ Text {2-PCP} $ è il PCP standard.

Ma cosa succede se $ \ text {n}> 2 $ ?È più difficile o può essere ridotto al PCP standard (come> 3-SAT ridotto a 3-SAT)?

Answer 1

$ \ text {n-pcp} $ può essere ridotto a $ \ text {2-PCP} $ come segue.

Let $ M $ BE UN MACCHINA DI TORMANTE NONTERMINISTICA CHE ACCETTA UN $ \ Text {N-PCP} $ istanza come input, indovina una soluzione per quell'istanza, e quindi controlla che è corretto.Chiaramente, $ m $ accetta se e solo se c'è una soluzione all'istanza di input.

Ora, let $ p $ essere un'istanza di $ \ text {n-pcp} $ .La riduzione codifica $ M (P) $ come una classe $ \ text {2-PCP} $ istanza inla moda standard.