Postkorrespondensproblem

Postkorrespondensproblemet är ett oavgörligt beslutsproblem som introducerades av Emil Post 1946. Eftersom det är enklare än stoppproblemet och Entscheidungsproblemet används det ofta i bevis på oavgörbarhet .

Definition av problemet

Låt $A$ vara ett alfabet med minst två symboler. Inmatningen av problemet består av två finita listor $\alpha _{1},\ldots ,\alpha _{N}$ och $\beta _{1},\ldots ,\beta _{N}$ ord över $A$ . En lösning på detta problem är en sekvens av index $(i_{k})_{1\leq k\leq K}$ med $\displaystyle K\geq 1 }$ och $1\leq i_{k}\leq N$ för alla $k$ , så att

\alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.

Beslutsproblemet är då att avgöra om en sådan lösning finns eller inte.

Alternativ definition

g:(i_{1},\ldots ,i_{K})\mapsto \alpha _{i_{1}}\ ldots \alpha _{i_{K}}

h:(i_{1},\ldots ,i_{K})\mapsto \beta _{i_{1}}\ldots \beta _{i_{K}}.

Detta ger upphov till en likvärdig alternativ definition som ofta finns i litteraturen, enligt vilken två godtyckliga homomorfismer $g,h$ med en gemensam domän och en gemensam codomän utgör en instans av Post-korrespondensproblemet, som nu frågar om det finns ett icke-tomt ord $w$ i domänen så att

g(w)=h(w)

.

En annan definition beskriver detta problem lätt som en typ av pussel. Vi börjar med en samling dominoskivor som var och en innehåller två strängar, en på varje sida. En individuell domino ser ut

{\begin{bmatrix}a\\ab\end{bmatrix}}

och en samling dominos ser ut

{{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{ bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}

.

Uppgiften är att göra en lista över dessa dominon (upprepning tillåten) så att strängen vi får genom att läsa av symbolerna på toppen är samma som strängen av symboler på botten. Denna lista kallas en matchning. Postkorrespondensproblemet är att avgöra om en samling domino har en match. Till exempel är följande lista en matchning för detta pussel.

{{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{ bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}

.

För vissa samlingar av dominoskivor är det kanske inte möjligt att hitta en matchning. Till exempel samlingen

{{\begin{bmatrix}abc\\ab\end{bmatrix}},{\begin{bmatrix}ca\ \a\end{bmatrix}},{\begin{bmatrix}acc\\ba\end{bmatrix}}}

.

kan inte innehålla en matchning eftersom varje översta sträng är längre än motsvarande bottensträng.

Exempel på problem

Exempel 1

Tänk på följande två listor:

α ₁	α ₂	α ₃
a	ab	bba

β ₁	β ₂	β ₃
bä	aa	bb

En lösning på detta problem skulle vara sekvensen (3, 2, 3, 1), eftersom

\alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba\cdot ab\cdot bba\cdot a=bbaabbbaa=bb\cdot aa\cdot bb\cdot baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.

Dessutom, eftersom (3, 2, 3, 1) är en lösning, så är alla dess "upprepningar", såsom (3, 2, 3, 1, 3, 2, 3, 1), etc.; det vill säga när en lösning finns finns det oändligt många lösningar av detta repetitiva slag.

Men om de två listorna endast hade bestått av $\alpha _{2},\alpha _{3}$ och $\beta _{2},\beta _{3}$ från dessa mängder, då skulle det inte ha funnits någon lösning (den sista bokstaven i en sådan α-sträng är inte densamma som bokstaven före den, medan β bara konstruerar par av samma bokstav).

Ett bekvämt sätt att visa en instans av ett postkorrespondensproblem är som en samling block av formuläret

α _i
β _i

det finns ett obegränsat utbud av varje typ av block. Således betraktas ovanstående exempel som

en
baa

i = 1

ab
aa

i = 2

bba
bb

i = 3

där lösaren har ett oändligt utbud av var och en av dessa tre blocktyper. En lösning motsvarar något sätt att lägga block bredvid varandra så att strängen i de översta cellerna motsvarar strängen i de nedre cellerna. Då motsvarar lösningen på exemplet ovan:

bba
bb

i ₁ = 3

ab
aa

i ₂ = 2

bba
bb

i ₃ = 3

en
baa

i ₄ = 1

Exempel 2

Återigen genom att använda block för att representera en instans av problemet, följande är ett exempel som har oändligt många lösningar utöver den typ som erhålls genom att bara "upprepa" en lösning.

bb
b

1

ab
ba

2

c
bc

3

I det här fallet är varje sekvens av formen (1, 2, 2, . . ., 2, 3) en lösning (utöver alla deras upprepningar):

bb
b

1

ab
ba

2

ab
ba

2

ab
ba

2

c
bc

3

Bevisskiss på oavgörbarhet

Det vanligaste beviset för PCP:s obestämbarhet beskriver en instans av PCP som kan simulera beräkningen av en godtycklig Turing-maskin på en viss ingång. En matchning kommer att inträffa om och endast om inmatningen skulle accepteras av Turing-maskinen. Eftersom att bestämma om en Turing-maskin kommer att acceptera en ingång är ett grundläggande oavgörligt problem, kan PCP inte heller avgöras. Följande diskussion är baserad på Michael Sipsers lärobok Introduction to the Theory of Computation .

Mer detaljerat är tanken att strängen längs toppen och botten ska vara en beräkningshistorik för Turing-maskinens beräkning. Det betyder att den kommer att lista en sträng som beskriver initialtillståndet, följt av en sträng som beskriver nästa tillstånd, och så vidare tills den slutar med en sträng som beskriver ett accepterande tillstånd. Tillståndssträngarna är åtskilda av någon separatorsymbol (vanligtvis skrivet #). Enligt definitionen av en Turing-maskin består maskinens fullständiga tillstånd av tre delar:

Bandets aktuella innehåll.
Det aktuella tillståndet för den finita tillståndsmaskinen som styr bandhuvudet.
Den aktuella positionen för tejphuvudet på bandet.

Även om bandet har oändligt många celler, kommer bara ett ändligt prefix av dessa att vara icke-tomt. Vi skriver ner dessa som en del av vår stat. För att beskriva tillståndet för den finita kontrollen skapar vi nya symboler, märkta q ₁ till q _k , för vart och ett av den finita tillståndsmaskinens k -tillstånd. Vi infogar den korrekta symbolen i strängen som beskriver bandets innehåll vid bandhuvudets position, och anger därigenom både bandhuvudets position och det aktuella tillståndet för den finita kontrollen. För alfabetet {0,1} kan ett typiskt tillstånd se ut ungefär så här:

101101110 q ₇ 00110.

En enkel beräkningshistorik skulle då se ut ungefär så här:

₀ q 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10.

₀ Vi börjar med detta block, där x är inmatningssträngen och q är starttillståndet:


₀ q x #

Toppen börjar med att "släpa" botten med ett tillstånd, och behåller denna fördröjning till slutet. Därefter, för varje symbol a i bandalfabetet, såväl som #, har vi ett "kopia"-block, som kopierar det oförändrat från ett tillstånd till nästa:

a
a

Vi har också ett block för varje positionsövergång maskinen kan göra, som visar hur tejphuvudet rör sig, hur det finita tillståndet förändras och vad som händer med de omgivande symbolerna. Till exempel, här är bandhuvudet över en 0 i tillstånd 4, och skriver sedan en 1 och flyttar sig åt höger och ändrar till tillstånd 7:

q ₄0
1 q ₇

Slutligen, när toppen når ett accepterande tillstånd, behöver botten en chans att äntligen komma ikapp för att slutföra matchen. För att tillåta detta utökar vi beräkningen så att när ett accepterande tillstånd har uppnåtts kommer varje efterföljande maskinsteg att göra att en symbol nära bandhuvudet försvinner, en i taget, tills ingen återstår. Om q _f är ett accepterande tillstånd, kan vi representera detta med följande övergångsblock, där a är en bandalfabetsymbol:

q _f a
q _f

aq _f
q _f

Det finns ett antal detaljer att räkna ut, som att hantera gränser mellan stater, se till att vår initiala bricka går först i matchen, och så vidare, men detta visar den allmänna idén om hur ett statiskt brickapussel kan simulera en Turing maskinberäkning.

Det föregående exemplet

₀ q 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10.

representeras som följande lösning på postkorrespondensproblemet:


₀ q 101#

₀ q 1
1 q ₄

0
0

1
1

#
#

1
1

q ₄ 0
1 q ₂

1
1

#
#

1
1

1 q ₂ 1
q ₈ 10

#
#

1 q ₈
q ₈

1
1

0
0

#
#

q ₈ 1
q ₈

0
0

#
#

q ₈ 0
q ₈

#
#

q ₈

#
#

...

Varianter

Många varianter av PCP har övervägts. En anledning är att när man försöker bevisa oavgörbarhet för något nytt problem genom att reducera från PCP, händer det ofta att den första reduktionen man hittar inte är från PCP i sig utan från en till synes svagare version.

Problemet kan formuleras i termer av monoida morfismer f , g från den fria monoiden B ^∗ till den fria monoiden A ^∗ där B har storlek n . Problemet är att avgöra om det finns ett ord w i B ⁺ så att f ( w ) = g ( w ).
Villkoret att alfabetet $A$ har minst två symboler krävs eftersom problemet kan avgöras om $A$ bara har en symbol.
En enkel variant är att fixa n , antalet brickor. Detta problem kan avgöras om n ≤ 2, men förblir obestämbart för n ≥ 5. Det är okänt om problemet är avgörbart för 3 ≤ n ≤ 4.
Det cirkulära postkorrespondensproblemet frågar om index $i_{1},i_{2},\ldots$ kan hittas så att $\alpha _{ i_{1}}\cdots \alpha _{i_{k}}$ och $\beta _{i_{1}}\cdots \beta _{i_{k}}$ är konjugera ord , dvs de är lika modulo rotation. Denna variant är obestämbar.
En av de viktigaste varianterna av PCP är det begränsade postkorrespondensproblemet , som frågar om vi kan hitta en matchning med högst k brickor, inklusive upprepade brickor. En brute force-sökning löser problemet i tid O(2 ^k ), men detta kan vara svårt att förbättra, eftersom problemet är NP-komplett . Till skillnad från vissa NP-fullständiga problem som det booleska tillfredsställbarhetsproblemet visades en liten variation av det gränsade problemet också vara komplett för RNP, vilket innebär att det förblir svårt även om indata väljs slumpmässigt (det är svårt i genomsnitt över enhetligt distribuerade ingångar).
En annan variant av PCP kallas det markerade Post Correspondence Problem , där varje $\alpha _{i}$ måste börja med en annan symbol, och varje $\beta _{i}$ måste också börja med en annan symbol. Halava, Hirvensalo och de Wolf visade att denna variation kan avgöras i exponentiell tid . Dessutom visade de att om detta krav lättas upp något så att bara ett av de två första tecknen behöver skilja sig åt (det så kallade 2-markerade postkorrespondensproblemet) blir problemet oavgörbart igen.
Post Embedding Problemet är en annan variant där man letar efter index $i_{1},i_{2},\ldots$ så att $\alpha _ {i_{1}}\cdots \alpha _{i_{k}}$ är ett (spritt) underord till $\beta _{i_{1}}\cdots \beta _{ i_{k}}$ . Denna variant är lätt att avgöra eftersom, när vissa lösningar finns, i synnerhet en längd-ett-lösning existerar. Mer intressant är Regular Post Embedding Problem , en ytterligare variant där man letar efter lösningar som hör till ett givet reguljärt språk (inlämnat t.ex. i form av ett reguljärt uttryck på uppsättningen { $\displaystyle \ {1,\ldots ,N\}}$ ). Problemet med Regular Post Embedding är fortfarande avgörbart men på grund av den extra regelbundna begränsningen har det en mycket hög komplexitet som dominerar varje multiplicera rekursiv funktion.
Identity Correspondence Problem (ICP) frågar om en ändlig uppsättning av par av ord (över ett gruppalfabet) kan generera ett identitetspar genom en sekvens av sammanlänkningar. Problemet är obestämbart och likvärdigt med följande gruppproblem: är halvgruppen som genereras av en ändlig uppsättning ordpar (över ett gruppalfabet) en grupp.

externa länkar

Eitan M. Gurari. En introduktion till teorin om beräkning , kapitel 4, Postens korrespondensproblem . Ett bevis på obeslutbarheten av PCP baserat på Chomsky typ-0 grammatik .
Dong, Jing. "Analysen och lösningen av en PCP-instans." 2012 Nationell konferens om informationsteknologi och datavetenskap. Uppsatsen beskriver en heuristisk regel för att lösa vissa specifika PCP-instanser.
Online PHP-baserad PCP-lösare
PCP HEMMA
PCP - ett trevligt problem
PCP-lösare i Java
Postkorrespondensproblem