সরাসরি পর্বে যান
পর্ব ৬৫ · ৮৫-এর মধ্যে · মডিউল ১১

PSPACE-completeness — TQBF আর game

PSPACE-Completeness — Quantified Boolean Formulas, TQBF in Polynomial Space, the Hardness Proof, the Formula Game and Generalized Geography

Taught in Bangla, this lesson defines quantified Boolean formulas and TQBF, proves TQBF is in PSPACE with one recursion frame per quantifier, and proves PSPACE-hardness using the ∀ trick that keeps the reachability formula polynomial. It turns formulas into the formula game and reduces it to generalized geography. In-page Python (Pyodide) measures calls and recursion depth of an evaluator, a JavaScript game plays geography, and a real run with the z3 solver checks closed QBFs against the evaluator.

এই পর্বে যা শিখবেন

  • Quantified Boolean formula, prenex রূপ আর TQBF-এর নিখুঁত সংজ্ঞা, আর quantifier-এর ক্রম কেন অর্থ বদলায়
  • TQBF ∈ PSPACE-এর প্রমাণ, আর একটি recursive evaluator-এ calls আর recursion depth মেপে দেখা
  • TQBF PSPACE-hard: configuration-এর reachability-কে QBF-এ লেখা, আর ∀-কৌশল কেন সূত্রকে ছোট রাখে
  • Formula game, winning strategy, আর FORMULA-GAME থেকে generalized geography-তে reduction
  • দাবা, Go, পাজল আর planning-এর জটিলতা নিয়ে কী প্রমাণিত আর কী খোলা

১ · Quantifier-এর খেলা — TQBF-এর সংজ্ঞা

NP-এর প্রশ্নে একটিমাত্র “আছে কি” লুকানো থাকে: সূত্রটি সত্য করার মতো কোনো মান আছে কি? পর্ব ৬০-এ দেখেছি, SAT এই ধরনের সব প্রশ্নের প্রতিনিধি। কিন্তু অনেক বাস্তব প্রশ্নে দুই পক্ষ থাকে। দাবার ধাঁধায় “সাদা চাল দিয়ে দুই চালে মাত” মানে: সাদার এমন একটি চাল আছে, যার পরে কালো যা-ই খেলুক, সাদার আবার এমন একটি চাল আছে যাতে মাত হয়। “আছে”, “সব”, “আছে” পালাক্রমে আসে। এই পর্বের বিষয় ঠিক এই পালাক্রমের জটিলতা।

বাজারঘরের অফিস-পিকনিকে একটি খেলা হয়, নাম “জেলা দখল”। বোর্ডে কয়েকটি জেলা আর তাদের মধ্যে একমুখী ডেলিভারি-রাস্তা আঁকা। দুজন খেলোয়াড় পালা করে শেষ দখল করা জেলা থেকে রাস্তা ধরে এমন একটি জেলা দখল করেন, যা আগে কেউ নেয়নি। যিনি আর চাল দিতে পারেন না, তিনি হারেন। প্রথম খেলোয়াড় জিততে পারবেন কি না, প্রশ্নটি দাঁড়ায়: “আমার এমন চাল আছে, যার পরে প্রতিপক্ষের প্রতিটি চালের জবাবে আমার এমন চাল আছে, …”। অংশ ৫-এ দেখব, এই খেলাটিই PSPACE-এর একটি কঠিনতম সমস্যা।

নিখুঁত ভাষায় আসা যাক। Boolean সূত্রে দুই ধরনের quantifier বসানো যায়: ∃x (“x-এর এমন একটি মান, 0 বা 1, আছে যে …”) আর ∀x (“x-এর দুটি মানেই …”)। Discrete Mathematics কোর্সের পর্ব ০৫-এ nested quantifier-এর ক্রম বদলালে অর্থ কীভাবে বদলায়, তা দেখানো হয়েছে; এখানে চলকগুলো শুধু Boolean, তাই প্রতিটি quantifier মাত্র দুটি মানের ওপর।

সংজ্ঞা ১.১ (QBF আর TQBF)

একটি quantified Boolean formula (QBF) হলো Boolean চলক, ∧, ∨, ¬ আর quantifier ∃, ∀ দিয়ে গড়া সূত্র। সূত্রের প্রতিটি চলক কোনো quantifier-এ বাঁধা থাকলে সূত্রটি fully quantified; তখন এটি হয় সত্য, নয় মিথ্যা। সব quantifier সামনে, তারপর quantifier-হীন অংশ (matrix) থাকলে সূত্রটি prenex normal form-এ আছে:

φ = Q1x1 Q2x2 ⋯ Qkxk [ψ], প্রতিটি Qi ∈ {∃, ∀}.

TQBF = {⟨φ⟩ : φ একটি সত্য fully quantified Boolean সূত্র}.

যেকোনো QBF-কে polynomial সময়ে prenex রূপে আনা যায় (চলকের নাম বদলে quantifier-গুলো সামনে টেনে), তাই এই পর্বে সব সূত্র prenex ধরা হবে, আর matrix ψ সাধারণত CNF. এখন পুরো পর্বের উদাহরণ:

φ = ∃x ∀y ∃z [ (x ∨ ¬y) ∧ (y ∨ z) ∧ (¬y ∨ ¬z) ]

শেষ দুটি clause একসঙ্গে বলে z = ¬y: y আর z-এর ঠিক একটি সত্য। প্রথম clause বলে y সত্য হলে x-কেও সত্য হতে হবে। তাই x = 1 নিলে, y যা-ই হোক, z = ¬y নিয়ে সব clause সত্য: φ সত্য, ⟨φ⟩ ∈ TQBF. এবার quantifier-এর ক্রম বদলে দেখুন: ∃z ∀y ∃x [একই ψ] বলে, এমন একটি z আছে যা y-এর দুটি মানেই z = ¬y রাখে। অসম্ভব, তাই এই সূত্র মিথ্যা। Matrix এক, শুধু ক্রম আলাদা, অথচ উত্তর উল্টো।

দুটি বিশেষ ক্ষেত্র চেনা। সব quantifier ∃ হলে প্রশ্নটি ঠিক SAT: ∃x1⋯∃xk ψ সত্য ⇔ ψ satisfiable. সব quantifier ∀ হলে প্রশ্নটি “ψ কি tautology?”, যা coNP-এর পরিচিত সমস্যা (পর্ব ৬২)। TQBF দুটিকেই ধরে, আর পালাক্রমে যত খুশি ∃ আর ∀ মেশাতে দেয়। শুধু ∃ বসানো একটি reduction, তাই SAT ≤p TQBF; ফলে TQBF অন্তত NP-hard. এই পর্ব দেখাবে, আসলে সে অনেক বেশি কিছু।

φ = ∃x ∀y ∃z ψ-এর মূল্যায়ন-গাছ

∃ node “অথবা”-র মতো, ∀ node “এবং”-এর মতো; প্রতিটি node-এর নিচে তার মান।

Evaluation tree of the QBF Ex Ay Ez psi 0 1 0 1 0 1 ∃x = 1 ∀y = 0 ∀y = 1 ∃z = 1 ∃z = 0 ∃z = 1 ∃z = 1 0 000 1 001 0 010 0 011 0 100 1 101 1 110 0 111 ∃: কোনো একটি সন্তান 1 হলেই 1 ∀: সব সন্তান 1 হলে তবেই 1 ড্যাশ: এই leaf কখনো দেখা হয়নি তীরের 0/1 = চলকের মান; সবুজ ফ্রেম 1, লাল ফ্রেম 0
ছবি ৬৫.১ — গাছের প্রতিটি স্তর একটি quantifier. x = 0-এর দিকে ∀y মিথ্যা, কারণ y = 1-এ কোনো z কাজ করে না; x = 1-এর দিকে দুটি y-তেই একটি z আছে। মূল ∃x তাই 1. ডান প্রান্তের leaf 111 কখনো দেখার দরকার হয়নি।

২ · TQBF ∈ PSPACE — একটি frame-এ একটি quantifier

ছবির গাছটি এক ধরনের game tree, আর তা থেকেই algorithm বেরিয়ে আসে। প্রথম quantifier সরিয়ে চলকটিতে 0 বসিয়ে বাকি সূত্রের মান বের করুন, তারপর 1 বসিয়ে। ∃ হলে দুটির কোনো একটি সত্য হলেই সত্য, ∀ হলে দুটিই সত্য হতে হবে। Quantifier ফুরিয়ে গেলে শুধু matrix-এর মান হিসাব। এটি গাছের ওপর depth-first search.

উপপাদ্য ২.১

TQBF ∈ PSPACE. আরও নির্দিষ্টভাবে, TQBF ∈ SPACE(n), যেখানে n = |⟨φ⟩|.

প্রমাণ: নিচের algorithm T নিন। Input ⟨φ⟩, φ prenex রূপে।

  1. φ-তে কোনো quantifier না থাকলে φ শুধু ধ্রুবক 0/1 আর সংযোজকের একটি রাশি; তার মান হিসাব করে 1 হলে গ্রহণ, নইলে বর্জন। — ভিত্তি
  2. φ = ∃x ψ হলে: ψ-তে x = 0 বসিয়ে T-কে recursive ভাবে ডাকুন, তারপর x = 1 বসিয়ে। কোনো একটি গ্রহণ করলে গ্রহণ, নইলে বর্জন। φ = ∀x ψ হলে দুটিই গ্রহণ করলে গ্রহণ। — quantifier-এর অর্থ
  3. সঠিকতা quantifier-এর সংখ্যা k-এর ওপর induction: k = 0-এ ধাপ ১ ঠিক; k-তে সঠিক ধরে নিলে ধাপ ২ ঠিক ∃ আর ∀-এর সংজ্ঞাই লেখে। — সঠিকতা
  4. জায়গা: recursion-এর গভীরতা k + 1 ≤ n + 1. প্রতিটি frame মনে রাখে শুধু কোন চলকে এখন কোন মান, আর 0 শেষ হয়ে 1 চলছে কি না: ধ্রুবক জায়গা (চলকের নম্বর রাখতে O(log n) বিট লাগলেও যোগফল O(n log n), polynomial; চলকের মান সরাসরি সূত্রের কপিতে লিখলে O(n)). Matrix-এর মান হিসাবে লাগে O(n). ভাইয়ের শাখা শেষ হলে তার জায়গা ফেরত পাওয়া যায়, তাই মোট জায়গা O(n). — জায়গার পুনর্ব্যবহার
  5. অতএব T একটি polynomial (আসলে রৈখিক) জায়গার decider, আর TQBF ∈ PSPACE. ∎

সময়ের হিসাব আলাদা: সবচেয়ে খারাপ ক্ষেত্রে গাছের 2kটি leaf-ই দেখতে হয়। জায়গা আর সময়ের এই পার্থক্য পর্ব ৬৪-এর মূল কথা: জায়গা বারবার ব্যবহার করা যায়, সময় যায় না। নিচের stepper গাছটিকে ঠিক এই algorithm-এর ক্রমে ঘুরে দেখে; algorithm প্রথমে 0, তারপর 1 চেষ্টা করে, আর উত্তর জানা হয়ে গেলে বাকি শাখা বাদ দেয়।

1∃x: আগে x = 0, দরকার হলে x = 12∀y: y = 0, তারপর y = 13∃z: আগে z = 0, দরকার হলে z = 14ψ = (x ∨ ¬y)(y ∨ z)(¬y ∨ ¬z)
অবস্থা
(x, y, z)
ψ
দেখা leaf
stack
  1. প্রথম leaf. x = 0, y = 0, z = 0. দ্বিতীয় clause (y ∨ z) মিথ্যা, তাই ψ = 0. ∃z এখনো হার মানেনি: z = 1 বাকি। Stack-এ তিনটি quantifier-এর frame.
  2. ∃z পেল। z = 1-এ তিনটি clause-ই সত্য, ψ = 1. তাই ∃z সত্য, অর্থাৎ x = 0, y = 0 শাখা সত্য। ∀y এবার y = 1 পরীক্ষা করবে।
  3. y = 1, ব্যর্থতা। প্রথম clause (x ∨ ¬y) = (0 ∨ 0) মিথ্যা, z যা-ই হোক। দুটি leaf-ই 0, তাই ∃z মিথ্যা। মোট ৪টি leaf দেখা হলো।
  4. x = 0 বাতিল। ∀y-এর একটি শাখা মিথ্যা, তাই ∀y মিথ্যা। ∃x এখন x = 1 চেষ্টা করবে। লক্ষ করুন, y আর z-এর frame সরে গেছে: সেই জায়গা আবার ব্যবহার হবে।
  5. x = 1, y = 0. z = 0-এ (y ∨ z) মিথ্যা, z = 1-এ সব সত্য। ∃z সত্য। একই তিনটি frame, নতুন মান নিয়ে।
  6. x = 1, y = 1. প্রথম চেষ্টা z = 0-এই ψ = 1: (1 ∨ 0), (1 ∨ 0), (0 ∨ 1). ∃z সত্য, তাই ∀y-এর দুটি শাখাই সত্য, আর ∃x সত্য। φ ∈ TQBF.
  7. খরচ। আটটির মধ্যে ৭টি leaf দেখা হয়েছে; (1, 1, 1) কখনো লাগেনি। কিন্তু stack কখনো ৪টি frame (তিন quantifier আর একটি leaf-হিসাব) ছাড়ায়নি। k চলকে leaf 2k পর্যন্ত, frame k + 1.

এবার একই algorithm Python-এ। ev একটিই dictionary a সবার মধ্যে ভাগ করে নেয়: প্রতিটি frame নিজের চলকের ঘরে মান লেখে, কাজ শেষে মুছে দেয়। এটাই “জায়গার পুনর্ব্যবহার”। গোনা হচ্ছে মোট calls, leaf আর সর্বোচ্চ recursion depth. শেষে একটি পরিবার: ∃x1 ∀x2 ∃x3 ⋯, যেখানে প্রতিটি ∀ চলকের পরের ∃ চলককে তার উল্টো হতে হয়।

# TQBF in polynomial space: one recursion frame per quantifier, values reused
stats = {"calls": 0, "leaves": 0, "depth": 0, "max": 0}
def holds(cls, a):                       # clause = list of (variable, wanted value)
    return all(any(a[v] == want for v, want in c) for c in cls)
def ev(prefix, cls, a):
    stats["calls"] += 1; stats["depth"] += 1
    stats["max"] = max(stats["max"], stats["depth"])
    if not prefix:
        stats["leaves"] += 1; r = holds(cls, a)
    else:
        q, v = prefix[0]; r = q == "A"   # A: true until a 0 is found
        for b in (0, 1):                 # the same slot a[v] is reused
            a[v] = b
            sub = ev(prefix[1:], cls, a)
            if q == "E" and sub: r = True; break
            if q == "A" and not sub: r = False; break
        del a[v]
    stats["depth"] -= 1
    return r
def run(name, prefix, cls):
    for k in stats: stats[k] = 0
    r = ev(prefix, cls, {})
    print(f"{name:12} {str(r):5} calls {stats['calls']:6}  leaves {stats['leaves']:5}  max depth {stats['max']}")
psi = [[("x", 1), ("y", 0)], [("y", 1), ("z", 1)], [("y", 0), ("z", 0)]]
run("Ex Ay Ez", [("E", "x"), ("A", "y"), ("E", "z")], psi)
run("Ez Ay Ex", [("E", "z"), ("A", "y"), ("E", "x")], psi)
for m in (5, 9, 13, 17, 21):             # E x1 A x2 E x3 ...: x(2i+1) = not x(2i)
    pre = [("E" if i % 2 else "A", i) for i in range(1, m + 1)]
    cls = [c for i in range(2, m, 2) for c in ([(i, 1), (i + 1, 1)], [(i, 0), (i + 1, 0)])]
    run(f"chain m={m}", pre, cls)

আসল আউটপুট (ব্রাউজারের Python):

Ex Ay Ez     True  calls     14  leaves     7  max depth 4
Ez Ay Ex     False calls     11  leaves     5  max depth 4
chain m=5    True  calls     20  leaves     8  max depth 6
chain m=9    True  calls    128  leaves    48  max depth 10
chain m=13   True  calls    704  leaves   256  max depth 14
chain m=17   True  calls   3584  leaves  1280  max depth 18
chain m=21   True  calls  17408  leaves  6144  max depth 22

প্রথম লাইন stepper-এর সঙ্গে হুবহু মেলে: ৭টি leaf, সর্বোচ্চ depth 4. দ্বিতীয় লাইনে একই matrix, ক্রম ∃z ∀y ∃x: উত্তর False, অংশ ১-এর যুক্তি মতো। পরিবারের সারিগুলোতে m চার করে বাড়লে calls প্রায় পাঁচ গুণ হচ্ছে (৭০৪ → ৩,৫৮৪ → ১৭,৪০৮), কারণ প্রতি দুটি ∀ চলকে leaf চার গুণ, আর ∃ কখনো কখনো দুটি মানই চেষ্টা করে। অথচ max depth ঠিক m + 1: সরলরেখায় বাড়ছে। সময় exponential, জায়গা রৈখিক।

৩ · TQBF PSPACE-hard — গণনাকে quantifier-এ লেখা

এখন উল্টো দিক: PSPACE-এর প্রতিটি সমস্যা TQBF-এ নামানো যায়। প্রথমে সংজ্ঞা, পর্ব ৫৯-এর NP-complete-এর ছাঁচে।

সংজ্ঞা ৩.১ (PSPACE-hard আর PSPACE-complete)

B PSPACE-hard, যদি PSPACE-এর প্রতিটি A-এর জন্য একটি polynomial-time reduction A ≤p B থাকে। B PSPACE-complete, যদি B PSPACE-hard আর B ∈ PSPACE.

Reduction-কে polynomial সময়ের হতে হয়, polynomial জায়গার নয়। কারণটি সরল: polynomial জায়গার reduction নিজেই পুরো সমস্যা সমাধান করে একটি স্থির “হ্যাঁ” বা “না” instance লিখে দিতে পারত, তখন PSPACE-এর প্রতিটি অ-তুচ্ছ সমস্যা “complete” হয়ে যেত। দিকের নিয়মও আগের মতো: A ≤p B আর B ∈ P হলে A ∈ P. তাই কোনো PSPACE-complete সমস্যা P-তে থাকলে P = PSPACE হবে, আর NP-তে থাকলে NP = PSPACE.

উপপাদ্য ৩.২ (Stockmeyer–Meyer, ১৯৭৩)

TQBF PSPACE-complete.

TQBF ∈ PSPACE অংশ ২-এ প্রমাণিত। বাকি কাজ: যেকোনো A ∈ PSPACE থেকে TQBF-এ polynomial সময়ের reduction. ধরি M একটি deterministic Turing machine, যা A-কে nk জায়গায় decide করে। M-এর configuration মানে tape-এর nkটি ঘর, state আর head-এর অবস্থান; পর্ব ৬০-এর tableau-র এক সারির মতো একে O(nk)টি Boolean চলকে লেখা যায়। পর্ব ৬৪-এর configuration-গোনা থেকে, এমন configuration সর্বোচ্চ 2d·nkটি, কোনো ধ্রুবক d-এর জন্য। ধরে নেওয়া যায় M গ্রহণের আগে tape মুছে head বাঁয়ে আনে, ফলে গ্রহণের configuration একটিই, caccept.

এখন সূত্র φc1,c2,t বানাব, যার অর্থ “c1 থেকে বড়জোর t ধাপে c2-তে পৌঁছানো যায়” (configuration graph-এ t দৈর্ঘ্যের পথ), t একটি 2-এর ঘাত। তাহলে

w ∈ A ⇔ φcstart,caccept,h সত্য, যেখানে h = 2d·nk

কারণ M থামে বলে কোনো configuration পুনরাবৃত্ত হয় না, তাই গ্রহণ ঘটলে তা h ধাপের মধ্যেই ঘটে।

ভিত্তি, t = 1: φc1,c2,1 বলে, c1 = c2, অথবা c2 হলো c1-এর এক-ধাপ পরের configuration. প্রথমটি ঘরে ঘরে চলকের সমতা; দ্বিতীয়টি Cook–Levin-এর legal window-এর মতো স্থানীয় শর্ত। দুটিই O(nk) আকারের।

সরল চেষ্টা: মাঝের একটি configuration m অনুমান করে পথটিকে দুই অর্ধেকে ভাঙা, ঠিক পর্ব ৬৪-এর CANYIELD-এর মতো:

φc1,c2,t = ∃m [ φc1,m,t/2 ∧ φm,c2,t/2 ]

এখানে ∃m মানে m-এর সব চলকের ওপর ∃. সঠিক, কিন্তু আকার? প্রতিটি স্তরে সূত্রের দুটি নকল লাগে, তাই S(t) = 2·S(t/2) + O(nk), অর্থাৎ S(t) = O(t · nk). t = h = 2d·nk-এ এটি exponential. CANYIELD algorithm হিসেবে ঠিকই চলে, কারণ প্রথম অর্ধেকের কাজ শেষে তার জায়গা দ্বিতীয় অর্ধেক আবার ব্যবহার করে। কিন্তু সূত্র জায়গা পুনর্ব্যবহার করতে পারে না: যা লেখা হয়, তা থাকে।

∀-কৌশল: দুই অর্ধেকের জন্য দুটি নকল না লিখে একটি নকল লিখুন, আর একটি ∀ দিয়ে বলুন “এই নকলটি দুটি জোড়ার প্রতিটিতে সত্য”:

φc1,c2,t = ∃m ∀(c3, c4) ∈ {(c1, m), (m, c2)} [ φc3,c4,t/2 ]

“∀ জোড়াটি এই দুটির একটি” আসলে সাধারণ Boolean ভাষায় লেখা যায়:

∃m ∀c3 ∀c4 [ ((c3 = c1 ∧ c4 = m) ∨ (c3 = m ∧ c4 = c2)) → φc3,c4,t/2 ]

এখানে a → b মানে ¬a ∨ b, আর c = c′ মানে দুই configuration-এর চলকগুলো ঘরে ঘরে সমান। এখন প্রতিটি স্তরে নতুন অংশ m, c3, c4-এর চলক আর কয়েকটি সমতা-পরীক্ষা: O(nk). পুনরাবৃত্তি S(t) = S(t/2) + O(nk), স্তর log2 h = d·nkটি, তাই

|φcstart,caccept,h| = O(nk · d·nk) = O(n2k)

প্রমাণ (A ≤p TQBF):

  1. Reduction f: w ↦ φcstart,caccept,h, ওপরের ∀-কৌশলে recursive ভাবে লেখা। cstart আর caccept ধ্রুবক মান হিসেবে ঢোকে। — নির্মাণ
  2. সূত্রের আকার O(n2k), আর একটি সরল recursive প্রোগ্রাম তা আকারের সমানুপাতিক সময়ে লেখে: f polynomial সময়ের। — দক্ষতা
  3. t-এর ওপর induction: φc1,c2,t সত্য ⇔ c1 থেকে বড়জোর t ধাপে c2. t = 1 ভিত্তির সংজ্ঞা। t-এ: পথ থাকলে তার মাঝের configuration-কে m নিন; তখন দুটি জোড়ার প্রতিটি t/2 ধাপে যুক্ত, আর induction-এ ভেতরের সূত্র দুটিতেই সত্য, অন্য সব (c3, c4)-এ → এর বাঁ দিক মিথ্যা। উল্টো দিকে সূত্র সত্য হলে কোনো m-এর জন্য দুটি জোড়াতেই ভেতরের সূত্র সত্য, অর্থাৎ t/2 + t/2 ধাপের পথ। — সঠিকতা
  4. Quantifier-গুলো ভেতরে থাকলেও চলকের নাম আলাদা বলে সামনে টেনে prenex রূপ পাওয়া যায়। অতএব w ∈ A ⇔ f(w) ∈ TQBF. ∎

নিচের ব্লক কথাগুলো একটি ছোট configuration graph-এ পরখ করে: ৮টি configuration (প্রতিটি ৩টি Boolean চলকে), ৯টি তীর। দুই পদ্ধতিতে reacht সূত্র বানিয়ে আকার (সূত্র-গাছের চিহ্ন-সংখ্যা) ছাপে, তারপর ∀-কৌশলের t = 8 সূত্রটি নিজের evaluator-এ মূল্যায়ন করে BFS-এর সঙ্গে মেলায়।

# reach_t(u, v) as a QBF: the naive split vs the forall trick, on 8 configurations
from itertools import product
B, EDGES = 3, {(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (2, 0), (5, 3)}
vec = lambda name: [f"{name}{i}" for i in range(B)]          # 3 Boolean variables
eq = lambda u, v: ("and", [("iff", a, b) for a, b in zip(u, v)])
code = lambda u, k: ("and", [("v", a) if k >> i & 1 else ("not", ("v", a)) for i, a in enumerate(u)])
step = lambda u, v: ("or", [eq(u, v)] + [("and", [code(u, p), code(v, q)]) for p, q in EDGES])
def naive(u, v, t, l=0):    # E m [reach(u, m, t/2) and reach(m, v, t/2)]
    if t == 1: return step(u, v)
    m = vec(f"m{l}_"); return ("E", m, ("and", [naive(u, m, t // 2, l + 1), naive(m, v, t // 2, l + 1)]))
def trick(u, v, t, l=0):    # E m A c,d [(c,d) = (u,m) or (m,v)  ->  reach(c, d, t/2)]
    if t == 1: return step(u, v)
    m, c, d = vec(f"m{l}_"), vec(f"c{l}_"), vec(f"d{l}_")
    pair = ("or", [("and", [eq(c, u), eq(d, m)]), ("and", [eq(c, m), eq(d, v)])])
    return ("E", m, ("A", c + d, ("imp", pair, trick(c, d, t // 2, l + 1))))
def size(f):                # number of symbols in the formula tree
    k = f[0]
    if k in ("v", "iff"): return 1 if k == "v" else 3
    subs = f[1] if k in ("and", "or") else [f[2]] if k in ("E", "A") else f[1:]
    return 1 + (len(f[1]) if k in ("E", "A") else 0) + sum(map(size, subs))
def ev(f, env):
    k = f[0]
    if k in ("v", "iff"): return env[f[1]] if k == "v" else env[f[1]] == env[f[2]]
    if k == "not": return not ev(f[1], env)
    if k == "imp": return not ev(f[1], env) or ev(f[2], env)
    if k in ("and", "or"): return (all if k == "and" else any)(ev(g, env) for g in f[1])
    vals = (dict(zip(f[1], bs)) for bs in product([False, True], repeat=len(f[1])))
    return (any if k == "E" else all)(ev(f[2], {**env, **b}) for b in vals)
a, b = vec("a"), vec("b"); put = lambda u, k: {x: bool(k >> i & 1) for i, x in enumerate(u)}
for t in (1, 2, 4, 8, 16): print(f"t = {t:2}: naive {size(naive(a, b, t)):5}  trick {size(trick(a, b, t)):4}")
F = trick(a, b, 8)
for s in (4, 7):         # all goals g reachable from s within 8 steps
    qbf, cur = [g for g in range(8) if ev(F, {**put(a, s), **put(b, g)})], {s}
    for _ in range(8): cur |= {q for p, q in EDGES if p in cur}
    print(f"from {s}: QBF {qbf}  BFS {sorted(cur)}")

আসল আউটপুট (ব্রাউজারের Python):

t =  1: naive   120  trick  120
t =  2: naive   245  trick  175
t =  4: naive   495  trick  230
t =  8: naive   995  trick  285
t = 16: naive  1995  trick  340
from 4: QBF [3, 4, 5, 6, 7]  BFS [3, 4, 5, 6, 7]
from 7: QBF [7]  BFS [7]

সরল সূত্র প্রতিবার t দ্বিগুণে প্রায় দ্বিগুণ (১২০ → ২৪৫ → ৪৯৫ → ৯৯৫ → ১,৯৯৫): আকার t-এর সমানুপাতিক। ∀-কৌশলের সূত্র প্রতি স্তরে ঠিক ৫৫টি চিহ্ন বাড়ে (তিন নতুন configuration-এর ৯টি চলক আর সমতা-পরীক্ষা): আকার log t-এর সমানুপাতিক। এই ছোট উদাহরণে t = 8; আসল প্রমাণে t = 2d·nk, যেখানে প্রথমটি অচল আর দ্বিতীয়টি O(n2k). শেষ দুই লাইনে QBF-এর উত্তর আর BFS হুবহু এক: configuration 4 থেকে 3, 5, 6, 7-এ যাওয়া যায় (4 নিজে t = 0 ধাপে), 0, 1, 2-এ নয়; 7 থেকে কোথাও নয়।

সাধারণ ভুল: “TQBF PSPACE-hard দেখাতে TQBF-কে কোনো PSPACE সমস্যায় reduce করি।” না: কঠিনতা প্রমাণে পরিচিত সমস্যাগুলো বাঁয়ে, নতুন সমস্যা ডানে (A ≤p TQBF). আরেকটি ভুল: CANYIELD-এর হুবহু অনুবাদ (সরল সূত্র) লিখে “polynomial” বলা। CANYIELD-এর জায়গা polynomial, কিন্তু সূত্রে নকলের সংখ্যা exponential. ∀-কৌশল ছাড়া প্রমাণ সম্পূর্ণ নয়।

৪ · Formula game — সূত্র মানেই দুই খেলোয়াড়ের লড়াই

অংশ ১-এর analogy এবার নিখুঁত করা যাক। φ = ∃x1 ∀x2 ∃x3 ⋯ Qkxk [ψ] দিয়ে একটি খেলা সংজ্ঞায়িত হয়। দুই খেলোয়াড়: E (∃-এর পক্ষ) আর A (∀-এর পক্ষ)। চলকগুলো ক্রমানুসারে মান পায়: ∃-চলকের মান বাছেন E, ∀-চলকের মান বাছেন A. সব চলকের মান হয়ে গেলে ψ সত্য হলে E জেতেন, মিথ্যা হলে A.

সংজ্ঞা ৪.১ (winning strategy আর FORMULA-GAME)

একজন খেলোয়াড়ের winning strategy হলো এমন একটি নিয়ম, যা খেলার প্রতিটি সম্ভাব্য অবস্থায় তাঁর চাল বলে দেয়, আর প্রতিপক্ষ যা-ই খেলুন, সেই নিয়ম মানলে তিনি জেতেন। FORMULA-GAME = {⟨φ⟩ : φ-এর খেলায় E-এর winning strategy আছে}.

উপপাদ্য ৪.২

FORMULA-GAME = TQBF. অর্থাৎ φ সত্য ⇔ E-এর winning strategy আছে।

প্রমাণ (quantifier-এর সংখ্যা k-এর ওপর induction):

  1. k = 0: কোনো চাল নেই; E জেতেন ⇔ ψ সত্য ⇔ φ সত্য। — ভিত্তি
  2. φ = ∃x φ′ হলে: φ সত্য ⇔ কোনো b ∈ {0, 1}-এর জন্য φ′[x = b] সত্য ⇔ (induction) কোনো b-এর পরে বাকি খেলায় E-এর winning strategy আছে ⇔ E প্রথম চালে সেই b খেলে জিততে পারেন। — E-এর পালা
  3. φ = ∀x φ′ হলে: φ সত্য ⇔ দুটি b-তেই φ′[x = b] সত্য ⇔ A যে b-ই খেলুন, E-এর জবাবি winning strategy আছে ⇔ পুরো খেলায় E-এর winning strategy আছে (দুই জবাবকে একটি নিয়মে জুড়ে)। — A-এর পালা
  4. দুই ক্ষেত্রেই সমতা টিকে থাকে, তাই সব k-এর জন্য উপপাদ্য সত্য। ∎

একটি লক্ষ করার বিষয়: winning strategy একটি function, যা A-এর আগের চালগুলো দেখে E-এর পরের চাল বলে। আমাদের φ-এ সেটি “x = 1, আর z = ¬y”. প্রশ্নটি জটিল হয়, কারণ এমন function খুঁজতে A-এর প্রতিটি সম্ভাব্য খেলা মাথায় রাখতে হয়। নিচের stepper খেলাটি চাল ধরে ধরে দেখায়।

1চাল ১: E বাছেন x2চাল ২: A বাছেন y3চাল ৩: E বাছেন z4ψ সত্য হলে E, নইলে A জেতেন
খেলার অবস্থা
x
y
z
তিন clause
  1. খেলার আগে। ψ = (x ∨ ¬y) ∧ (y ∨ z) ∧ (¬y ∨ ¬z). E-এর পরিকল্পনা: প্রথমে x = 1, আর শেষে z হবে y-এর উল্টো। এটিই একটি winning strategy, যা পরের ধাপগুলো যাচাই করবে।
  2. চাল ১, E: x = 1. এতে প্রথম clause (x ∨ ¬y) A যা-ই করুন সত্য থাকে। A-এর হাতে এখন একটিমাত্র অস্ত্র: y দিয়ে শেষ দুই clause-এ চাপ দেওয়া।
  3. চাল ২, A: y = 1. এখন (y ∨ z) সত্য, কিন্তু (¬y ∨ ¬z) সত্য রাখতে z-কে 0 হতে হবে।
  4. চাল ৩, E: z = 0. তিনটি clause: (1 ∨ 0), (1 ∨ 0), (0 ∨ 1), সবই সত্য। ψ = 1, E জেতেন।
  5. A অন্যভাবে খেললে। y = 0 হলে (y ∨ z)-এর জন্য z = 1 লাগে, আর E কৌশল মতো z = ¬y = 1 খেলেন: (1 ∨ 1), (0 ∨ 1), (1 ∨ 0), আবার সব সত্য। A-এর দুটি চালেরই জবাব আছে।
  6. E ভুল শুরু করলে। x = 0 খেললে A খেলেন y = 1, আর প্রথম clause (0 ∨ 0) মিথ্যা, z যা-ই হোক। তখন A-এর winning strategy থাকে। তাই E-এর জন্য x = 1 বাধ্যতামূলক, ঠিক ছবি ৬৫.১-এর বাঁ শাখার মতো।

এখান থেকে দুটি শিক্ষা। প্রথমত, TQBF-কে খেলা হিসেবে দেখলে PSPACE-এর অনেক সমস্যা চেনা সহজ হয়: “এক পক্ষ চাল দেয়, অন্য পক্ষ জবাব দেয়, খেলা polynomial চালে শেষ হয়” এমন যেকোনো খেলার বিজয়ী নির্ধারণ PSPACE-এ, অংশ ২-এর মতো একই recursion দিয়ে। AI কোর্সের পর্ব ৪২-এর minimax আসলে এই recursion-ই, শুধু মান 0/1-এর বদলে স্কোর। দ্বিতীয়ত, NP-তে “certificate” একটি ছোট string, কিন্তু এখানে প্রমাণ একটি strategy, যা সাধারণত exponential আকারের টেবিল। ছোট certificate না থাকাটাই সন্দেহ জাগায় যে TQBF NP-তে নেই, যদিও তা প্রমাণিত নয়।

৫ · Generalized geography — বাজারঘরের “জেলা দখল” PSPACE-complete

ছোটবেলার শব্দ-খেলায় একজন একটি জায়গার নাম বলেন, পরের জনকে এমন নাম বলতে হয় যা আগের নামের শেষ অক্ষর দিয়ে শুরু, আর কোনো নাম দুবার বলা যায় না। জায়গাগুলোকে node আর “শেষ অক্ষর = প্রথম অক্ষর”-কে তীর ধরলে খেলাটি একটি directed graph-এ পথ বানানো। যেকোনো graph-এ খেললে তাকে বলে generalized geography, আর অংশ ১-এর “জেলা দখল” ঠিক এটাই।

সংজ্ঞা ৫.১ (generalized geography)

একটি directed graph G আর একটি node b দেওয়া। খেলার টোকেন b-তে, আর b ব্যবহৃত বলে গণ্য। Player I আর Player II পালা করে (I আগে) টোকেনটিকে বর্তমান node থেকে একটি তীর ধরে এমন node-এ নেন, যা আগে ব্যবহৃত হয়নি; সেটিও ব্যবহৃত হয়ে যায়। যিনি চাল দিতে পারেন না, তিনি হারেন। GG = {⟨G, b⟩ : এই খেলায় Player I-এর winning strategy আছে}.

উপপাদ্য ৫.২ (Schaefer, ১৯৭৮)

GG PSPACE-complete.

GG ∈ PSPACE: recursive algorithm: “বর্তমান node u থেকে যে চাল দেবেন, তিনি জিততে পারবেন কি? u-এর প্রতিটি অব্যবহৃত প্রতিবেশী v-এর জন্য v-কে ব্যবহৃত চিহ্ন দিয়ে প্রশ্ন করুন, v থেকে প্রতিপক্ষ জিততে পারেন কি না; কোনো v-তে না পারলে উত্তর হ্যাঁ, তারপর চিহ্ন মুছুন।” প্রতিটি চালে একটি node ব্যবহৃত হয়, তাই recursion-এর গভীরতা ≤ |V|. ব্যবহৃত-চিহ্নের একটি ভাগ করা array (|V| বিট) আর প্রতি frame-এ বর্তমান node ও কোন প্রতিবেশী চলছে (O(log |V|) বিট): মোট O(|V| log |V|) জায়গা, polynomial.

GG PSPACE-hard, প্রমাণের রূপরেখা (FORMULA-GAME ≤p GG): φ = ∃x1 ∀x2 ⋯ ∃xk [ψ] নিন, ψ CNF. Quantifier পালাক্রমে আছে আর প্রথম ও শেষটি ∃, এমন ধরা যায়: দরকার হলে অব্যবহৃত নকল চলক যোগ করলেই হয়। এখন graph Gφ:

  1. প্রতিটি চলক xi-এর জন্য একটি diamond: ওপরে Ti, তা থেকে দুই পাশে Li (মানে xi = সত্য) আর Ri (মিথ্যা), দুটি থেকেই নিচে Bi. তারপর Bi → Ti+1. শুরু b = T1. — মান বাছাইয়ের জায়গা
  2. পালার হিসাব: প্রতিটি diamond পেরোতে তিনটি চাল লাগে (পাশ, নিচ, পরের ওপর)। তিন বিজোড়, তাই diamond 1-এ পাশ বাছেন Player I, diamond 2-এ Player II, diamond 3-এ আবার I: ঠিক ∃, ∀, ∃-এর পালা। Player I = E, Player II = A. — quantifier = পালা
  3. শেষ অংশ: Bk → c, c থেকে প্রতিটি clause-এর জন্য node Cj, Cj থেকে তার প্রতিটি literal-এর node, আর literal node থেকে diamond-এ ফেরার তীর: xi হলে Li-তে, ¬xi হলে Ri-তে। — যাচাইয়ের জায়গা
  4. কেন কাজ করে: c থেকে A একটি clause বাছেন (“এটি মিথ্যা”), E তার একটি literal বাছেন (“এটি সত্য”)। এরপর A-কে ফেরার তীর ধরতে হয়। Literal সত্য হলে সেই পাশের node আগেই ব্যবহৃত, তাই A আটকে হারেন। Literal মিথ্যা হলে A সেই অব্যবহৃত পাশে যান, আর E-কে তার একমাত্র তীর ধরে Bi-তে যেতে হয়, যা ব্যবহৃত: E হারেন। তাই E জেতেন ⇔ মানগুলো ψ-এর প্রতিটি clause সত্য করে। — সঠিকতার মূল কথা
  5. Gφ-এর আকার φ-এর রৈখিক, আর তা polynomial সময়ে লেখা যায়। অতএব φ ∈ FORMULA-GAME ⇔ ⟨Gφ, T1⟩ ∈ GG. (Sipser-এর বইয়ে এই নির্মাণের পূর্ণ প্রমাণ আছে।) ∎

φ থেকে বানানো geography graph Gφ

বাঁয়ে তিনটি diamond (x, y, z), ডানে তিনটি clause আর তাদের literal node.

Generalized geography graph built from the formula Ex Ay Ez psi x → L1 ¬y → R2 y → L2 z → L3 ¬y → R2 ¬z → R3 T1 L1 R1 B1 T2 L2 R2 B2 T3 L3 R3 B3 c C1 C2 C3 ∃x · E ∀y · A ∃z · E সবুজ L = সত্য, লাল R = মিথ্যা “x → L1”: literal node থেকে L1-এ তীর কমলা: দুজনের সেরা খেলার পথ
ছবি ৬৫.২ — ২২টি node-এর Gφ. Literal node থেকে diamond-এ ফেরার তীর ভিড় এড়াতে লেবেলে লেখা (“¬y → R2” মানে R2-তে তীর)। কমলা পথ: E x = 1 নেন, A y = 1, E z = 0; তারপর A clause C1 বাছেন, E literal x, আর L1 আগেই ব্যবহৃত বলে A আটকে যান।
1T → L (সত্য) বা R (মিথ্যা) → B2B1 → T2, B2 → T3, B3 → c3c → C1, C2, C34C → literal → L বা R-এ ফেরা
খেলা
শেষের পথ
পরের চাল
মান
  1. শুরু। টোকেন T1-এ, T1 ব্যবহৃত। প্রথম চাল Player I-এর, অর্থাৎ E-এর, আর তিনি x-এর diamond-এর ওপরে দাঁড়িয়ে।
  2. E বাছেন L1. বাঁ পাশ মানে x = 1. L1 এখন ব্যবহৃত, আর R1 অব্যবহৃত থেকে গেল: এই চিহ্নই পরে x-এর মান “মনে রাখবে”।
  3. দুটি বাধ্য চাল। L1-এর একমাত্র তীর B1-এ, তাই A যান B1-এ; B1-এর একমাত্র তীর T2-তে, তাই E যান T2-তে। পরের চাল A-এর: ঠিক ∀y-এর পালা।
  4. A বাছেন L2 (y = 1). তারপর বাধ্য চাল: E যান B2-তে, A যান T3-তে। এবার পাশ বাছার পালা আবার E-এর।
  5. E বাছেন R3 (z = 0). কৌশল z = ¬y. তারপর A যান B3-তে, E যান c-তে। সব মান ঠিক হয়ে গেছে: x = 1, y = 1, z = 0.
  6. A বাছেন C1. A দাবি করছেন “C1 = (x ∨ ¬y) মিথ্যা”. অন্য দুটি clause বাছলেও ফল একই হতো, কারণ তিনটিই সত্য।
  7. E বাছেন literal x. C1:x থেকে একমাত্র তীর L1-এ, যা ধাপ ২ থেকে ব্যবহৃত। A-এর কোনো চাল নেই: A হারেন, E জেতেন।
  8. E ভুল literal বাছলে। ¬y বেছে নিলে A যান R2-তে (y = 1 বলে R2 অব্যবহৃত)। R2-এর একমাত্র তীর B2-তে, যা ব্যবহৃত: এবার E আটকে হারেন। মিথ্যা literal দাবি করলে সত্যিই হারতে হয়।

নিচের ব্লক reduction-টি হুবহু বানায়, তারপর খেলাটি সমাধান করে: memoization-সহ recursion, যা প্রতিটি অবস্থায় একটি জেতার চাল খোঁজে। Literal node-এর নাম C1:1 মানে clause 1-এর literal x1 (= x), C3:-3 মানে ¬x3. শেষে ১৫০টি এলোমেলো সূত্রে TQBF-এর উত্তর আর geography-র বিজয়ী মেলানো হয়।

import random; from functools import lru_cache
def build(n, cls):                       # FORMULA-GAME -> generalized geography
    E = {}; add = lambda u, v: E.setdefault(u, []).append(v)
    for i in range(1, n + 1):            # diamond i: L = true side, R = false side
        for s in "LR": add(f"T{i}", f"{s}{i}"); add(f"{s}{i}", f"B{i}")
        add(f"B{i}", f"T{i + 1}" if i < n else "c")
    for j, c in enumerate(cls, 1):       # clause node, literal nodes, back edges
        add("c", f"C{j}")
        for l in c:
            add(f"C{j}", f"C{j}:{l}"); add(f"C{j}:{l}", f"L{l}" if l > 0 else f"R{-l}")
    return E
def solver(E):
    @lru_cache(None)
    def win(u, used):                    # can the player to move from u force a win?
        return next((v for v in E.get(u, []) if v not in used
                     and not win(v, used | {v})), None)
    return win
def tqbf(n, cls, a=()):                  # x1 E, x2 A, x3 E, ...
    if len(a) == n: return all(any(a[abs(l) - 1] == (l > 0) for l in c) for c in cls)
    r = [tqbf(n, cls, a + (b,)) for b in (False, True)]
    return any(r) if len(a) % 2 == 0 else all(r)
cls = [(1, -2), (2, 3), (-2, -3)]         # (x or not y)(y or z)(not y or not z)
E = build(3, cls); win = solver(E); u, used, path = "T1", frozenset({"T1"}), ["T1"]
while True:                              # winner plays a winning move, loser the first legal one
    v = win(u, used) or next((v for v in E.get(u, []) if v not in used), None)
    if v is None: break
    u, used = v, used | {v}; path.append(v)
print(len(set(E) | {v for vs in E.values() for v in vs}), "nodes, I wins:", win("T1", frozenset(["T1"])) is not None)
print(" ".join(path), "| stuck:", "I" if len(path) % 2 else "II")
random.seed(7); agree = 0
for _ in range(150):
    n = random.choice([1, 3, 5]); vs = range(1, n + 1)
    f = [tuple(random.choice([1, -1]) * v for v in random.sample(vs, min(n, 2))) for _ in range(random.randint(1, 4))]
    agree += tqbf(n, f) == (solver(build(n, f))("T1", frozenset(["T1"])) is not None)
print("TQBF = geography winner on", agree, "of 150 random formulas")

আসল আউটপুট (ব্রাউজারের Python):

22 nodes, I wins: True
T1 L1 B1 T2 L2 B2 T3 R3 B3 c C1 C1:1 | stuck: II
TQBF = geography winner on 150 of 150 random formulas

Gφ-এ ২২টি node, ছবি ৬৫.২-এর মতো, আর Player I জেতেন, কারণ φ সত্য। দ্বিতীয় লাইনের পথ stepper-এর ধাপ ১ থেকে ৭-এর হুবহু খেলা: হেরে যাওয়া খেলোয়াড় প্রথম বৈধ চাল খেলেন বলে A y = 1 আর C1 বাছেন। শেষ লাইন ⇔-এর একটি সীমিত কিন্তু সত্যিকারের পরীক্ষা: ১, ৩ বা ৫ চলকের ১৫০টি সূত্রের প্রতিটিতে দুই উত্তর এক। পরীক্ষা প্রমাণ নয়; প্রমাণ ওপরের রূপরেখায়।

৬ · সত্যিকারের run — z3 দিয়ে QBF যাচাই

বাস্তবে QBF সমাধানের জন্য আলাদা solver আছে, আর SMT solver z3-ও Boolean চলকের ওপর ∃ আর ∀ সমেত সূত্র নিতে পারে। বন্ধ (সব চলক বাঁধা) সূত্রের জন্য z3-এর “sat” মানে সূত্রটি সত্য। একটি uv প্রকল্পে z3 দিয়ে তিনটি জিনিস যাচাই করা হলো: পর্বের সূত্র φ আর তার উল্টো ক্রম; ৩০০টি এলোমেলো alternating 3-CNF QBF (৩ থেকে ৮টি চলক, স্থির seed) z3 আর একটি সরল recursive evaluator-এ; আর অংশ ৩-এর ∀-কৌশলের reach8 সূত্র, এবার ৬৪টি (শুরু, শেষ) জোড়ার সবকটিতে, BFS-এর সঙ্গে।

সত্যিকারের run (ডেস্কটপ, uv প্রকল্পে z3-solver 5.4.1.0, Python 3.12.13; z3 MIT licence-এর। z3-এ কোনো usage-reporting বা telemetry নেই; installed package-এর Python code-এ network-এর কোনো import না পেয়ে নিশ্চিত হয়েছি):

~/bazarghar-toc$ uv add z3-solver
 + z3-solver==5.4.1.0
~/bazarghar-toc$ uv run python qbf_z3.py
z3 5.4.1
Ex Ay Ez psi : True
Ez Ay Ex psi : False
300 random QBFs (3-8 vars, E first): z3 = own evaluator in 300/300, true 114
reach_8 with the forall trick on 8 configurations: z3 = BFS in 64/64 pairs
total time 10.5 s

z3-ও বলে φ সত্য আর উল্টো ক্রমের সূত্র মিথ্যা, অংশ ১-এর হাতের যুক্তি আর অংশ ২-এর evaluator-এর সঙ্গে মিলে। ৩০০টি এলোমেলো সূত্রের প্রতিটিতে দুই পদ্ধতির উত্তর এক (১১৪টি সত্য, ১৮৬টি মিথ্যা: পরীক্ষাটি একপেশে নয়)। ∀-কৌশলের সূত্রে z3 ৬৪টি জোড়াতেই BFS-এর সঙ্গে একমত, অর্থাৎ অংশ ৩-এর নির্মাণ ব্রাউজারের বাইরে একটি স্বাধীন tool-এও ঠিক উত্তর দেয়। সময়টি এই ছোট ক্ষেত্রের; QBF solver-এর সাধারণ গতি নিয়ে এ থেকে কোনো সিদ্ধান্ত টানা যায় না।

Script-এর মূল অংশ, সূত্র বানানোর recursion, অংশ ৩-এর সূত্রের সরাসরি অনুবাদ:

def reach(u, v, t):
    if t == 1: return step(u, v)
    m, c, d = vec("m"), vec("c"), vec("d")
    pair = z3.Or(z3.And(eq(c, u), eq(d, m)), z3.And(eq(c, m), eq(d, v)))
    return z3.Exists(m, z3.ForAll(c + d, z3.Implies(pair, reach(c, d, t // 2))))

৭ · খেলা, পাজল আর planning — কোথায় PSPACE, কোথায় তার বাইরে

“জেলা দখল” খেলাটি বাজারঘরের ছোট মানচিত্রে চালানো যাক। নিচের JavaScript ব্লক GG-এর একই recursion চালায়, আর তিনটি শুরুর জেলা থেকে বিজয়ী, প্রথম জেতার চাল আর দুই পক্ষের সেরা খেলা ছাপে। রাস্তাগুলো বানানো, বাস্তব সড়ক-মানচিত্র নয়।

// Bazarghar "district claim" game = generalized geography on a small road graph
const G = {                           // one-way roads of a made-up delivery map
  Dhaka: ["Gazipur", "Narayanganj", "Manikganj"], Gazipur: ["Tangail", "Narsingdi"],
  Narayanganj: ["Narsingdi", "Munshiganj"], Manikganj: ["Tangail", "Munshiganj"],
  Tangail: ["Mymensingh"], Narsingdi: ["Mymensingh", "Gazipur"],
  Munshiganj: ["Narayanganj"], Mymensingh: ["Gazipur"],
};
const memo = new Map();
function win(u, used) {               // can the player who moves next (from u) force a win?
  const key = u + "|" + [...used].sort().join(",");
  if (memo.has(key)) return memo.get(key);
  let best = null;
  for (const v of G[u] || []) {
    if (used.has(v)) continue;
    used.add(v);
    const theyWin = win(v, used) !== null;
    used.delete(v);
    if (!theyWin) { best = v; break; }
  }
  memo.set(key, best);
  return best;
}
for (const start of ["Dhaka", "Manikganj", "Narayanganj"]) {
  memo.clear();
  let u = start, used = new Set([start]), line = [start], mover = 0;
  while (true) {                     // winner plays a winning move, loser its first legal move
    const v = win(u, used) ?? (G[u] || []).find((x) => !used.has(x));
    if (v === undefined) break;
    used.add(v); line.push(v); u = v; mover ^= 1;
  }
  const first = win(start, new Set([start]));
  console.log(`start ${start}: ${first ? "player 1 wins, first move " + first : "player 2 wins"}`);
  console.log(`  ${line.join(" -> ")}  (player ${mover + 1} is stuck)`);
  console.log(`  positions examined: ${memo.size}`);
}

আসল আউটপুট (ব্রাউজারের JavaScript):

start Dhaka: player 1 wins, first move Gazipur
  Dhaka -> Gazipur -> Tangail -> Mymensingh  (player 2 is stuck)
  positions examined: 6
start Manikganj: player 2 wins
  Manikganj -> Tangail -> Mymensingh -> Gazipur -> Narsingdi  (player 1 is stuck)
  positions examined: 11
start Narayanganj: player 1 wins, first move Munshiganj
  Narayanganj -> Munshiganj  (player 2 is stuck)
  positions examined: 6

Dhaka থেকে শুরু হলে প্রথম খেলোয়াড় Gazipur নিয়ে জেতেন: দ্বিতীয়জন Tangail বা Narsingdi যেখানেই যান, প্রথমজন Mymensingh নেন, আর সেখান থেকে একমাত্র রাস্তা Gazipur-এ, যা আগেই দখল হয়ে গেছে। Manikganj থেকে শুরু হলে দ্বিতীয় খেলোয়াড়ের winning strategy আছে। এত ছোট মানচিত্রে মাত্র কয়েকটি অবস্থা দেখতে হয়; কিন্তু অবস্থা মানে (বর্তমান জেলা, ব্যবহৃত জেলার set), তাই সাধারণ graph-এ তাদের সংখ্যা exponential হতে পারে, আর উপপাদ্য ৫.২ বলে এর চেয়ে মৌলিকভাবে ভালো algorithm থাকলে P = PSPACE হতো।

বাস্তবের খেলায় একটি সূক্ষ্মতা আছে। 8 × 8 দাবা একটি নির্দিষ্ট, সসীম খেলা; তার “জটিলতা” n-এর function হিসেবে মাপা যায় না। তাই গবেষকরা generalized সংস্করণ নেন: n × n বোর্ড, যার জন্য complexity অর্থবহ। মূল পার্থক্য খেলার দৈর্ঘ্যে। খেলা polynomial চালে শেষ হতে বাধ্য হলে বিজয়ী নির্ধারণ PSPACE-এ, অংশ ২-এর recursion দিয়ে। কিন্তু অবস্থা পুনরাবৃত্তির সুযোগ থাকলে খেলা exponential দীর্ঘ হতে পারে, আর তখন সমস্যা EXP-এ উঠে যেতে পারে।

সমস্যা (n × n বা সাধারণ রূপে)পরিচিত ফল (সূত্রে যেমন বলা হয়)
Generalized geographyPSPACE-complete (Schaefer ১৯৭৮); planar graph-এও (Lichtenstein–Sipser ১৯৮০)
HexPSPACE-complete (Reisch ১৯৮১)
Othello (Reversi)PSPACE-complete (Iwata–Kasai ১৯৯৪)
GoPSPACE-hard (Lichtenstein–Sipser ১৯৮০); জাপানি ko নিয়মে EXPTIME-complete (Robson ১৯৮৩)
দাবা, চেকার্সEXPTIME-complete (দাবা: Fraenkel–Lichtenstein ১৯৮১; চেকার্স: Robson ১৯৮৪)
Sokoban, Rush Hour (এক খেলোয়াড়ের পাজল)PSPACE-complete (Culberson ১৯৯৭; Flake–Baum ২০০২)
STRIPS-ধরনের planning (পরিকল্পনা আছে কি?)PSPACE-complete (Bylander ১৯৯৪)
NFA বা regex-এর universality আর equivalencePSPACE-complete (Meyer–Stockmeyer, ১৯৭০-এর দশকের শুরু)

টেবিলের ফলগুলো মূল প্রবন্ধের সারসংক্ষেপ হিসেবে সাহিত্যে যেভাবে বলা হয়, সেভাবে দেওয়া; প্রতিটি ফলের ঠিক সংস্করণ (কোন নিয়ম, কোন সীমা) মূল প্রবন্ধে আলাদা, তাই উদ্ধৃতির আগে মূল সূত্র দেখে নিন। এক খেলোয়াড়ের পাজল আর planning-এ প্রতিপক্ষ নেই, তবু PSPACE আসে: সমাধানের পথ exponential লম্বা হতে পারে, তাই “পথ আছে কি” প্রশ্নটি NP-এর ছোট certificate-এ ধরা পড়ে না; এটি আসলে একটি বিশাল configuration graph-এ reachability, যা Savitch-এর কৌশলে polynomial জায়গায় সমাধান হয়। বাজারঘরের গুদামে রোবটের তাক সরানোর পরিকল্পনা ঠিক এই শ্রেণির প্রশ্ন। NFA-র universality-র কথা পর্ব ২০-এ এসেছিল; সেখানে PSPACE-completeness-এর কারণ একই: NFA-র subset-গুলোর exponential বড় graph-এ খোঁজ।

যা প্রমাণিত

P ⊆ NP ⊆ PSPACE ⊆ EXP, আর P ⊊ EXP (time hierarchy, পর্ব ৬৭)। TQBF, GG, Hex, Sokoban PSPACE-complete.

যা অজানা

P = PSPACE কি না, NP = PSPACE কি না, PSPACE = EXP কি না। তবে P ⊊ EXP বলে এদের অন্তত একটি সমতা মিথ্যা।

বাস্তবে যা ঘটে

QBF solver আর খেলার engine কঠিন worst case সত্ত্বেও অনেক বাস্তব instance সামলায়; গ্যারান্টি নেই, তাই timeout আর সীমা রাখা জরুরি।

একটি ব্যবহারিক শিক্ষা

সমস্যায় “প্রতিপক্ষ যা-ই করুক” বা “সব পরিস্থিতিতে” এলে সন্দেহ করুন যে এটি NP-এর চেয়ে কঠিন, আর SAT-এর বদলে QBF বা খেলা-অনুসন্ধানের দিকে তাকান।

আরও গভীরে: Alternating Turing machine-এ প্রতিটি state ∃ বা ∀ ধরনের; Chandra, Kozen আর Stockmeyer (১৯৮১) দেখান, alternating polynomial সময় ঠিক PSPACE. পালাক্রমের সংখ্যা স্থির k-তে সীমিত করলে polynomial hierarchy-র k-তম স্তর পাওয়া যায় (পর্ব ৬৮), আর তাই PH ⊆ PSPACE. আরেকটি বিস্ময়: interactive proof-এর শ্রেণি IP ঠিক PSPACE (Shamir ১৯৯২, Lund–Fortnow–Karloff–Nisan-এর কাজের ওপর), অর্থাৎ একজন সন্দেহপ্রবণ polynomial যাচাইকারী এলোমেলো প্রশ্ন করে TQBF-এর সত্যতা যাচাই করতে পারেন (পর্ব ৭৪)।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • TQBF সংজ্ঞায়িত করুন, আর SAT-এর সঙ্গে সম্পর্ক বলুন। সত্য fully quantified Boolean সূত্রের language; সব quantifier ∃ হলে তা SAT, তাই SAT ≤p TQBF.
  • TQBF ∈ PSPACE কেন? প্রতি quantifier-এ একটি recursion frame, দুই মান পরপর চেষ্টা, জায়গা পুনর্ব্যবহার: O(n) জায়গা।
  • Hardness প্রমাণে ∀ কেন লাগে? ∃m [φt/2 ∧ φt/2] প্রতি স্তরে আকার দ্বিগুণ করে; ∀(c3, c4)-এ একটি নকল দুই জোড়ায় ব্যবহার করলে আকার O(n2k).
  • PSPACE-complete-এ reduction polynomial সময়ের কেন? polynomial জায়গার reduction নিজেই সমস্যা সমাধান করে ফেলতে পারে, তখন সংজ্ঞাটি অর্থহীন হয়।
  • GG-তে diamond কী করে? একটি চলকের মান বাছাই: পাশের node ব্যবহৃত হয়ে মানটি “মনে রাখে”, আর তিন চালের diamond পালা বদলে ∃/∀ মেলায়।

৮ · AI-এর যুগে TQBF আর PSPACE নিয়ে কাজ

AI assistant এই বিষয়ে কিছু ভুল বারবার করে। Hardness প্রমাণে সরল CANYIELD-সূত্র লিখে তাকে polynomial বলে দেয়, ∀-কৌশল বাদ দিয়ে। Reduction-এর দিক উল্টায় (“TQBF-কে GG-তে reduce করে TQBF-এর কঠিনতা দেখালাম”)। Quantifier-এর ক্রম বদলালেও অর্থ একই ধরে নেয়, যা অংশ ১-এর উদাহরণেই ভুল প্রমাণিত। PSPACE-complete-এর সংজ্ঞায় polynomial জায়গার reduction বসায়। বলে বসে “দাবা PSPACE-complete” বা “Go-র জটিলতা মীমাংসিত”, শর্ত আর নিয়মের পার্থক্য ছাড়াই। আর সবচেয়ে গুরুতর: “P ≠ PSPACE প্রমাণিত” বা “PSPACE = EXP” জাতীয় দাবি, যা খোলা প্রশ্ন।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
সরল ∃m [φ ∧ φ] সূত্রকে polynomial বলাপ্রতি স্তরে নকল কয়টি, গুনুন; S(t) = 2S(t/2) + … হলে আকার t-এর সমানুপাতিক
Reduction উল্টো দিকেপরিচিত PSPACE-complete সমস্যা বাঁয়ে আছে কি না দেখুন: TQBF ≤p X দিয়ে X-এর কঠিনতা
Quantifier-এর ক্রমকে গুরুত্বহীন ভাবাtqbf_eval.py বা z3-এ একই matrix দুই ক্রমে চালিয়ে দেখুন
Geography-র gadget-এ পালা বা তীর ভুলgeography.py-এর মতো reduction বানিয়ে ছোট সূত্রে TQBF-এর সঙ্গে মেলান
খেলার জটিলতা বা ইতিহাস বানানো, খোলা প্রশ্নকে মীমাংসিত বলাSipser, Arora–Barak বা মূল প্রবন্ধ দেখুন; শর্তসহ ফলটি মেলান

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞা, নির্মাণ, দুই দিকের প্রমাণ আর একটি যাচাই-কোড একসঙ্গে চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্বে TQBF আর PSPACE-completeness শিখছি (Sipser-এর রীতি)। ১. TQBF-এর সংজ্ঞা দাও, আর ∃x ∀y [(x ∨ y) ∧ (¬x ∨ ¬y)] আর ∀y ∃x [একই matrix]-এর মান হাতে হিসাব করে দেখাও। ২. TQBF ∈ PSPACE-এর প্রমাণ দাও, recursion-এর গভীরতা আর প্রতি স্তরের জায়গাসহ। ৩. PSPACE-hardness প্রমাণে φ(c1, c2, t)-এর সরল রূপ আর ∀-কৌশলের রূপ দুটিই লেখো, আর দুটির আকারের পুনরাবৃত্তি সূত্র সমাধান করো। ৪. একটি Python কোড দাও, যা ছোট QBF-এর মান recursive ভাবে বের করে আর একটি স্বাধীন পদ্ধতির (যেমন সব assignment-এর টেবিল) সঙ্গে মেলায়। ৫. কোনো খেলার জটিলতা বা ইতিহাস নিয়ে নিশ্চিত না হলে বলো, কোনো রেফারেন্স বানিয়ো না, আর কোনো খোলা প্রশ্নকে মীমাংসিত বোলো না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১CANYIELD algorithm হিসেবে polynomial জায়গায় চলে, অথচ তার হুবহু সূত্র-রূপ exponential বড়। algorithm আর সূত্রের মধ্যে এই পার্থক্য কোথা থেকে আসে, আর ∀ ঠিক কী “পুনর্ব্যবহার” করে?

একটি algorithm সময়ের সঙ্গে চলে। CANYIELD প্রথম অর্ধেক, c1 থেকে m, পুরো হিসাব করে, উত্তর “হ্যাঁ” পেলে সেই হিসাবের সব জায়গা মুছে দ্বিতীয় অর্ধেক, m থেকে c2, একই জায়গায় শুরু করে। দুই অর্ধেক কখনো একসঙ্গে মেমরিতে থাকে না। জায়গা তাই মাপে শুধু “একই মুহূর্তে কতটা লাগে”, আর recursion-এর প্রতিটি স্তর একটি configuration যোগ করে: মোট O(f(n)2), Savitch-এর ফল।

একটি সূত্র কিন্তু স্থির লেখা। সূত্রে প্রথম অর্ধেকের শর্ত লিখলে তা কাগজে থেকেই যায়; দ্বিতীয় অর্ধেকের শর্ত লিখতে আবার নতুন করে লিখতে হয়। সরল রূপে তাই প্রতিটি স্তর দুটি সম্পূর্ণ নকল চায়, আর log t স্তরে 2log t = t নকল। এটি tableau-র অবস্থার মতো: Cook–Levin-এ সময়ের প্রতিটি ধাপের জন্য এক সারি চলক লেগেছিল, কারণ সূত্রে “আগের ধাপ মুছে ফেলা” বলে কিছু নেই।

∀-কৌশল এখানে একটি ছদ্ম-পুনর্ব্যবহার আনে। ∀(c3, c4) বলে, ভেতরের একটিমাত্র নকল দুটি আলাদা ইনপুট-জোড়ায় সত্য হতে হবে। সূত্রের যিনি মূল্যায়ন করবেন, তিনি সেই নকল দুবার “চালাবেন”, একবার (c1, m) নিয়ে, একবার (m, c2) নিয়ে, ঠিক যেমন CANYIELD একই জায়গা দুবার ব্যবহার করে। অর্থাৎ পুনর্ব্যবহারের কাজটি সূত্র থেকে সরে মূল্যায়নকারীর ঘাড়ে যায়, আর অংশ ২-এর evaluator সেটি polynomial জায়গায় করতে পারে। এই কারণেই কৌশলটি SAT-এ কাজ করে না: শুধু ∃ দিয়ে “সব জোড়ায়” বলা যায় না। তাই এই প্রমাণ NP = PSPACE দেয় না।

প্রোগ্রামিংয়ের সঙ্গে মিলটি স্পষ্ট। একটি function একবার লিখে দুবার ডাকা আর তার শরীর দুবার কপি-পেস্ট করার পার্থক্যই এটা। কপি-পেস্টে কোডের আকার বাড়ে; ডাকলে বাড়ে না, কিন্তু চালানোর সময় দুবার খরচ হয়। ∀ এখানে “function call”-এর ভূমিকা নেয়।

মূল উপলব্ধি: জায়গা সময়ের সঙ্গে পুনর্ব্যবহার করা যায়, লেখা সূত্র যায় না; ∀ একটি নকলকে দুই জোড়ায় খাটিয়ে সেই পুনর্ব্যবহার সূত্রের ভেতরে ফিরিয়ে আনে।

প্র ০২NP-এর প্রতিটি “হ্যাঁ” উত্তরের একটি ছোট certificate আছে। TQBF-এর সত্য সূত্রের জন্য এমন ছোট প্রমাণ কেন সাধারণত পাওয়া যায় না? এটি NP বনাম PSPACE প্রশ্নের সঙ্গে কীভাবে যুক্ত?

SAT-এর একটি satisfying assignment কয়েকটি বিট: চলকপ্রতি একটি। কেউ দিলে আমরা দ্রুত মিলিয়ে নিই। কিন্তু ∃x ∀y ∃z ψ সত্য প্রমাণ করতে শুধু x-এর মান দিলে চলে না; দেখাতে হয় y-এর প্রতিটি মানের জন্য একটি z আছে। সাধারণভাবে E-এর strategy হলো A-এর আগের সব চাল থেকে পরের চালের একটি function. k চলকের পালাক্রমিক সূত্রে এমন function-এর টেবিল প্রায় 2k/2টি সারির হতে পারে। ছবি ৬৫.১-এর গাছে এটিই দেখা যায়: প্রতিটি ∀ node-এর দুটি সন্তানেরই প্রমাণ দরকার, তাই প্রমাণ নিজেই একটি exponential গাছ।

এর মানে এই নয় যে ছোট প্রমাণ অসম্ভব বলে প্রমাণিত। যদি প্রতিটি সত্য QBF-এর polynomial আকারের, polynomial সময়ে যাচাইযোগ্য প্রমাণ থাকত, তাহলে TQBF ∈ NP হতো, আর TQBF PSPACE-complete বলে NP = PSPACE হতো। বেশিরভাগ গবেষক মনে করেন NP ≠ PSPACE, কিন্তু এটি প্রমাণিত নয়; এমনকি P ≠ PSPACE-ও প্রমাণিত নয়। তাই “TQBF-এর ছোট certificate নেই” কথাটি একটি বিশ্বাস, উপপাদ্য নয়।

তবে একটি চমকপ্রদ মধ্যপথ আছে। ১৯৯০ সালের দিকে Lund, Fortnow, Karloff আর Nisan, তারপর Shamir দেখান যে IP = PSPACE: একজন সর্বশক্তিমান প্রমাণকারী আর একজন polynomial সময়ের, এলোমেলো প্রশ্ন করা যাচাইকারীর মধ্যে কথোপকথনে TQBF-এর সত্যতা বিশ্বাসযোগ্যভাবে প্রমাণ করা যায়। স্থির ছোট certificate না থাকলেও যাচাইকারী প্রশ্ন করে, এলোমেলোতা কাজে লাগিয়ে, প্রতারণা ধরে ফেলতে পারেন। পর্ব ৭৪-এ এই ধারণা বিস্তারিত আসবে। বাস্তবেও QBF solver-রা কখনো কখনো উত্তরের সঙ্গে “certificate” দেয়, যেমন E-এর strategy-কে একটি Boolean circuit হিসেবে; ছোট হলে এটি যাচাই করা যায়, কিন্তু সবসময় ছোট হবে এমন গ্যারান্টি নেই।

মূল উপলব্ধি: NP-এর প্রমাণ একটি পথ, PSPACE-এর প্রমাণ একটি strategy-গাছ; গাছটি ছোট করা যায় কি না, সেটিই NP বনাম PSPACE প্রশ্ন, যা এখনো খোলা।

প্র ০৩8 × 8 দাবা একটি সসীম খেলা, তবু দাবার “জটিলতা” নিয়ে গবেষণা হয়। n × n-এ সাধারণীকরণ কেন দরকার, আর generalized দাবা কেন PSPACE নয়, EXPTIME-complete?

Complexity তত্ত্ব input-এর দৈর্ঘ্য n বাড়লে সম্পদ কীভাবে বাড়ে তা মাপে। 8 × 8 দাবার অবস্থার সংখ্যা বিশাল হলেও সসীম, তাই তাত্ত্বিকভাবে একটি বিশাল কিন্তু ধ্রুবক আকারের টেবিল সব অবস্থার উত্তর দিতে পারে, আর এর “জটিলতা” O(1). প্রশ্নটি অর্থবহ করতে Fraenkel আর Lichtenstein (১৯৮১) n × n বোর্ডের একটি দাবা সংজ্ঞায়িত করেন, যেখানে বোর্ডের অবস্থা input, আর দেখান যে বিজয়ী নির্ধারণ EXPTIME-complete. Robson একই রকম ফল চেকার্স (১৯৮৪) আর জাপানি ko নিয়মের Go (১৯৮৩)-র জন্য দেন বলে সাহিত্যে উল্লেখ আছে।

PSPACE আর EXPTIME-এর পার্থক্য খেলার দৈর্ঘ্যে। Geography-তে প্রতিটি চালে একটি node চিরতরে ব্যবহৃত হয়, তাই খেলা |V| চালের মধ্যে শেষ হয়, আর DFS-এর গভীরতা polynomial. দাবায় ঘুঁটি আগে-পিছে যেতে পারে, অবস্থা ফিরে আসে, আর n × n বোর্ডে খেলা exponential দীর্ঘ হতে পারে। তখন recursion-এর গভীরতাই exponential, polynomial জায়গায় আঁটে না। আবার অবস্থার সংখ্যা exponential, তাই সব অবস্থার টেবিল exponential সময়ে ভরা যায়: EXPTIME-এ। Hardness-এর প্রমাণ আসে alternating যন্ত্রের সঙ্গে খেলার মিল থেকে: Chandra, Kozen আর Stockmeyer দেখান, polynomial জায়গার alternating যন্ত্র ঠিক EXPTIME-এর সমস্যাগুলো চেনে।

এর একটি পরিষ্কার পরিণতি আছে। P ⊊ EXP প্রমাণিত (time hierarchy, পর্ব ৬৭), তাই generalized দাবা P-তে নেই, এটা শর্তহীনভাবে প্রমাণিত, P বনাম NP-এর উত্তর ছাড়াই। খুব কম প্রাকৃতিক সমস্যার জন্য এমন শর্তহীন নিম্নসীমা জানা। অন্যদিকে Go-র কিছু নিয়মে (যেমন superko) সঠিক শ্রেণি নিয়ে প্রশ্ন খোলা আছে বলে পড়া যায়, আর generalized geography PSPACE-complete হলেও P-তে নেই, তা প্রমাণিত নয়।

বাস্তবে এর অর্থ সীমিত: 8 × 8 দাবায় engine-গুলো অসাধারণ খেলে, আর চেকার্সের মতো ছোট খেলা ২০০৭ সালে কম্পিউটারে পুরো সমাধান (দুই পক্ষ নিখুঁত খেললে ড্র) হয়েছে বলে জানা যায়। Complexity বলে n বাড়লে কী হয়; একটি নির্দিষ্ট বোর্ড নিয়ে কিছু বলে না।

মূল উপলব্ধি: খেলা polynomial চালে শেষ হলে PSPACE, অবস্থা ফিরে আসতে পারলে EXPTIME; আর complexity-র প্রশ্ন কেবল আকার বাড়ানো যায় এমন সাধারণ রূপেই অর্থবহ।

প্র ০৪Sokoban বা Rush Hour-এর মতো এক খেলোয়াড়ের পাজলে কোনো প্রতিপক্ষ নেই, তবু তারা PSPACE-complete. ∀ ছাড়া এই কঠিনতা কোথা থেকে আসে, আর তা বাজারঘরের গুদাম-রোবটের পরিকল্পনায় কী বলে?

NP-এর সঙ্গে তুলনা করুন। NP-এর প্রশ্নে সমাধান ছোট: polynomial দৈর্ঘ্যের certificate. Sokoban-এ সমাধান একটি চালের ক্রম, আর কিছু instance-এ সবচেয়ে ছোট সমাধানও exponential লম্বা হতে পারে বলে জানা যায়। তখন certificate হিসেবে পুরো ক্রম দেওয়া polynomial নয়। প্রশ্নটি আসলে একটি exponential বড় configuration graph-এ “শুরু থেকে লক্ষ্যে পথ আছে কি”, যা nondeterministic যন্ত্র polynomial জায়গায় একটি একটি চাল অনুমান করে করতে পারে: NPSPACE, আর Savitch-এর উপপাদ্যে NPSPACE = PSPACE.

কঠিনতার দিকে, এই পাজলগুলোতে বস্তু সরিয়ে Boolean “gadget” বানানো যায়: একটি বাক্স সরালে একটি দরজা খোলে, আরেকটি বন্ধ হয়, আর এভাবে polynomial জায়গার যন্ত্রের tape নকল করা যায়। Culberson ১৯৯৭ সালে Sokoban-এর জন্য, আর Flake ও Baum ২০০২ সালে Rush Hour-এর জন্য এমন প্রমাণ দেন বলে পরিচিত। পরে Hearn আর Demaine “nondeterministic constraint logic” নামে একটি সাধারণ কাঠামো দেন, যা দিয়ে অনেক স্লাইডিং পাজলের PSPACE-completeness একই ছাঁচে প্রমাণ করা যায়। ∀ এখানে লাগে না, কারণ hardness আসে দৈর্ঘ্য থেকে, প্রতিপক্ষ থেকে নয়।

AI-এর planning-এ একই ঘটনা। STRIPS-ধরনের planning-এ অবস্থা কয়েকটি Boolean তথ্যের সেট, আর কাজগুলো কিছু তথ্য যোগ বা মুছে দেয়; Bylander ১৯৯৪ সালে দেখান, “একটি পরিকল্পনা আছে কি” সাধারণভাবে PSPACE-complete. বাজারঘরের গুদামে কয়েকটি রোবট সরু করিডোরে তাক সরায়: কোন তাক কোন ক্রমে সরালে অর্ডারের তাক বেরিয়ে আসবে? তাক আর রোবট বাড়ালে এটি ঠিক এই শ্রেণির প্রশ্ন। প্রকৌশলের শিক্ষা: সাধারণ গ্যারান্টিযুক্ত দ্রুত algorithm আশা করা উচিত নয়; heuristic search, সীমিত গভীরতা, বা সমস্যার বিশেষ কাঠামো (যেমন সবসময় খালি জায়গা রাখা) ব্যবহার করতে হয়।

সবশেষে সূক্ষ্ম কথা: “পরিকল্পনার দৈর্ঘ্য ≤ k, k unary-তে দেওয়া” এমন সীমা দিলে certificate ছোট হয়ে প্রশ্ন NP-তে নেমে আসে। এজন্যই বাস্তবের অনেক planner সীমিত দৈর্ঘ্যের পরিকল্পনাকে SAT-এ এনকোড করে সমাধান করে।

মূল উপলব্ধি: PSPACE-এর কঠিনতা দুই উৎস থেকে আসতে পারে: প্রতিপক্ষের পালাক্রম (∀), অথবা exponential লম্বা সমাধান; পাজল আর planning দ্বিতীয়টির উদাহরণ।

প্র ০৫TQBF PSPACE-complete, অথচ বাস্তবের QBF solver আর খেলার AI প্রায়ই বড় instance সামলায়। Minimax, alpha-beta আর QBF solving-এর মধ্যে সম্পর্ক কী, আর তাত্ত্বিক কঠিনতা থেকে বাস্তবে কী আশা করা উচিত?

Minimax আসলে অংশ ২-এর evaluator-ই: ∃ node-এ সন্তানদের সর্বোচ্চ, ∀ node-এ সর্বনিম্ন, শুধু 0/1-এর বদলে স্কোর। আমাদের evaluator-এ ∃ একটি সত্য সন্তান পেলেই থামে, আর ∀ একটি মিথ্যা পেলেই; alpha-beta pruning এই একই ধারণার স্কোর-রূপ, যা অনেক শাখা না দেখেই বাদ দেয় (AI কোর্সের পর্ব ৪২-এ বিস্তারিত)। সবচেয়ে ভালো চাল-ক্রমে alpha-beta-র দেখা leaf-এর সংখ্যা মোটামুটি বর্গমূলে নেমে আসে বলে Knuth আর Moore-এর বিশ্লেষণে জানা যায়, তবু exponential থাকে।

QBF solver-রা আরও কৌশল যোগ করে। Search-ভিত্তিক solver (যেমন DepQBF) CDCL-এর মতো বিরোধ থেকে শেখে, আর “সমাধান” থেকেও শেখে: কোনো ∀ শাখা সত্য প্রমাণ হলে সেই কারণ মনে রাখে। অন্য পদ্ধতি ∀ চলক বাদ দিতে সূত্রকে প্রসারিত করে (expansion), আর কিছু solver প্রতি-উদাহরণ ধরে ধরে সূত্রের বিমূর্ত রূপ শোধরানোর পদ্ধতি নেয়, যার নাম counterexample-guided abstraction refinement. QBFEVAL নামের প্রতিযোগিতায় এদের তুলনা হয় বলে জানা যায়। Hardware যাচাই, কিছু synthesis আর planning সমস্যায় QBF এনকোডিং বাস্তবে ব্যবহৃত হয়, যদিও SAT solver-এর মতো ব্যাপক নয়।

তাত্ত্বিক কঠিনতা থেকে তিনটি বাস্তব প্রত্যাশা আসে। প্রথমত, worst case-এ exponential সময় ধরে নিন: কোনো solver সব instance দ্রুত মেটাবে না, যদি না P = PSPACE, যা প্রায় কেউ বিশ্বাস করেন না, যদিও প্রমাণিত নয়। দ্বিতীয়ত, কাঠামো কাজে লাগান: quantifier-এর পালাক্রম কম (যেমন শুধু ∃∀) হলে সমস্যা polynomial hierarchy-র নিচের স্তরে, যেখানে SAT-ভিত্তিক কৌশল প্রায়ই ভালো চলে। তৃতীয়ত, খেলার AI প্রায়ই নিখুঁত উত্তর চায় না, ভালো চাল চায়: সীমিত গভীরতা, মূল্যায়ন-function আর শেখা heuristic দিয়ে নিখুঁত সমাধান ছাড়াই শক্তিশালী খেলা সম্ভব, যেমন আধুনিক দাবা আর Go engine.

মূল উপলব্ধি: Minimax, alpha-beta আর QBF solving একই ∃/∀ গাছের ওপর ভিন্ন কৌশল; PSPACE-completeness বলে সব instance-এর গ্যারান্টি অসম্ভবের কাছাকাছি, কিন্তু কাঠামো আর আনুমানিক লক্ষ্যে বাস্তবে অনেক দূর যাওয়া যায়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। tqbf_eval.py আর geography.py ব্লক বদলে নিজের উত্তর যাচাইও করতে পারেন।

  1. Trace আর হিসাব: φ1 = ∀x ∃y [(x ∨ y) ∧ (¬x ∨ ¬y)] আর φ2 = ∃y ∀x [একই matrix]. অংশ ২-এর algorithm (আগে 0, দরকার হলে 1, উত্তর জানা হলেই থামা) কোন কোন leaf দেখবে, ক্রমানুসারে লিখুন। প্রতিটি সূত্রের মান কী, আর কয়টি leaf দেখা হলো?

    Matrix মানে y = ¬x (ঠিক একটি সত্য)। φ1: x = 0: y = 0 → (0 ∨ 0) মিথ্যা; y = 1 → সত্য, ∃y সত্য। x = 1: y = 0 → (1 ∨ 0), (0 ∨ 1) সত্য, ∃y সত্য। ∀x সত্য। দেখা leaf (x, y): (0, 0), (0, 1), (1, 0), মোট ৩টি; φ1 সত্য।

    φ2: y = 0: x = 0 → মিথ্যা, ∀x সঙ্গে সঙ্গে মিথ্যা। y = 1: x = 0 → (0 ∨ 1), (1 ∨ 0) সত্য; x = 1 → (¬x ∨ ¬y) = (0 ∨ 0) মিথ্যা, ∀x মিথ্যা। ∃y মিথ্যা। দেখা leaf (y, x): (0, 0), (1, 0), (1, 1), মোট ৩টি; φ2 মিথ্যা। scratch-এ tqbf_eval.py-এর evaluator-এ চালিয়ে একই ক্রম আর মান পেয়েছি। শিক্ষা: “প্রতিটি x-এর জন্য একটি y” আর “একটি y সব x-এর জন্য” আলাদা কথা।

  2. প্রমাণে ভুল খুঁজুন: একজন লিখেছেন: “TQBF ∈ NP. Certificate: প্রতিটি ∃-চলকের একটি মান। Verifier সেই মান বসিয়ে বাকি ∀-চলকগুলোর সব মানে matrix পরীক্ষা করে।” দুটি ভুল দেখান, আর ∃x ∀y ∃z ψ (এই পর্বের সূত্র) দিয়ে প্রথমটি দেখান।

    ভুল ১, একটি মান যথেষ্ট নয়: ∀-চলকের পরে আসা ∃-চলকের মান আগের ∀-চলকের ওপর নির্ভর করতে পারে। আমাদের φ-এ z = ¬y লাগে; z-এর জন্য একটি স্থির মান (0 বা 1) দিলে y-এর একটি মানে ψ মিথ্যা হয়। যেমন x = 1, z = 0: y = 0-এ (y ∨ z) = 0. তাই সত্য সূত্রেরও এমন certificate নেই, আর verifier ভুলভাবে বর্জন করবে। সঠিক “certificate” হলো একটি strategy-function, যা সাধারণত ছোট নয়।

    ভুল ২, verifier polynomial নয়: k′টি ∀-চলকের সব মান পরীক্ষা করতে 2k′ সময় লাগে। NP-এর verifier-কে polynomial সময়ে চলতে হয়।

    শুধু ∃ থাকলে (SAT) দুটি সমস্যাই মিলিয়ে যায়, তাই SAT ∈ NP. TQBF ∈ NP হলে NP = PSPACE হতো, যা খোলা প্রশ্ন; ভুল যুক্তি দিয়ে তা প্রমাণ হয় না।

  3. নির্মাণ: φ3 = ∃x ∀y ∃z [(x ∨ y) ∧ (¬y ∨ z)]-এর জন্য generalized geography graph Gφ3 বানান: node আর তীরের তালিকা দিন, আর node ও তীরের সংখ্যা বলুন। Player I কি জেতেন? একটি winning strategy বলুন।

    Diamond: প্রতিটি i = 1, 2, 3 (x, y, z)-এর জন্য Ti → Li, Ti → Ri, Li → Bi, Ri → Bi; আর B1 → T2, B2 → T3, B3 → c. Clause: c → C1, c → C2; C1 → C1:x, C1 → C1:y; C2 → C2:¬y, C2 → C2:z. ফেরা: C1:x → L1, C1:y → L2, C2:¬y → R2, C2:z → L3.

    গোনা: node ১২ + ১ + ২ + ৪ = ১৯টি; তীর ১২ (diamond) + ৩ (B থেকে) + ২ (c থেকে) + ৪ (clause থেকে literal) + ৪ (ফেরা) = ২৫টি।

    বিজয়ী: φ3 সত্য: x = 1 নিলে প্রথম clause সত্য, আর z = 1 নিলে দ্বিতীয়টি, y যা-ই হোক। তাই Player I জেতেন। কৌশল: T1 থেকে L1 (x = 1), T3 থেকে L3 (z = 1); শেষে A C1 বাছলে E literal x (L1 ব্যবহৃত), C2 বাছলে E literal z (L3 ব্যবহৃত)। scratch-এ geography.py-এর build আর solver দিয়ে ১৯টি node, ২৫টি তীর আর Player I-এর জয় মিলিয়েছি।

  4. প্রমাণ: (ক) প্রমাণ করুন: TQBF ∈ P হলে P = PSPACE. (খ) ∀-কৌশলের সূত্রের আকারের পুনরাবৃত্তি S(t) = S(t/2) + c·nk, S(1) = c·nk সমাধান করুন (t একটি 2-এর ঘাত), আর দেখান t = 2d·nk-এ আকার O(n2k). সরল রূপের S′(t) = 2S′(t/2) + c·nk-এর সঙ্গে তুলনা করুন।

    (ক) ১. P ⊆ PSPACE সবসময় সত্য: t(n) সময়ে যন্ত্র বড়জোর t(n)টি ঘর ছোঁয়। ২. A ∈ PSPACE নিন। উপপাদ্য ৩.২ থেকে A ≤p TQBF, একটি f দিয়ে, যার সময় p(n). ৩. TQBF-এর polynomial decider D ধরি, সময় q(n). A-এর decider: f(w) হিসাব, তারপর D. |f(w)| ≤ p(n), তাই মোট সময় p(n) + q(p(n)), polynomial. ৪. তাই A ∈ P, অর্থাৎ PSPACE ⊆ P, আর P = PSPACE. ∎ এটি দিকের নিয়ম: A ≤p B, B ∈ P ⇒ A ∈ P.

    (খ) t = 2j ধরি। প্রতিবার ভাগে একটি c·nk যোগ হয়, j বার: S(2j) = c·nk + j·c·nk = c·nk(j + 1). t = 2d·nk-এ j = d·nk, তাই S = c·nk(d·nk + 1) = O(n2k). সরল রূপে S′(2j) = 2j·c·nk + (2j − 1)·c·nk = (2t − 1)·c·nk: আকার t-এর সমানুপাতিক, এখানে 2d·nk-এর মতো exponential. forall_trick.py-এর সংখ্যাগুলো (১২০, ১৭৫, ২৩০, … প্রতি স্তরে +৫৫; সরল রূপে প্রায় দ্বিগুণ) ঠিক এই দুই আকৃতি দেখায়।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমTQBF PSPACE-complete, প্রমাণের এই ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Recursive evaluator দিয়ে দেখান TQBF ∈ PSPACE (একটি quantifier, একটি frame)
  2. A ∈ PSPACE নিন, আর একটি যন্ত্র M যা A-কে nk জায়গায় decide করে
  3. Configuration-কে O(nk) চলকে লিখে φc1,c2,1 বানান
  4. ∀-কৌশলে φc1,c2,t-কে φc3,c4,t/2-এর একটি নকল দিয়ে লিখুন
  5. t = 2d·nk-এ আকার O(n2k) আর সঠিকতা দেখান: w ∈ A ⇔ সূত্র সত্য

ψ = (x ∨ ¬y) ∧ (y ∨ z) ∧ (¬y ∨ ¬z). নিচের কোন সূত্রটি সত্য?

  • ∃z ∀y ∃x ψ
  • ∃x ∀y ∃z ψ
  • ∀x ∀y ∃z ψ
  • ∃x ∃z ∀y ψ

k চলকের একটি prenex QBF-এর মান recursive ভাবে (প্রথম quantifier সরিয়ে 0 আর 1 বসিয়ে) বের করলে সবচেয়ে খারাপ ক্ষেত্রে সময় আর জায়গা কেমন?

  • সময় exponential হতে পারে, জায়গা polynomial
  • সময় আর জায়গা দুটিই exponential
  • সময় আর জায়গা দুটিই polynomial
  • সময় polynomial, জায়গা exponential

TQBF-এর PSPACE-hardness প্রমাণে φc1,c2,t = ∃m [φc1,m,t/2 ∧ φm,c2,t/2] রূপটি কেন ব্যবহার করা যায় না?

  • এটি ভুল অর্থ দেয়: পথ না থাকলেও সত্য হতে পারে
  • ∃ quantifier TQBF-এ ব্যবহার করা যায় না
  • প্রতি স্তরে সূত্র দ্বিগুণ হয়, তাই আকার exponential
  • একটি configuration লিখতে exponential চলক লাগে

একটি সমস্যা B-কে PSPACE-complete বলতে কোনটি দেখাতে হয়? (A ≤p B মানে A-কে polynomial সময়ে B-তে reduce করা।)

  • B ∈ PSPACE আর B ≤p TQBF
  • B ∈ PSPACE আর PSPACE-এর প্রতিটি A polynomial জায়গার reduction-এ B-তে যায়
  • B ∈ PSPACE আর SAT ≤p B
  • B ∈ PSPACE আর TQBF ≤p B

Generalized geography: graph-এ তীর T1 → L1, T1 → R1, L1 → B1, R1 → B1, B1 → c, c → C1, C1 → P, P → L1. টোকেন T1-এ (ব্যবহৃত), Player I আগে চাল দেন, যিনি চাল দিতে পারেন না তিনি হারেন। Player I-এর সেরা প্রথম চাল কী, আর কে জেতেন?

  • R1; Player I জেতেন
  • L1; Player I জেতেন
  • যেকোনো চাল; Player II জেতেন
  • Player I-এর কোনো চাল নেই

নিচের কোন দাবিটি প্রমাণিত?

  • P ≠ PSPACE
  • NP = PSPACE
  • n × n বোর্ডের generalized দাবার বিজয়ী নির্ধারণ P-তে নেই
  • PSPACE = EXP

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. TQBF = সত্য fully quantified Boolean সূত্র। সব ∃ হলে SAT; quantifier-এর ক্রম বদলালে উত্তর বদলাতে পারে।
  2. TQBF ∈ PSPACE: প্রতি quantifier-এ একটি recursion frame, 0 আর 1 পরপর, জায়গা পুনর্ব্যবহার। সময় 2k পর্যন্ত, জায়গা O(n).
  3. TQBF PSPACE-hard (Stockmeyer–Meyer ১৯৭৩): reachability-সূত্র ∃m ∀(c3, c4) ∈ {(c1, m), (m, c2)} [φt/2]; সরল রূপ exponential, ∀-কৌশলে O(n2k).
  4. φ সত্য ⇔ formula game-এ E-এর winning strategy আছে। Generalized geography PSPACE-complete: চলকপ্রতি diamond, শেষে clause আর literal-এর বিচার।
  5. polynomial দৈর্ঘ্যের খেলা আর বহু পাজল/planning PSPACE-এ; n × n দাবা EXPTIME-complete. P বনাম PSPACE আর NP বনাম PSPACE খোলা।

পরের পর্বে: জায়গা আরও কমিয়ে logarithmic-এ: L আর NL, read-only input tape, directed graph-এ পথ খোঁজার NL-completeness, আর Immerman–Szelepcsényi-র বিস্ময়কর ফল NL = coNL.

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান