Yazan : Şadi Evren ŞEKER
Emil Post tarafından 1946 yılında ortaya atılan ve belirsiz karar problemi olarak sınıflandırılabilecek olan (undecidable decision problem) problemin ismidir. Literatürde kısaca PCP olarak da geçmektedir. Bu problem, yine Emil Post tarafından geliştirilen, Post Makinesi (post machine) olarak bilinen ve Turing makinesinin (Turing Machine) bir benzeri olan makinenin geliştirilmesini sağlamıştır. Problem, durma problemine göre (halting problem) daha basit bir yapıdadır bu yüzden belirsiz karar problemlerinin ispatlanmasında daha çok tercih edilir.
Problem aşağıdaki şekilde tanımlanabilir.
A bir alfabe olmak üzere, bu alfabeden tanımlı olan n elemanlı iki küme ele alalım:
X = {x1,x2, … xn }
Y = {y1,y2, … yn}
Bu iki küme üzerinden üretilen iki kelimenin eşit olması durumunu arıyoruz.
Örneğin aşağıdaki kümeleri ele alalım:
X = { sad , sek , er, i}
Y = { sa , se, ker , di }
Yukarıdaki örnek kümeler için böyle bir eşitlik bulunabilir:
sad + i + sek + er = sadiseker = sa + di + se + ker
Yukarıdaki eşitliğin sol tarafı X kümesinde, sağ tarafı ise Y kümesinden üretilmiştir.
Bazı problemler çözümsüz, bazı problemler ise birden fazla çözüme sahip olabilir. Örneğin aşağıdaki kümeleri ele alalım:
X= {a,ab,bba}
Y= { baa, aa, bb}
Çözüm aşağıdaki şekilde olabilir:
bba + ab + bba + a = bbaabbbaa = bb + aa + bb + baa
Ancak bu tek çözüm değildir. Örneğin aşağıdaki de bir çözüm üretebilir:
bba + ab + bba + a + bba + ab + bba + a = bbaabbbaabbaabbbaa = bb + aa + bb + baa + bb + aa + bb + baa
Yukarıdaki ikinci çözüm, bir önceki çözümün tekrarı niteliğindedir. Yani üretilen eşitlik dizilimi bir önceki çözümün iki kere tekrarlanması ile oluşturulmuştur. Bu işlem istenildiği kadar tekrar edilebilir.
Örneğin yukarıdaki kümelerin ilk elemanları çıkarılarak aşağıdaki kümeler oluşturulsaydı
X= {ab,bba}
Y= { aa, bb}
Bu kümelerden elde edilen bir çözüm bulunamazdı.