पोस्ट पत्राचार समस्या

एमिल पोस्ट द्वारा 1946 में शुरू किया गया पोस्ट कॉरेस्पॉन्डेंस प्रॉब्लम (पीसीपी) एक अचूक निर्णय समस्या है। एक वर्णमाला पर पीसीपी समस्या P निम्नानुसार बताई गई है -

निम्नलिखित दो सूचियों को देखते हुए, M तथा N of पर गैर-खाली तार

M = (x ₁ , x ₂ , x ₃ , ………, x _n )

एन = (y ₁ , y ₂ , y ₃ , ………, y _n )

हम कह सकते हैं कि एक पोस्ट पत्राचार समाधान है, अगर कुछ i ₁ , i ₂ , ………… i _{k के लिए} , जहां 1 where i _j , n, स्थिति x _i1 …… .x _ik = y _i1 …… है। y _ik संतुष्ट करता है।

उदाहरण 1

खोजें कि क्या सूची

म = (अब्ब, आ, आ) और एन = (बबा, आ, आ)

एक पत्राचार समाधान है?

उपाय

	x 1	x 2	x 3
म	जुलाहे का ताना	आ	एएए
एन	बीबीए	एएए	आ

यहाँ,

x₂x₁x₃ = ‘aaabbaaa’

तथा y₂y₁y₃ = ‘aaabbaaa’

हम देख सकते हैं कि

x₂x₁x₃ = y₂y₁y₃

इसलिए, समाधान है i = 2, j = 1, and k = 3.

उदाहरण 2

खोजें कि क्या सूची M = (ab, bab, bbaaa) तथा N = (a, ba, bab) एक पत्राचार समाधान है?

उपाय

	x 1	x 2	x 3
म	अब	बाब	bbaaa
एन	ए	बी 0 ए	बाब

इस मामले में, कोई समाधान नहीं है क्योंकि -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (लंबाई समान नहीं हैं)

इसलिए, यह कहा जा सकता है कि यह पोस्ट पत्राचार समस्या है undecidable।