স্পেস কমপ্লেক্সিটি ও PSPACE

১ · স্পেস কমপ্লেক্সিটি — মেমোরি দিয়ে জটিলতা মাপা

M10 জুড়ে আমরা একটি টুরিং মেশিন সমস্যাটি সমাধান করতে কত সময় (ধাপ) নেয় তা মেপেছি। কিন্তু একটি TM-এর দ্বিতীয়, স্বতন্ত্র সম্পদ (resource) আছে — সেটি চলার সময় কতগুলো টেপ সেল স্পর্শ করে, অর্থাৎ কতটা স্পেস কমপ্লেক্সিটিSpace Complexityইনপুট দৈর্ঘ্য n-এর ফাংশন হিসেবে, worst-case-এ একটি TM কতগুলো টেপ সেল ব্যবহার করে — সময় যতই লাগুক না কেন, সম্পূর্ণ স্বতন্ত্র একটি মাপ। ব্যবহার করে। এই দুটো সম্পূর্ণ স্বতন্ত্র সম্পদ — একটি অ্যালগরিদম কম সময়ে কিন্তু বেশি মেমোরি ব্যবহার করে চলতে পারে, অথবা উল্টোটা। স্পেস কমপ্লেক্সিটি বিশেষভাবে গুরুত্বপূর্ণ কারণ মেমোরি পুনরায় ব্যবহারযোগ্য (একই সেল বারবার ওভাররাইট করা যায়) — তাই একটি অ্যালগরিদম কম স্পেসে অনেক বেশি সময় ধরে চলতে পারে, যা একটি গুরুত্বপূর্ণ, ভিন্ন ট্রেড-অফ তৈরি করে।

২ · ক্লাস PSPACE

$$PSPACE = \{L : L \text{ কোনো TM } O(n^k) \text{ স্পেসে ডিসাইড করে, কোনো ধ্রুবক } k \text{-এর জন্য}\}$$

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

একটি গুরুত্বপূর্ণ, প্রতিষ্ঠিত কন্টেইনমেন্ট সম্পর্ক (state করা, প্রমাণ ছাড়াই এই মুহূর্তে):

$$P \subseteq NP \subseteq PSPACE$$

৩ · স্যাভিচের থিওরেম — স্পেসে নন-ডিটারমিনিজমের প্রকৃত মূল্য

$NP \subseteq PSPACE$ কন্টেইনমেন্টের পেছনে আছে একটি সত্যিই গুরুত্বপূর্ণ, নামকরা ফলাফল:

এর মানে — স্পেসের জন্য, নন-ডিটারমিনিজম বাদ দিতে চাইলে সর্বোচ্চ একটি বর্গাকার (quadratic) ব্লো-আপ লাগে, যা $n^k$-এর জন্য এখনো $n^{2k}$ — অর্থাৎ এখনো পলিনমিয়াল। তাই NP (নন-ডিটারমিনিস্টিক পলিনমিয়াল টাইম)-এর প্রতিটি প্রবলেম, নন-ডিটারমিনিজম প্রতিস্থাপন করলেও, পলিনমিয়াল স্পেসে থেকেই যায় — এই কারণেই $NP \subseteq PSPACE$।

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

৪ · PSPACE-কমপ্লিট প্রবলেম — TQBF

L45-এর মতোই, PSPACE-এর মধ্যেও "সবচেয়ে কঠিন" প্রবলেম আছে — PSPACE-কমপ্লিট প্রবলেম, যেখানে PSPACE-এর প্রতিটি প্রবলেম পলিনমিয়াল-টাইমে রিডিউস হয়। এর ক্লাসিক উদাহরণ — TQBFTrue Quantified Boolean FormulaSAT-এর সম্প্রসারণ যেখানে প্রতিটি ভ্যারিয়েবলে একটি quantifier ($\exists$ বা $\forall$) যুক্ত থাকে — প্রশ্ন হলো পুরো কোয়ান্টিফায়েড ফর্মুলাটি সত্য কি না। — একটি বুলিয়ান ফর্মুলা যেখানে প্রতিটি ভ্যারিয়েবলের সামনে $\exists$ ("কোনো একটি মান আছে যাতে...") অথবা $\forall$ ("সব মানের জন্যই...") বসানো থাকে, যেমন $\exists x \forall y\, (x \vee \neg y)$। TQBF সরাসরি দুই-খেলোয়াড় গেম সমাধানের সাথে সম্পর্কিত (উল্লেখযোগ্য: অনেক বোর্ড-গেমের সাধারণীকৃত/n×n সংস্করণ PSPACE-কমপ্লিট) — এই বিমূর্ত ক্লাসকে পরিচিত কিছুর সাথে যুক্ত করে।

# P / NP / PSPACE তুলনা টেবিল, এবং একটি সত্যিকারের রিকার্সিভ TQBF-এভালুয়েটর

comparison = {
    "P":      {"resource": "পলিনমিয়াল সময়",      "known_containment": "P subseteq NP subseteq PSPACE",
               "canonical_complete_problem": "সার্কিট ভ্যালু প্রবলেম (P-কমপ্লিট)"},
    "NP":     {"resource": "নন-ডিটারমিনিস্টিক পলিনমিয়াল সময়", "known_containment": "P subseteq NP subseteq PSPACE",
               "canonical_complete_problem": "SAT (কুক-লেভিন, L46)"},
    "PSPACE": {"resource": "পলিনমিয়াল স্পেস (সময় সীমাহীন)", "known_containment": "NP subseteq PSPACE, স্যাভিচ থিওরেম দিয়ে",
               "canonical_complete_problem": "TQBF"},
}

print(f"{'ক্লাস':8s} | {'সম্পদ':30s} | {'কমপ্লিট প্রবলেম'}")
print("-" * 70)
for cls, info in comparison.items():
    print(f"{cls:8s} | {info['resource']:30s} | {info['canonical_complete_problem']}")

print()

# --- TQBF এভালুয়েটর -----------------------------------------------------
# কোয়ান্টিফায়েড ফর্মুলা রিপ্রেজেন্টেশন (নেস্টেড টাপল):
#   ('exists', var, subformula) | ('forall', var, subformula)
#   ম্যাট্রিক্স (কোয়ান্টিফায়ার-মুক্ত অংশ): ('var', name) | ('not', e) | ('and', e1, e2) | ('or', e1, e2)

def evaluate_matrix(expr, assignment):
    if expr[0] == 'var':
        return assignment[expr[1]]
    if expr[0] == 'not':
        return not evaluate_matrix(expr[1], assignment)
    if expr[0] == 'and':
        return evaluate_matrix(expr[1], assignment) and evaluate_matrix(expr[2], assignment)
    if expr[0] == 'or':
        return evaluate_matrix(expr[1], assignment) or evaluate_matrix(expr[2], assignment)
    raise ValueError("অজানা এক্সপ্রেশন")

def evaluate_tqbf(formula, assignment):
    if formula[0] == 'exists':
        _, var, sub = formula
        for val in (False, True):          # দুটোর যেকোনো একটি কাজ করলেই যথেষ্ট
            new_assign = dict(assignment); new_assign[var] = val
            if evaluate_tqbf(sub, new_assign):
                return True
        return False
    if formula[0] == 'forall':
        _, var, sub = formula
        for val in (False, True):          # দুটোই কাজ করতে হবে
            new_assign = dict(assignment); new_assign[var] = val
            if not evaluate_tqbf(sub, new_assign):
                return False
        return True
    return evaluate_matrix(formula, assignment)

# উদাহরণ ১: for all x, exists y : (x XOR y) -- হাতে-যাচাই: x=T হলে y=F কাজ করে, x=F হলে y=T কাজ করে -> সবসময় True
xor_expr = ('or',
            ('and', ('var', 'x'), ('not', ('var', 'y'))),
            ('and', ('not', ('var', 'x')), ('var', 'y')))
formula1 = ('forall', 'x', ('exists', 'y', xor_expr))
print("∀x ∃y (x XOR y) =", evaluate_tqbf(formula1, {}), " (প্রত্যাশিত: True)")

# উদাহরণ ২: exists x, for all y : (x AND y) -- হাতে-যাচাই: y=False হলে x∧y সবসময় False, তাই এমন x নেই -> False
and_expr = ('and', ('var', 'x'), ('var', 'y'))
formula2 = ('exists', 'x', ('forall', 'y', and_expr))
print("∃x ∀y (x AND y) =", evaluate_tqbf(formula2, {}), " (প্রত্যাশিত: False)")