পোস্ট করেসপন্ডেন্স প্রবলেম

১ · PCP কী — ডোমিনো ও ফরমাল স্টেটমেন্ট

কল্পনা করুন আপনার কাছে কিছু ডোমিনোপ্রতিটি টাইলের উপরে একটি টপ-স্ট্রিং, নিচে একটি বটম-স্ট্রিং লেখা — সাধারণ ডোমিনো খেলার টাইলের মতোই একটি রূপক টাইল আছে, প্রতিটির উপরে একটি স্ট্রিং (টপ) আর নিচে একটি স্ট্রিং (বটম) লেখা। আপনি এই টাইলগুলো (পুনরাবৃত্তি সহ, যত খুশি বার একই টাইল ব্যবহার করা যায়) পাশাপাশি সাজাবেন — প্রশ্ন হলো: এমনভাবে সাজানো কি সম্ভব যাতে সব টাইলের উপরের স্ট্রিংগুলো পাশাপাশি জোড়া লাগিয়ে যে স্ট্রিং হয়, সেটা ঠিক নিচের স্ট্রিংগুলো জোড়া লাগিয়ে যে স্ট্রিং হয়, তার সাথে অক্ষরে-অক্ষরে মিলে যায়?

ফরমালি (KaTeX-এ): একটি আলফাবেট Σ-এর উপর ডোমিনোর একটি সসীম সংগ্রহ $(t_1,b_1), (t_2,b_2), \ldots, (t_k,b_k)$ দেওয়া হলে ($t_i, b_i \in \Sigma^*$ প্রতিটি জোড়ার টপ ও বটম স্ট্রিং), PCP জিজ্ঞাসা করে — এমন কোনো $n \geq 1$ ও সূচক (index) সিকোয়েন্স $i_1, i_2, \ldots, i_n \in \{1,\ldots,k\}$ (একই সূচক বারবার ব্যবহার করা যাবে) কি বিদ্যমান, যাতে —

$$t_{i_1}t_{i_2}\cdots t_{i_n} = b_{i_1}b_{i_2}\cdots b_{i_n}$$

লক্ষ্য করুন এই সংজ্ঞায় কোনো "মেশিন," "প্রোগ্রাম," বা "গণনা" নেই — শুধু স্ট্রিং জোড়া লাগানো ও তুলনা করা। তবুও, পরের সেকশনে দেখবেন, এই নিরীহ-দেখতে সমস্যাটি সাধারণভাবে সমাধানযোগ্য নয়।

২ · PCP কেন আনডিসাইডেবল

থিওরেম: PCP আনডিসাইডেবল — অর্থাৎ কোনো অ্যালগরিদম নেই যা প্রতিটি সম্ভাব্য ডোমিনো-সংগ্রহের জন্য সঠিকভাবে "সমাধান আছে" বা "সমাধান নেই" বলতে পারে। প্রমাণের কৌশলটি (M9/L40-এর রিডাকশন-স্টাইলের সরাসরি সম্প্রসারণ) হলো — একটি নির্বিচারে বেছে নেওয়া টুরিং মেশিন $M$ ও ইনপুট $w$ থেকে একটি ডোমিনো-সংগ্রহ নির্মাণ করা, যেভাবে যে $M$ যদি $w$-তে accept করে, তাহলে এবং শুধুমাত্র তাহলেই সেই ডোমিনো-সংগ্রহের একটি সমাধান-সিকোয়েন্স থাকবে — প্রতিটি ডোমিনো $M$-এর কম্পিউটেশনের এক-একটি "স্ন্যাপশট"কে টপ থেকে বটমে এগিয়ে নিয়ে যাওয়ার প্রতিনিধিত্ব করে, এবং একটি বৈধ সমাধান-সিকোয়েন্স ঠিক $M$-এর $w$-এর উপর সম্পূর্ণ, সঠিক কম্পিউটেশন হিস্টোরি এনকোড করে। এই নির্মাণ নিজেই বেশ জটিল (সম্পূর্ণ বিস্তারিত এখানে প্রয়োজন নেই) — মূল কথা হলো, যদি PCP ডিসাইডেবল হতো, তাহলে এই রিডাকশন ব্যবহার করে হল্টিং প্রবলেমও (M9/L39) ডিসাইডেবল হয়ে যেত — একটি সরাসরি contradiction, তাই PCP আনডিসাইডেবল।

৩ · Worked example — হাতে-কলমে সমাধান খোঁজা

উপরের ফ্লো-ডায়াগ্রামে দেখানো ডোমিনো-সংগ্রহ {(a, aa), (ab, b), (ba, a)} বিবেচনা করুন — একে ডোমিনো ১, ২, ৩ হিসেবে সূচিত করি। সিকোয়েন্স "১, ২" চেষ্টা করে দেখা যাক —

• টপ: $t_1 t_2 = \texttt{a} + \texttt{ab} = \texttt{aab}$
• বটম: $b_1 b_2 = \texttt{aa} + \texttt{b} = \texttt{aab}$

দুটোই aab — হুবহু মিলে গেছে! সুতরাং সিকোয়েন্স $(1, 2)$ এই PCP ইনস্ট্যান্সের একটি বৈধ সমাধান। এটিই এই কোর্সের একটি সাধারণ থিম — একটি সমস্যা সাধারণভাবে আনডিসাইডেবল হলেও, নির্দিষ্ট ছোট ইনস্ট্যান্সে হাতে-কলমে (বা bounded সার্চে) সমাধান খুঁজে পাওয়া সম্পূর্ণ সম্ভব।

# PCP-এর জন্য একটি সত্যিকারের bounded BFS সার্চ -- একটি সাধারণ ডিসিশন প্রসিডিউর নয়!
# (PCP আনডিসাইডেবল -- এই ফাংশনটি শুধু "length বাউন্ডের মধ্যে" সমাধান খোঁজে, বাউন্ডের বাইরে
#  সমাধান থাকলেও এটি "নেই" বলে ভুল সিদ্ধান্তে আসতে পারে -- এটিই আনডিসাইডেবিলিটির সাথে সামঞ্জস্যপূর্ণ)

from collections import deque

def solve_pcp_bounded(dominoes, max_sequence_length):
    # state = (top_so_far, bottom_so_far, sequence_of_indices)
    start = ("", "", [])
    queue = deque([start])
    visited = set()
    while queue:
        top_so_far, bottom_so_far, seq = queue.popleft()
        if len(seq) > 0 and top_so_far == bottom_so_far:
            return seq   # সমাধান পাওয়া গেছে
        if len(seq) >= max_sequence_length:
            continue     # length বাউন্ড ছাড়িয়ে গেছে, এই শাখা বাদ
        for idx, (t, b) in enumerate(dominoes):
            new_top = top_so_far + t
            new_bottom = bottom_so_far + b
            # prefix pruning: একটি অবশ্যই অন্যটির প্রিফিক্স হতে হবে, নাহলে এই শাখা কখনোই মিলবে না
            if new_top.startswith(new_bottom) or new_bottom.startswith(new_top):
                seq2 = seq + [idx]
                key = (new_top, new_bottom, len(seq2))
                if key not in visited:
                    visited.add(key)
                    queue.append((new_top, new_bottom, seq2))
    return None   # বাউন্ডের মধ্যে কোনো সমাধান পাওয়া যায়নি

# ---- সমাধানযোগ্য ইনস্ট্যান্স ----
dominoes = [("a", "aa"), ("ab", "b"), ("ba", "a")]
solution = solve_pcp_bounded(dominoes, max_sequence_length=6)
print("ডোমিনো সংগ্রহ:", dominoes)
print("পাওয়া সিকোয়েন্স (0-indexed):", solution)

if solution is not None:
    top_concat = "".join(dominoes[i][0] for i in solution)
    bottom_concat = "".join(dominoes[i][1] for i in solution)
    print(f"টপ concatenation    = {top_concat!r}")
    print(f"বটম concatenation   = {bottom_concat!r}")
    print("সমাধান বৈধ (টপ == বটম)?", top_concat == bottom_concat)

# ---- ডেলিবারেটলি আনসলভেবল ইনস্ট্যান্স ----
# প্রতিটি ডোমিনোর টপ ও বটমের প্রথম অক্ষর ভিন্ন -- তাই কোনো ডোমিনোই সিকোয়েন্স শুরু করতে পারে না
unsolvable_dominoes = [("ab", "ba"), ("ca", "ac")]
unsolvable_result = solve_pcp_bounded(unsolvable_dominoes, max_sequence_length=6)
print()
print("আনসলভেবল ডোমিনো সংগ্রহ:", unsolvable_dominoes)
print("bounded সার্চের ফলাফল:", unsolvable_result, "(কোনো সমাধান নেই, প্রত্যাশিতভাবেই)")