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

Space complexity আর Savitch-এর theorem

Space Complexity and Savitch's Theorem — Measuring Space, SPACE and NSPACE, Configuration Counting, the CANYIELD Proof, PSPACE = NPSPACE and the Inclusion Chain

Taught in Bangla, this lesson defines the space used by a Turing machine and the classes SPACE, NSPACE, PSPACE and NPSPACE. It decides SAT in linear space, puts NFA non-universality in nondeterministic linear space, relates time and space by counting configurations, and proves Savitch's theorem through the CANYIELD midpoint recursion, so PSPACE = NPSPACE. In-page Python (Pyodide) runs SAT with one buffer and CANYIELD while measuring depth, and the lesson marks which links from L to EXP are proven strict.

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

  • Turing machine-এর space complexity-র সংজ্ঞা, আর SPACE, NSPACE, PSPACE, NPSPACE শ্রেণি
  • SAT, NFA-র non-universality আর ALBA-এর জায়গার হিসাব প্রমাণসহ
  • সময় আর জায়গার সম্পর্ক: TIME(t) ⊆ SPACE(t), NTIME(t) ⊆ SPACE(t), SPACE(f) ⊆ TIME(2O(f))
  • Savitch-এর theorem-এর CANYIELD প্রমাণ পুরোটা, আর PSPACE = NPSPACE
  • L থেকে EXP পর্যন্ত শ্রেণির শৃঙ্খলে কোনটি প্রমাণিত আর কোনটি খোলা প্রশ্ন

১ · জায়গাও একটি সম্পদ — tape-এর ঘর গোনা

মডিউল ১০-এ একটি সম্পদ মাপা হয়েছে: সময় (পর্ব ৫৭)। কিন্তু বাস্তবের প্রোগ্রাম শুধু ধীর হয়ে ব্যর্থ হয় না, মেমরি ফুরিয়েও ব্যর্থ হয়। বাজারঘরের রাতের সার্ভার যদি অর্ডার-লগের প্রতিটি লাইন মেমরিতে জমিয়ে রাখে, তাহলে লগ বড় হলে একদিন “out of memory” দেখা দেবে, যত সময়ই দেওয়া হোক। তাই computational complexity-র দ্বিতীয় বড় সম্পদ হলো জায়গা (space), অর্থাৎ গণনার সময় কতটা স্মৃতি লাগে।

স্কুলের স্লেট আর চকের কথা ভাবুন। অঙ্ক করতে করতে স্লেট ভরে গেলে আপনি মুছে আবার লেখেন। একটি স্লেটে সারা বছরের হাজারটা অঙ্ক করা যায়, কারণ জায়গা ফেরত পাওয়া যায়। কিন্তু অঙ্কে যে এক ঘণ্টা গেল, সেটি আর ফেরত আসে না। সময় শুধু খরচ হয়, জায়গা বারবার ব্যবহার হয়। এই পর্বের প্রায় প্রতিটি ফল এই সরল পার্থক্য থেকে আসে।

মাপার যন্ত্র আগের মতো এক-tape Turing machine (পর্ব ৪৩)। সময়ে আমরা ধাপ গুনেছিলাম; এখানে গুনব head কতগুলো আলাদা ঘর অন্তত একবার পড়েছে (scan করেছে)।

সংজ্ঞা ১.১ (Space complexity)

ধরুন M একটি deterministic Turing machine, যা প্রতিটি input-এ থামে (একটি decider). M-এর space complexity হলো function f: ℕ → ℕ, যেখানে

f(n) = max { w-এর ওপর চলার সময় M যতগুলো tape-ঘর scan করে : |w| = n }

M যদি একটি nondeterministic Turing machine হয়, যার প্রতিটি শাখা প্রতিটি input-এ থামে, তাহলে f(n) হলো দৈর্ঘ্য n-এর input-এ যেকোনো শাখায় scan করা ঘরের সর্বোচ্চ সংখ্যা।

সংজ্ঞাটি time complexity-র সংজ্ঞার হুবহু ছাঁচে গড়া: worst case, input-এর দৈর্ঘ্যের function, আর শুধু decider-এর জন্য। একটি পার্থক্য খেয়াল করুন। একই ঘর হাজারবার পড়লেও জায়গার হিসাবে সেটি একবারই গোনা হয়। সময়ের হিসাবে প্রতিটি পড়াই একটি ধাপ।

এই পর্বের রীতি: এক-tape model-এ input নিজেই n ঘর জুড়ে থাকে, আর যন্ত্রকে অন্তত input পড়তে হয়। তাই এখানে সবসময় f(n) ≥ n ধরা হবে। f(n) = log n-এর মতো n-এর চেয়ে ছোট জায়গা মাপতে আলাদা model লাগে: একটি শুধু-পড়ার (read-only) input tape আর আলাদা একটি work tape, যেখানে শুধু work tape-এর ঘর গোনা হয়। সেই model আর L, NL শ্রেণি পর্ব ৬৬-এ আসবে।

২ · SPACE আর NSPACE — প্রথম উদাহরণ

সংজ্ঞা ২.১ (Space complexity class)

f: ℕ → ℕ একটি function হলে

SPACE(f(n)) = { L : কোনো O(f(n)) জায়গার deterministic Turing machine L-কে decide করে }

NSPACE(f(n)) = { L : কোনো O(f(n)) জায়গার nondeterministic Turing machine L-কে decide করে }

PSPACE = ⋃k ≥ 1 SPACE(nk),   NPSPACE = ⋃k ≥ 1 NSPACE(nk)

এখানে “decide” মানে সব শাখা থামে। সময়ের শ্রেণির মতো এখানেও multi-tape বা এক-tape, যেটিই নিই, জায়গার শ্রেণি বদলায় না: k-tape যন্ত্রকে এক-tape যন্ত্র track-এ সাজিয়ে অনুকরণ করে, আর তাতে জায়গা শুধু একটি ধ্রুবক গুণ বাড়ে (পর্ব ৪৫)। সময়ে যে বর্গ-দাম ছিল, জায়গায় তা নেই।

২.১ SAT লিনিয়ার জায়গায়

SAT = {⟨φ⟩ : φ একটি satisfiable Boolean formula}. পর্ব ৫৮-এ দেখেছেন, SAT ∈ NP, আর কোনো polynomial-সময়ের algorithm জানা নেই। কিন্তু জায়গার হিসাবে SAT খুব সস্তা।

উপপাদ্য ২.২

SAT ∈ SPACE(n).

প্রমাণ। ধরুন φ-তে m-টি variable x1, …, xm, আর |⟨φ⟩| = n. যন্ত্র M1 = “input ⟨φ⟩-এর ওপর: ১. x1, …, xm-এর প্রতিটি মান-নির্ধারণের (assignment) জন্য: ২. সেই মানে φ-এর মান হিসাব করা। ৩. মান 1 হলে accept. ৪. কোনোটিতে না হলে reject.”

  1. সঠিকতা: M1 সব 2mটি মান-নির্ধারণ দেখে, তাই φ satisfiable ⇔ কোনো একটিতে মান 1 ⇔ M1 accept করে। — সব সম্ভাবনা গোনা হয়েছে
  2. জায়গা: বর্তমান মান-নির্ধারণ একটি m-bit সারি, যা একই ঘরগুলোতে binary counter-এর মতো এক বাড়িয়ে পরেরটিতে যায়। m ≤ n. — প্রতিটি variable input-এ অন্তত একবার লেখা
  3. φ-এর মান হিসাব করতে বাড়তি O(n) ঘর যথেষ্ট, আর হিসাব শেষে সেগুলো মুছে পরের মান-নির্ধারণে আবার ব্যবহার হয়। — জায়গা ফেরত আসে
  4. মোট জায়গা O(n) + O(n) = O(n). ∎

সময়ের হিসাব সম্পূর্ণ আলাদা: 2mটি মান-নির্ধারণ, প্রতিটিতে polynomial কাজ, তাই exponential. নিচের ব্লকে M1-এর ধারণাটি Python-এ। একমাত্র বড় তালিকা a, যার দৈর্ঘ্য m; পরের মান-নির্ধারণ বানানো হয় সেই তালিকাতেই binary-তে এক যোগ করে। পরীক্ষার জন্য নেওয়া হয়েছে একটি unsatisfiable formula φm = (x1 ∨ ⋯ ∨ xm) ∧ ¬x1 ∧ ⋯ ∧ ¬xm, যাতে যন্ত্রকে সব 2mটি মান দেখতেই হয়।

# SAT by brute force, reusing ONE assignment buffer.
# A clause is a list of literals: +i means x_i, -i means NOT x_i.
def sat_one_buffer(clauses, m):
    a = [0] * m                     # the only "big" memory: m cells
    tried = reads = 0
    while True:
        tried += 1
        ok = True
        for cl in clauses:          # evaluate phi under assignment a
            sat = False
            for lit in cl:
                reads += 1
                if a[abs(lit) - 1] == (lit > 0): sat = True; break
            if not sat: ok = False; break
        if ok: return True, tried, reads, len(a)
        i = 0                       # next assignment: binary +1 in place
        while i < m and a[i] == 1: a[i] = 0; i += 1
        if i == m: return False, tried, reads, len(a)
        a[i] = 1
def phi(m):                         # (x1 v ... v xm) and (not x1) ... (not xm)
    return [list(range(1, m + 1))] + [[-i] for i in range(1, m + 1)]
small = [[1, 2], [-1, 3], [-2, -3]]   # satisfiable: x1=0, x2=1, x3=0
print("small formula:", sat_one_buffer(small, 3))
print(" m  satisfiable  tried   literal reads  buffer cells")
for m in (4, 8, 12, 16):
    ok, tried, reads, cells = sat_one_buffer(phi(m), m)
    print(f"{m:2}  {str(ok):11} {tried:6} {reads:14,} {cells:6}")

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

small formula: (True, 3, 10, 3)
 m  satisfiable  tried   literal reads  buffer cells
 4  False           16             56      4
 8  False          256          1,012      8
12  False         4096         16,368     12
16  False        65536        262,124     16

প্রথম লাইন: ছোট formula (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) তৃতীয় মান-নির্ধারণে (x1 = 0, x2 = 1, x3 = 0) সত্য হয়, ১০টি literal পড়ার পরে। সারণিতে প্রতি চারটি variable বাড়লে চেষ্টা ১৬ গুণ হয় (16 থেকে 65,536), literal পড়া-ও প্রায় তা-ই। কিন্তু শেষ কলামটি দেখুন: জায়গা শুধু m ঘর, 4 থেকে 16, রৈখিক। একই স্লেট ৬৫,৫৩৬ বার মুছে লেখা হয়েছে। Python-এর নিজের মেমরি-খরচ এখানে মাপা হয়নি; তালিকার দৈর্ঘ্যই Turing machine-এর ঘরের প্রতীক।

২.২ NFA-র universality-র complement — nondeterministic linear জায়গায়

দ্বিতীয় উদাহরণটি nondeterminism-এর জোর দেখায়। পর্ব ২০-এ universality problem দেখেছেন:

ALLNFA = { ⟨A⟩ : A একটি NFA আর L(A) = Σ∗ }

এর complement-কে এখানে NOTALLNFA লিখব: যেসব NFA অন্তত একটি string প্রত্যাখ্যান করে। বাজারঘরের ভাষায়: কুপন-কোড যাচাইয়ের একটি NFA কি এমন কোনো কোড বাদ দেয়, যা দেওয়ার কথা নয়?

উপপাদ্য ২.৩ (Sipser-এর উদাহরণের অনুসরণে)

NOTALLNFA ∈ NSPACE(n).

প্রমাণ। ধরুন A-র state q-টি; q ≤ n. Nondeterministic যন্ত্র N = “input ⟨A⟩-এর ওপর: ১. A-র শুরুর state-এ (তার ε-closure-সহ) একটি চিহ্ন বসানো। ২. নিচের কাজ 2q বার: যদি কোনো চিহ্নিত state accept state না হয়, accept; নইলে nondeterministically একটি চিহ্ন a ∈ Σ বেছে নিয়ে চিহ্নগুলো a পড়ার পরের state-গুলোতে সরানো। ৩. reject.”

  1. চিহ্নিত state-গুলো মিলে ঠিক সেই subset, যেখানে A এ পর্যন্ত অনুমান করা string পড়ার পর থাকতে পারে (পর্ব ১০-এর subset construction-এর একটি state). কোনো চিহ্নিত state accept না হলে সেই string A প্রত্যাখ্যান করে। — NFA-র গ্রহণের নিয়ম
  2. L(A) ≠ Σ∗ হলে একটি সবচেয়ে ছোট প্রত্যাখ্যাত string s আছে। s পড়ার পথে subset-গুলো সব আলাদা; কোনোটি দুবার এলে মাঝের অংশ কেটে আরও ছোট প্রত্যাখ্যাত string পাওয়া যেত। subset আছে 2qটি, তাই |s| < 2q, আর N-এর একটি শাখা ঠিক s-এর চিহ্নগুলো অনুমান করে accept করে। — pigeonhole
  3. L(A) = Σ∗ হলে কোনো শাখাই প্রত্যাখ্যাত string পায় না; 2q বারের পরে সব শাখা reject করে। তাই প্রতিটি শাখা থামে, আর N একটি decider. — counter-এর সীমা
  4. জায়গা: চিহ্ন q bit, আর 2q পর্যন্ত গোনার counter q + 1 bit. মোট O(q) = O(n). অনুমান করা string কোথাও লেখা হয় না, শুধু বর্তমান subset. ∎

লক্ষ করুন, subset construction পুরো DFA বানাতে চাইলে 2qটি subset একসঙ্গে রাখত; N রাখে মাত্র একটি। নিচের ব্লক একটি একক-অক্ষরের (Σ = {a}) NFA-তে এই হাঁটা চালায়। NFA-টি শুরুর state s থেকে 2, 3, 5 আর 7 দৈর্ঘ্যের চারটি চক্রে ঢোকে; দৈর্ঘ্য p-এর চক্রের শেষ state ছাড়া সব accept. তাই ak প্রত্যাখ্যাত ঠিক তখন, যখন প্রতিটি p-র জন্য k mod p = p − 1, অর্থাৎ k + 1 সংখ্যাটি 2 · 3 · 5 · 7 = 210 দিয়ে বিভাজ্য। Σ-তে একটিই অক্ষর, তাই এখানে “অনুমান” একটিই পথ।

# Is L(A) != {a}*?  Walk the subset of current states, one symbol at a time.
from math import prod
P = (2, 3, 5, 7)                   # one cycle per prime p
start = "s"                        # accepting; on 'a' enter every cycle
states = [start] + [(p, i) for p in P for i in range(p)]
def step(S):                       # the NFA's move on symbol 'a'
    T = set()
    for q in S:
        if q == start: T |= {(p, 1 % p) for p in P}
        else: p, i = q; T.add((p, (i + 1) % p))
    return frozenset(T)
def accepting(S):                  # (p, i) accepts unless i == p - 1
    return any(q == start or q[1] != q[0] - 1 for q in S)
q = len(states)
S, n, peak = frozenset({start}), 0, 0
while accepting(S) and n < 2 ** q:   # counter bound: 2^q subsets
    S, n = step(S), n + 1
    peak = max(peak, len(S))
print("states q =", q, "| rejected string found:", not accepting(S))
print("shortest rejected length n =", n, "| lcm(P) - 1 =", prod(P) - 1)
print("memory: one subset =", q, "bits, counter =", (2 ** q).bit_length(),
      "bits | largest subset size seen:", peak)
S, defn = frozenset({start}), []       # compare with the arithmetic definition
for k in range(400):                   # a^k in L  <=>  k = 0 or k mod p != p-1 for some p
    defn.append(accepting(S) == (k == 0 or any(k % p != p - 1 for p in P)))
    S = step(S)
print("NFA = definition for k < 400:", all(defn),
      "| rejected k < 400:", [k for k in range(400) if all(k % p == p - 1 for p in P)])

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

states q = 18 | rejected string found: True
shortest rejected length n = 209 | lcm(P) - 1 = 209
memory: one subset = 18 bits, counter = 19 bits | largest subset size seen: 4
NFA = definition for k < 400: True | rejected k < 400: [209]

NFA-র state ১৮টি (s আর 2 + 3 + 5 + 7 = 17টি চক্র-state). সবচেয়ে ছোট প্রত্যাখ্যাত string a209, অর্থাৎ ২০৯টি অক্ষর অনুমান করতে হয়েছে, অথচ যেকোনো মুহূর্তে মনে রাখা হয়েছে শুধু একটি subset (১৮ bit) আর একটি counter (১৯ bit). সবচেয়ে বড় subset-এ ছিল মাত্র ৪টি state, প্রতিটি চক্রে একটি। শেষ লাইনে NFA-র উত্তর ৪০০-র কম প্রতিটি k-তে গাণিতিক সংজ্ঞার সঙ্গে মেলানো হয়েছে: ঠিক একটি দৈর্ঘ্য, ২০৯, প্রত্যাখ্যাত। চক্রের সংখ্যা বাড়ালে state যোগফলের মতো বাড়ে, কিন্তু সবচেয়ে ছোট প্রত্যাখ্যাত string গুণফলের মতো; তাই string-টি লিখে রাখার পদ্ধতি দ্রুত অচল হয়, subset-হাঁটা চলে।

NOTALLNFA NP-তে আছে কি না, জানা নেই: সবচেয়ে ছোট প্রত্যাখ্যাত string exponential লম্বা হতে পারে, তাই সেটি polynomial certificate হতে পারে না। আসলে ALLNFA PSPACE-complete (পর্ব ২০-এ বলা Meyer–Stockmeyer-এর ফল), তাই এটি NP-তে বা coNP-তে থাকলে বড় কোনো অপ্রত্যাশিত সমতা প্রমাণ হতো। অংশ ৬-এ দেখবেন, Savitch-এর theorem দিয়ে এটিকে deterministic জায়গায় আনা যায়।

৩ · জায়গা ফেরত আসে, সময় আসে না — সময় থেকে জায়গা

প্রথম সম্পর্কটি প্রায় স্পষ্ট: যন্ত্র এক ধাপে বড়জোর একটি নতুন ঘরে যায়।

উপপাদ্য ৩.১

t(n) ≥ n হলে TIME(t(n)) ⊆ SPACE(t(n)). বিশেষত P ⊆ PSPACE.

প্রমাণ। t(n) ধাপে head বড়জোর t(n) বার সরে, তাই প্রথম ঘর থেকে শুরু করে বড়জোর t(n) + 1টি ঘর scan করে। t(n) + 1 = O(t(n)). ∎

দ্বিতীয় সম্পর্কটি বেশি আকর্ষণীয়, কারণ এখানে nondeterminism আছে। পর্ব ৪৬-এ NTM-কে deterministic যন্ত্রে অনুকরণ করতে computation tree-র সব শাখা খোঁজা হয়েছিল। সময়ে এর দাম exponential. কিন্তু জায়গায়?

উপপাদ্য ৩.২

t(n) ≥ n হলে, আর t(n) যদি O(t(n)) জায়গায় হিসাব করা যায়, তাহলে NTIME(t(n)) ⊆ SPACE(t(n)). বিশেষত NP ⊆ PSPACE.

প্রমাণ। ধরুন N একটি t(n)-সময়ের NTM, আর প্রতিটি ধাপে তার সামনে বড়জোর b-টি বিকল্প। প্রতিটি শাখাকে {1, …, b}-এর ওপর দৈর্ঘ্য t(n)-এর একটি string r দিয়ে চেনা যায়: “ধাপ i-তে ri-তম বিকল্প নাও”। তিন-tape deterministic যন্ত্র M:

  1. Tape ৩-এ r-কে 11⋯1 দিয়ে শুরু করা, তারপর প্রতিবার lexicographic ক্রমে পরের string-এ বদলানো (একই ঘরে)। — r-এর দৈর্ঘ্য t(n), তাই O(t(n)) ঘর
  2. প্রতিটি r-এর জন্য tape ২ মুছে তাতে w কপি করা, আর r অনুসারে N-এর একটি শাখা t(n) ধাপ পর্যন্ত চালানো। শাখা accept করলে M accept করে। — tape ২-এ শাখা t(n) ধাপে বড়জোর t(n) + 1 ঘর ছোঁয়
  3. সব r শেষ হলে reject. সঠিকতা: N w গ্রহণ করে ⇔ কোনো শাখা accept করে ⇔ কোনো r-এ M accept করে। — প্রতিটি শাখা কোনো r দিয়ে চেনা
  4. জায়গা: tape ১-এ w (n ≤ t(n)), tape ২ আর ৩-এ O(t(n)). প্রতিটি নতুন r-এর জন্য tape ২ মুছে আবার ব্যবহার হয়। k-tape থেকে এক-tape-এ গেলে জায়গা ধ্রুবক গুণ বাড়ে, তাই মোট O(t(n)). ∎

M-এর সময় প্রায় bt(n) · t(n), exponential; কিন্তু জায়গা একটি শাখার সমান। এটিই এই পর্বের মূল সুর: সব শাখা একটির পর একটি চালালে সময় যোগ হয়, জায়গা হয় না। NP ⊆ PSPACE-এর আরেকটি পথ: SAT ∈ PSPACE, আর প্রতিটি NP সমস্যা polynomial সময়ে SAT-এ নামে (পর্ব ৫৯, পর্ব ৬০); polynomial সময়ের reduction-এর output polynomial লম্বা, তাই সেটি তৈরি করে SAT-এর লিনিয়ার-জায়গার যন্ত্র চালালে মোট জায়গা polynomial.

৪ · Configuration গোনা — জায়গা থেকে সময়

উল্টো দিক: f(n) জায়গার যন্ত্র কতক্ষণ চলতে পারে? উত্তর আসে একটি গণনা থেকে। একটি configuration u q v যন্ত্রের পুরো তাৎক্ষণিক অবস্থা (পর্ব ৪৩): state, head-এর অবস্থান আর tape-এর লেখা। জায়গা সীমিত হলে configuration-ও সীমিত।

লেমা ৪.১ (Configuration গোনা)

M = (Q, Σ, Γ, δ, q0, qaccept, qreject) যদি দৈর্ঘ্য n-এর input-এ বড়জোর f(n) ঘর ব্যবহার করে, তাহলে সেই input-এ M-এর সম্ভাব্য configuration বড়জোর

|Q| · f(n) · |Γ|f(n)

টি। f(n) ≥ 1 হলে এটি 2d · f(n)-এর বেশি নয়, যেখানে d একটি ধ্রুবক, যা শুধু |Q| আর |Γ|-এর ওপর নির্ভর করে। সংক্ষেপে: 2O(f(n)).

শেষ ধাপটি সরল হিসাব: |Q| · f · |Γ|f = 2log|Q| + log f + f · log|Γ|, আর log f ≤ f. নিচের stepper একটি ছোট যন্ত্রে গণনাটি ধাপে ধাপে করে।

1একটি config = state + head + tape2state বাছাই: |Q| উপায়3head-এর ঘর: f(n) উপায়4প্রতিটি ঘরে চিহ্ন: |Γ|^f(n) উপায়5মোট ≤ 2^(d·f(n))6এর বেশি ধাপ = কোনো config দুবার
যন্ত্র: Q = {q0, q1, q2}, Γ = {0, 1, ␣}, f = 4
উদাহরণ
এ পর্যন্ত গুণফল
2-এর ঘাতে
  1. একটি configuration. “01 q1 0␣” মানে tape-এ 010␣, state q1, আর head তৃতীয় ঘরের 0-এর ওপর। যন্ত্র ৪টি ঘর ব্যবহার করে, তাই প্রতিটি configuration এমন চার-ঘরের ছবি।
  2. State. তিনটি state, তাই প্রথম পছন্দের ৩টি উপায়।
  3. Head. Head চারটি ঘরের যেকোনোটিতে থাকতে পারে: ৩ × ৪ = ১২টি (state, head) জোড়া।
  4. Tape-এর লেখা. চারটি ঘরের প্রতিটিতে ৩টি চিহ্নের যেকোনোটি: 34 = 81টি লেখা। মোট 12 × 81 = 972টি configuration, যা 210 = 1024-এর কম।
  5. বড় f. একই যন্ত্র f(n) = n = 20 ঘর ব্যবহার করলে 3 · 20 · 320 ≈ 2.09 × 1011, প্রায় 237.6. সংখ্যাটি বিশাল, কিন্তু f-এর exponential-এর বেশি নয়: 2O(f).
  6. Pigeonhole. যন্ত্রটি deterministic আর ৯৭৩ ধাপ চললে ৯৭৪টি configuration দেখা হয়, তাই কোনো একটি দুবার এসেছে। Deterministic যন্ত্র একই configuration থেকে একই পথে চলে, তাই সে চিরকাল ঘুরবে। একটি decider তাই ৯৭২ ধাপের মধ্যেই থামে।
উপপাদ্য ৪.২

f(n) ≥ n হলে SPACE(f(n)) ⊆ TIME(2O(f(n))) আর NSPACE(f(n)) ⊆ TIME(2O(f(n))). বিশেষত PSPACE ⊆ NPSPACE ⊆ EXP.

প্রমাণ।

  1. Deterministic অংশ: M যদি f(n) জায়গার decider হয়, তার configuration বড়জোর 2d f(n)টি (লেমা ৪.১)। এর বেশি ধাপ চললে কোনো configuration পুনরাবৃত্ত হয়, তখন M চিরকাল ঘোরে, যা decider-এর সংজ্ঞার বিরোধী। তাই M-এর সময় ≤ 2d f(n). — stepper-এর pigeonhole যুক্তি
  2. Nondeterministic অংশ: N-এর input w-এর ওপর configuration graph বানানো: vertex = f(n) ঘরের configuration, তীর c → c′ যদি N-এর এক ধাপে c থেকে c′ আসা সম্ভব। vertex 2O(f(n))টি। — লেমা ৪.১
  3. N w গ্রহণ করে ⇔ শুরুর configuration থেকে কোনো accepting configuration-এ পথ আছে। এটি একটি reachability প্রশ্ন, যা চিহ্ন দেওয়া (BFS) দিয়ে graph-এর আকারের polynomial সময়ে হয় (পর্ব ৫৭-এর PATH). (2O(f))k = 2O(f). — PATH ∈ P
  4. Multi-tape-এ লেখা এই algorithm-কে এক-tape-এ আনলে সময় বর্গ হয়, তাও 2O(f(n)). f(n) = nk বসালে NPSPACE ⊆ ⋃k TIME(2O(nk)) = EXP. ∎

এই একই গণনা পর্ব ০৬-এর linear bounded automaton-এর পুরোনো প্রশ্নের উত্তর দেয়। ALBA = {⟨M, w⟩ : M একটি LBA আর M w গ্রহণ করে}. LBA-র tape input-এর সমান লম্বা, তাই দৈর্ঘ্য n-এর w-এ configuration বড়জোর q · n · gnটি (q = state-সংখ্যা, g = tape-চিহ্নের সংখ্যা)। Deterministic LBA হলে এতগুলো ধাপ অনুকরণ করে না থামলে loop নিশ্চিত, তাই reject; ধাপ গোনার counter লাগে log2(q n gn) bit, যা input ⟨M, w⟩-এর দৈর্ঘ্যের polynomial. Nondeterministic LBA হলে প্রশ্নটি configuration graph-এ reachability, আর পরের অংশের Savitch-এর theorem সেটি polynomial জায়গায় করে (configuration-এর আকারের বর্গ)। দুই ক্ষেত্রেই ALBA decidable আর PSPACE-এ, যদিও পর্ব ৫২-এ দেখেছেন, LBA-র emptiness প্রশ্ন ELBA undecidable. পার্থক্য হলো, membership-এ একটি নির্দিষ্ট w আছে, তাই configuration সসীম; emptiness-এ সব w নিয়ে প্রশ্ন।

৫ · Savitch-এর theorem — মাঝখানে ভেঙে nondeterminism সরানো

অংশ ৩-এ NTIME(t) ⊆ SPACE(t) পেয়েছি। একই কৌশল NSPACE-এ খাটে না: f(n) জায়গার NTM-এর একটি শাখা 2O(f(n)) ধাপ লম্বা হতে পারে, তাই শাখার পছন্দগুলো লিখে রাখতেই exponential জায়গা লাগে। অংশ ৪-এর BFS-ও খাটে না: সেটি দেখা হয়ে যাওয়া configuration-এর তালিকা রাখে, আবার 2O(f(n)) জায়গা। তাহলে কি nondeterministic জায়গা deterministic জায়গার চেয়ে exponential শক্তিশালী? সময়ের ক্ষেত্রে এই প্রশ্নই P বনাম NP, যা খোলা। জায়গার ক্ষেত্রে উত্তর জানা, আর তা আশ্চর্য রকম ভালো।

ধরুন আপনাকে জিজ্ঞাসা করা হলো: “ঢাকা থেকে চট্টগ্রাম বাসে বড়জোর ৮টি ধাপে যাওয়া যায় কি?” সব রুট লিখে রাখার মতো খাতা আপনার নেই, আছে শুধু একটি ছোট নোটপ্যাড। কৌশল: মাঝের একটি শহর m বেছে নিন, ধরা যাক কুমিল্লা। তারপর দুটি ছোট প্রশ্ন: “ঢাকা থেকে কুমিল্লা ৪ ধাপে?” আর “কুমিল্লা থেকে চট্টগ্রাম ৪ ধাপে?” প্রতিটি ছোট প্রশ্নও একইভাবে ভাঙুন। কুমিল্লায় কাজ না হলে নোটপ্যাড মুছে পরের শহর, ফেনী, চেষ্টা করুন। নোটপ্যাডে কখনো কয়েকটি স্তরের “এখান থেকে ওখানে, এত ধাপে” ছাড়া কিছু থাকে না। সময় লাগে অনেক, কারণ একই প্রশ্ন বারবার করা হয়; কিন্তু জায়গা খুব কম।

উপপাদ্য ৫.১ (Savitch-এর theorem, ১৯৭০)

যেকোনো function f: ℕ → ℕ, যেখানে f(n) ≥ log n, তার জন্য

NSPACE(f(n)) ⊆ SPACE(f(n)2)

এই পর্বের model-এ f(n) ≥ n; নিচের প্রমাণ সেখানে খাটে। f(n) ≥ log n-এর পূর্ণ রূপের জন্য পর্ব ৬৬-এর দুই-tape model লাগে, প্রমাণ একই; শর্ত f(n) ≥ log n কেন লাগে, তা প্রমাণের ৬ নম্বর ধাপে বলা আছে। মূল হাতিয়ার একটি recursive পদ্ধতি, CANYIELD(c1, c2, t): “c1 থেকে c2-তে বড়জোর t ধাপে যাওয়া যায় কি?” (t একটি 2-এর ঘাত)।

CANYIELD(c1, c2, t):
 1. t = 1 হলে: c1 = c2, অথবা N-এর নিয়মে c1 থেকে এক ধাপে c2?
    হ্যাঁ হলে accept, নইলে reject.
 2. t > 1 হলে, f(n) জায়গার প্রতিটি configuration cm-এর জন্য:
 3.     CANYIELD(c1, cm, t/2) চালানো
 4.     CANYIELD(cm, c2, t/2) চালানো
 5.     দুটিই accept করলে accept
 6. কোনো cm কাজ না করলে reject.

নিচের ছবিতে একটি ছোট configuration graph: আটটি configuration, যার c0 শুরুর আর c5 একমাত্র accepting configuration. c2-তে N-এর একটি nondeterministic পছন্দ আছে: c3-এর দিকে, অথবা rejecting configuration c6-এর দিকে। c7 থেকে c5-এ তীর আছে, কিন্তু c0 থেকে c7-এ পৌঁছানো যায় না। আটটি configuration, তাই t = 8 যথেষ্ট।

একটি NTM-এর ছোট configuration graph

c0 থেকে c5 পর্যন্ত সবুজ পথটি ৫ ধাপের। CANYIELD পথটি কোথাও লিখে রাখে না, শুধু মধ্যবিন্দু খোঁজে।

Configuration graph for CANYIELD: start c0, accept c5 c0 c1 c2 c3 c4 c5 c6 c7 শুরু accept reject অপ্রাপ্য
ছবি ৬৪.১ — c0 → c1 → c2 → c3 → c4 → c5 একটি accepting শাখা, দৈর্ঘ্য ৫. c2 → c6 একটি rejecting শাখা। হলুদ c7 থেকে accept-এ যাওয়া যায়, কিন্তু শুরু থেকে c7-এ নয়।

নিচের stepper CANYIELD(c0, c5, 8) চালায়। মধ্যবিন্দু চেষ্টা হয় c0, c1, … ক্রমে; প্রথম অর্ধেক ব্যর্থ হলে দ্বিতীয় অর্ধেক আর ডাকা হয় না। “Stack” সারিতে চলমান recursive ডাকগুলো (c1, c2, t) আকারে: প্রথম লাইনে সবচেয়ে বাইরের ডাক, শেষ লাইনে সবচেয়ে নতুন।

1t = 1: c1 = c2 বা এক ধাপ?2প্রতিটি মধ্যবিন্দু cm:3  CANYIELD(c1, cm, t/2)4  CANYIELD(cm, c2, t/2)5  দুটিই হ্যাঁ → accept6কোনো cm নয় → reject
Recursion-এর stack
stack
মধ্যবিন্দু
ফল
  1. মধ্যবিন্দু c0. CANYIELD(c0, c0, 4) সহজেই হ্যাঁ (c1 = c2). কিন্তু CANYIELD(c0, c5, 4) না, কারণ c0 থেকে c5 পৌঁছাতে ৫টি ধাপ লাগে। এই ব্যর্থ ডাকের ভেতরের সব frame শেষে মুছে যায়।
  2. মধ্যবিন্দু c1, প্রথম অর্ধেক. CANYIELD(c0, c1, 4) হ্যাঁ: c0 → c1 একটি তীর। একই জায়গা, নতুন প্রশ্ন।
  3. দ্বিতীয় অর্ধেক, c1 থেকে c5 ৪ ধাপে. এর ভেতরে মধ্যবিন্দু c0 (c1 থেকে c0-এ যাওয়া যায় না), c1 (তখন c1 থেকে c5 ২ ধাপে লাগবে, কিন্তু লাগে ৪), আর c2 (c2 থেকে c5 ৩ ধাপ, ২-এর বেশি) ব্যর্থ।
  4. মধ্যবিন্দু c3. CANYIELD(c1, c3, 2)-এর ভেতরে মধ্যবিন্দু c2: CANYIELD(c1, c2, 1) আর CANYIELD(c2, c3, 1), দুটিই সরাসরি তীর। এখন stack-এ ৪টি frame, t = 8, 4, 2, 1: এর চেয়ে গভীর কখনো হয় না।
  5. CANYIELD(c3, c5, 2). মধ্যবিন্দু c4: c3 → c4 আর c4 → c5, দুটিই তীর। তাই c1 থেকে c5 ৪ ধাপে যাওয়া যায়।
  6. ফল. ওপরের ডাক মধ্যবিন্দু c1 দিয়ে সফল: ACCEPT. পুরো পথ c0, …, c5 কোথাও একসঙ্গে লেখা হয়নি। মোট ১৭৩টি ডাক লেগেছে (পরের ব্লকে মাপা), কিন্তু একসঙ্গে বড়জোর ৪টি frame.

এবার পূর্ণ প্রমাণ।

প্রমাণ (উপপাদ্য ৫.১)। ধরুন N একটি NTM, যা A-কে f(n) জায়গায় decide করে। আমরা একটি deterministic যন্ত্র M বানাব, যা A-কে O(f(n)2) জায়গায় decide করে।

  1. N-কে সামান্য বদলে নেওয়া: accept করার আগে সে tape মুছে head বাঁ প্রান্তে নিয়ে যায়। তাহলে accepting configuration একটিই, caccept. শুরুর configuration cstart = q0w. — জায়গা বাড়ে না
  2. লেমা ৪.১ থেকে একটি ধ্রুবক d বাছা, যাতে দৈর্ঘ্য n-এর input-এ N-এর configuration ≤ 2d f(n)টি। M = “input w-এর ওপর: CANYIELD(cstart, caccept, 2d f(n))-এর ফল দেওয়া।” — configuration গোনা
  3. CANYIELD-এর সঠিকতা, t-এর ওপর আরোহ (t = 1, 2, 4, …): t = 1-এ সরাসরি পরীক্ষা। t > 1-এ, যদি c1 থেকে c2-তে দৈর্ঘ্য ℓ ≤ t-এর পথ থাকে, তার ⌊ℓ/2⌋-তম configuration cm নিলে দুই অংশের দৈর্ঘ্য ⌊ℓ/2⌋ আর ⌈ℓ/2⌉, দুটিই ≤ t/2, তাই আরোহ অনুমানে দুটি ডাকই accept. উল্টো দিকে, দুটি ডাক কোনো cm-এ accept করলে দুটি পথ জুড়ে দৈর্ঘ্য ≤ t-এর পথ পাওয়া যায়। — অর্ধেক করা
  4. M-এর সঠিকতা: N w গ্রহণ করে ⇔ cstart থেকে caccept-এ কোনো পথ আছে। সবচেয়ে ছোট এমন পথে কোনো configuration পুনরাবৃত্ত হয় না, তাই তার দৈর্ঘ্য configuration-সংখ্যার কম, ≤ 2d f(n). ধাপ ৩ থেকে CANYIELD ঠিক উত্তর দেয়। M সবসময় থামে, কারণ প্রতিটি ডাকে t অর্ধেক হয় আর মধ্যবিন্দু সসীম। — সবচেয়ে ছোট পথ
  5. জায়গা: প্রতিটি recursion-স্তর একটি frame রাখে: c1, c2, চলমান cm (প্রতিটি O(f(n)) ঘর) আর t (binary-তে d f(n) bit). এক frame = O(f(n)). প্রতিটি ডাকে t অর্ধেক হয়, তাই গভীরতা log2 2d f(n) + 1 = O(f(n)). ভেতরের ডাক শেষ হলে তার জায়গা ফেরত আসে। মোট O(f(n)) · O(f(n)) = O(f(n)2). t = 1-এর পরীক্ষা N-এর δ দেখে O(f(n)) জায়গায় হয়। — stack-এর উচ্চতা × frame-এর আকার
  6. দুটি সূক্ষ্ম বিষয়। এক, M-কে 2d f(n) লিখতে f(n) জানতে হয়। f(n) যদি O(f(n)) জায়গায় হিসাব করা যায়, সমস্যা নেই; নইলে f = 1, 2, 3, …-এর জন্য পরপর চেষ্টা করে দেখা যায় N সেই সীমা পেরোয় কি না (Sipser-এর বইয়ে বিস্তারিত)। দুই, পর্ব ৬৬-এর model-এ configuration-এ input-head-এর অবস্থানও থাকে, n রকম; তখন configuration-সংখ্যা n · 2O(f(n)), যা 2O(f(n)) হয় ঠিক তখন, যখন f(n) ≥ log n. এই কারণেই শর্তটি। ∎

এবার Python-এ CANYIELD চালিয়ে ডাকের সংখ্যা আর সর্বোচ্চ গভীরতা গোনা যাক, আর একই প্রশ্নে BFS কত বড় set রাখে, তা দেখা যাক। শেষ সারণিতে N-টি configuration-এর একটি সরল পথ c0 → c1 → ⋯ → cN−1, দুই দিকে প্রশ্ন: সামনে (পৌঁছানো যায়) আর পেছনে (যায় না)।

# CANYIELD (Savitch) on small configuration graphs.
from collections import deque
def run_canyield(G, c1, c2, t):
    configs, st = sorted(G), {"calls": 0, "depth": 0, "max": 0}
    def cy(c1, c2, t):              # can c1 reach c2 in at most t steps?
        st["calls"] += 1; st["depth"] += 1
        st["max"] = max(st["max"], st["depth"])
        if t == 1: ans = c1 == c2 or c2 in G[c1]
        else:                       # try every midpoint m, halve t
            ans = any(cy(c1, m, t // 2) and cy(m, c2, t // 2) for m in configs)
        st["depth"] -= 1
        return ans
    return cy(c1, c2, t), st["calls"], st["max"]
def bfs(G, s, t):                   # the time-friendly way: stores a set
    seen, q = {s}, deque([s])
    while q:
        for v in G[q.popleft()]:
            if v not in seen: seen.add(v); q.append(v)
    return t in seen, len(seen)
G = {0: [1], 1: [2], 2: [3, 6], 3: [4], 4: [5], 5: [], 6: [], 7: [5]}
print("c0 -> c5:", run_canyield(G, 0, 5, 8), "BFS:", bfs(G, 0, 5))
print("c0 -> c7:", run_canyield(G, 0, 7, 8), "BFS:", bfs(G, 0, 7))
print(" N  question    answer      calls  max depth  BFS set")
for N in (4, 8, 16):                # a path c0 -> c1 -> ... -> c(N-1)
    P = {i: [i + 1] if i < N - 1 else [] for i in range(N)}
    for a, b in ((0, N - 1), (N - 1, 0)):
        ans, calls, depth = run_canyield(P, a, b, N)
        print(f"{N:2}  {f'c{a} -> c{b}':11} {str(ans):6} {calls:10,} {depth:6} "
              f"{bfs(P, a, b)[1]:8}")

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

c0 -> c5: (True, 173, 4) BFS: (True, 7)
c0 -> c7: (False, 940, 4) BFS: (False, 7)
 N  question    answer      calls  max depth  BFS set
 4  c0 -> c3    True           20      3        4
 4  c3 -> c0    False          31      3        1
 8  c0 -> c7    True          443      4        8
 8  c7 -> c0    False         820      4        1
16  c0 -> c15   True       47,038      5       16
16  c15 -> c0   False      88,741      5        1

প্রথম লাইন stepper-এর হিসাব মেলায়: c0 থেকে c5 পৌঁছানো যায়, ১৭৩টি ডাকে, সর্বোচ্চ গভীরতা ৪. দ্বিতীয় লাইনে c7 অপ্রাপ্য, তাই সব মধ্যবিন্দু ব্যর্থ হয়ে ৯৪০টি ডাক লাগে। BFS-এর উত্তর একই, কিন্তু সে মনে রাখে ৭টি দেখা configuration-এর set. সারণিতে মূল নিদর্শন: N দ্বিগুণ হলে সর্বোচ্চ গভীরতা মাত্র এক বাড়ে (3, 4, 5 = log2 N + 1), অথচ ডাকের সংখ্যা লাফিয়ে বাড়ে (20 থেকে 47,038). পৌঁছানো গেলে BFS-এর set N-এর সমান হয়, অর্থাৎ configuration-সংখ্যার রৈখিক, যা আসল যন্ত্রে 2O(f(n)). একটি scratch চালনায় (সাধারণ CPython) N = 32-এ একই প্রোগ্রাম c0 → c31-এর জন্য প্রায় ২ কোটি ২৩ লক্ষ ডাক নিয়েছিল, গভীরতা মাত্র ৬; তাই সেটি এখানে রাখা হয়নি। এটিই Savitch-এর দাম: জায়গা বাঁচাতে প্রতিটি উপ-প্রশ্নের ফল ভুলে যাওয়া হয়, তাই একই প্রশ্ন বারবার হিসাব হয়। Memoization যোগ করলে সময় কমত, কিন্তু টেবিল রাখতে জায়গা আবার exponential হতো।

সময়ের হিসাব: প্রতিটি ডাক 2O(f)টি মধ্যবিন্দুর প্রতিটির জন্য দুটি ডাক করে, আর গভীরতা O(f), তাই M-এর সময় (2O(f))O(f) = 2O(f2). অংশ ৪-এর BFS-এর 2O(f)-এর চেয়ে অনেক খারাপ। জায়গা আর সময়ের মধ্যে এই আপস (trade-off) complexity-র একটি স্থায়ী বিষয়।

৬ · PSPACE = NPSPACE — আর তার ফল

অনুসিদ্ধান্ত ৬.১

PSPACE = NPSPACE.

প্রমাণ।

  1. PSPACE ⊆ NPSPACE: প্রতিটি deterministic Turing machine একটি NTM, যার প্রতিটি অবস্থায় একটিই বিকল্প। — সংজ্ঞা
  2. NPSPACE ⊆ PSPACE: L ∈ NSPACE(nk) হলে Savitch থেকে L ∈ SPACE(n2k), কারণ nk ≥ log n. — উপপাদ্য ৫.১
  3. n2k আবার একটি polynomial, তাই L ∈ PSPACE. দুই দিক মিলিয়ে সমতা। ∎

সময়ের সঙ্গে তুলনাটি চোখে পড়ার মতো। P বনাম NP প্রশ্নের উত্তর কেউ জানে না, আর nondeterminism সরাতে জানা সেরা সাধারণ পদ্ধতি exponential সময় নেয়। জায়গায় nondeterminism সরানোর দাম শুধু বর্গ, আর polynomial-এর বর্গ polynomial. তাই polynomial জায়গার স্তরে nondeterminism কোনো বাড়তি শক্তি দেয় না। এর কয়েকটি সরাসরি ফল:

  • NFA universality. NOTALLNFA ∈ NSPACE(n) ⊆ SPACE(n2) (উপপাদ্য ২.৩ + Savitch). Deterministic জায়গার শ্রেণি complement-এ বদ্ধ (accept আর reject অদলবদল), তাই ALLNFA ∈ SPACE(n2) ⊆ PSPACE.
  • Context-sensitive language. Context-sensitive language-এর শ্রেণি ঠিক NSPACE(n) (পর্ব ০৬: nondeterministic LBA, Kuroda ১৯৬৪)। তাই প্রতিটি CSL SPACE(n2)-এ।
  • PSPACE-hardness এক রকমই. PSPACE-complete সমস্যা (পর্ব ৬৫-এর TQBF, generalized geography) প্রমাণ করতে deterministic বা nondeterministic, যেকোনো polynomial-জায়গার যন্ত্র থেকে reduce করলেই চলে।

Walter Savitch উপপাদ্যটি প্রকাশ করেন ১৯৭০ সালে, “Relationships between nondeterministic and deterministic tape complexities” প্রবন্ধে (Journal of Computer and System Sciences). প্রবন্ধটি তাঁর Berkeley-র doctoral গবেষণা থেকে এসেছে বলে পরিচিত, যেখানে তাঁর তত্ত্বাবধায়ক ছিলেন Stephen Cook, পরে NP-completeness-এর জনক (পর্ব ৬০)। প্রায় অর্ধশতাব্দী পরেও কেউ Savitch-এর বর্গকে সাধারণভাবে উন্নত করতে পারেননি: NSPACE(f) ⊆ SPACE(f1.99)-এর মতো কিছু প্রমাণিত নয়, আবার বর্গই সর্বনিম্ন, তাও প্রমাণিত নয়।

Savitch-এর ফলটি linear জায়গায় কী বলে, তা লক্ষ করুন: NSPACE(n) ⊆ SPACE(n2), কিন্তু SPACE(n) = NSPACE(n) কি না অজানা। এটিই পর্ব ০৬-এ দেখা “প্রথম LBA সমস্যা” (Kuroda ১৯৬৪), যা আজও খোলা। “দ্বিতীয় LBA সমস্যা”, অর্থাৎ NSPACE(n) complement-এ বদ্ধ কি না, তার উত্তর “হ্যাঁ”, ১৯৮৭–৮৮ সালে Immerman আর Szelepcsényi-র উপপাদ্যে (পর্ব ৬৬)।

৭ · শ্রেণির শৃঙ্খল — L থেকে EXP, কী জানা আর কী অজানা

পর্ব ৬৬-এ দুটি ছোট শ্রেণি আসবে, এখানে শুধু নাম: L = SPACE(log n) আর NL = NSPACE(log n), read-only input tape-এর model-এ। এই পর্বের সব ফল মিলে একটি শৃঙ্খল পাওয়া যায়:

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXP

প্রতিটি ⊆-এর পেছনে কোন যুক্তি, আর কোনটির কঠোরতা জানা, তা নিচের stepper-এ।

1L ⊆ NL2NL ⊆ P3P ⊆ NP4NP ⊆ PSPACE5PSPACE = NPSPACE6NPSPACE ⊆ EXP
যুক্তি আর অবস্থা
কেন
কঠোর?
  1. L ⊆ NL. একটি deterministic যন্ত্র একটি NTM, যার প্রতিটি অবস্থায় একটিই বিকল্প। সমতা কি না, অর্থাৎ L = NL, খোলা প্রশ্ন।
  2. NL ⊆ P. O(log n) জায়গার যন্ত্রের configuration 2O(log n) = nO(1)টি, polynomial. তাই configuration graph-এ reachability (PATH) polynomial সময়ে। প্রমাণ পর্ব ৬৬-এ।
  3. P ⊆ NP. আবার সংজ্ঞা থেকেই (পর্ব ৫৮)। P = NP কি না, বিখ্যাত খোলা প্রশ্ন (পর্ব ৬৩)।
  4. NP ⊆ PSPACE. উপপাদ্য ৩.২: NTM-এর শাখাগুলো একটির পর একটি চালানো, জায়গা মুছে আবার ব্যবহার। NP = PSPACE কি না, অজানা।
  5. PSPACE = NPSPACE. Savitch-এর theorem. শৃঙ্খলের একমাত্র “=”, আর এটি প্রমাণিত।
  6. NPSPACE ⊆ EXP. উপপাদ্য ৪.২: nk জায়গার configuration 2O(nk)টি, তাই সেই graph-এ reachability exponential সময়ে। PSPACE = EXP কি না, অজানা।
  7. কী কঠোর, প্রমাণিত. Savitch থেকে NL ⊆ SPACE(log2 n), আর space hierarchy theorem থেকে SPACE(log2 n) ⊊ SPACE(n) ⊆ PSPACE; তাই NL ⊊ PSPACE. Time hierarchy theorem থেকে P ⊊ EXP. অর্থাৎ NL থেকে PSPACE-এর তিনটি কড়ার অন্তত একটি কঠোর, আর P থেকে EXP-এর তিনটির অন্তত একটি; কিন্তু কোনটি, তা কেউ জানে না।

শৃঙ্খলের মানচিত্র — প্রমাণিত আর অজানা

প্রতিটি বাক্স নিচেরটিকে ধারণ করে। মাঝের “⊆ অজানা” মানে কঠোর কি না কেউ জানে না। দুই পাশের বন্ধনী দুটি প্রমাণিত কঠোর ফল।

Inclusion chain L, NL, P, NP, PSPACE = NPSPACE, EXP with the two proven strict separations EXP PSPACE = NPSPACE NP P NL L n×n দাবা (সাধারণীকৃত) TQBF, NFA universality SAT, HAMPATH CYK, Euclid PATH {0ᵏ1ᵏ} (counter দিয়ে) ⊆ অজানা ⊆ অজানা ⊆ অজানা ⊆ অজানা ⊆ অজানা P ⊊ EXP · প্রমাণিত NL ⊊ PSPACE · প্রমাণিত
ছবি ৬৪.২ — শৃঙ্খলের একমাত্র প্রমাণিত সমতা PSPACE = NPSPACE (Savitch). প্রমাণিত কঠোর: P ⊊ EXP (বাঁ বন্ধনী) আর NL ⊊ PSPACE (ডান বন্ধনী)। পাঁচটি ⊆-এর প্রতিটি আলাদাভাবে কঠোর কি না, অজানা। সাধারণীকৃত দাবা EXP-complete বলে Fraenkel আর Lichtenstein-এর ১৯৮১ সালের কাজ থেকে পরিচিত; তাই সেটি প্রমাণিতভাবে P-র বাইরে।

বেশিরভাগ গবেষক মনে করেন, শৃঙ্খলের প্রতিটি ⊆ কঠোর, কিন্তু একটিও আলাদাভাবে প্রমাণিত নয়। সবচেয়ে কাছের উদাহরণ P বনাম PSPACE: P = PSPACE প্রমাণিত হলে P = NP-ও হতো (কারণ P ⊆ NP ⊆ PSPACE), তাই P ≠ PSPACE প্রমাণ করা P ≠ NP প্রমাণের চেয়ে সহজ হওয়ার কথা, তবু এটিও খোলা। বাজারঘরের ভাষায়: “একটি স্লেট আর অসীম ধৈর্য” (PSPACE) দিয়ে যা করা যায়, তা “দ্রুত” (P) করা যায় কি না, আমরা জানি না।

আরও গভীরে: Hopcroft, Paul আর Valiant ১৯৭৭ সালে দেখান বলে পরিচিত যে multi-tape যন্ত্রে TIME(t(n)) ⊆ SPACE(t(n)/log t(n)), অর্থাৎ জায়গা সময়ের চেয়ে কঠোরভাবে শক্তিশালী সম্পদ। ২০২৫ সালে Ryan Williams এই সীমাকে মোটামুটি √(t log t)-এ নামিয়েছেন বলে প্রকাশিত হয়েছে, যা জায়গা আর সময়ের সম্পর্কে বহু দশকের সবচেয়ে বড় অগ্রগতি হিসেবে আলোচিত; বিস্তারিত মূল প্রবন্ধে দেখুন। অন্যদিকে Savitch-এর বর্গ এখনো সেরা জানা সাধারণ সীমা, আর L = NL বা SPACE(n) = NSPACE(n) উন্মুক্ত।

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

  • Savitch-এর theorem বলুন আর প্রমাণের মূল ধারণা দিন। f(n) ≥ log n হলে NSPACE(f) ⊆ SPACE(f2); CANYIELD মধ্যবিন্দু ধরে t অর্ধেক করে, গভীরতা O(f) × frame O(f).
  • SAT ∈ PSPACE কেন? সব মান-নির্ধারণ একটি m-bit counter-এ একে একে, একই জায়গায়; SAT ∈ SPACE(n).
  • SPACE(f) ⊆ TIME(2O(f)) প্রমাণ করুন। Configuration ≤ |Q| f |Γ|f; decider কোনো configuration দুবার দেখে না।
  • PSPACE = NPSPACE কিন্তু P বনাম NP খোলা কেন? জায়গায় nondeterminism সরানোর দাম বর্গ, সময়ে জানা দাম exponential.
  • L থেকে EXP-এর কোন অন্তর্ভুক্তি কঠোর জানা? শুধু NL ⊊ PSPACE আর P ⊊ EXP (hierarchy theorem).

৮ · AI-এর যুগে space complexity

AI assistant এই বিষয়ে আত্মবিশ্বাসী উত্তর দেয়, কিন্তু কয়েকটি ভুল বারবার দেখা যায়: শর্ত বাদ দেওয়া, প্রমাণিত আর খোলা প্রশ্ন গুলিয়ে ফেলা, আর জায়গার হিসাবে recursion-এর stack ভুলে যাওয়া।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Savitch দেখায় NSPACE(f) = SPACE(f)” বা “L = NL প্রমাণিত”Savitch দেয় বর্গ, সমতা নয়; L বনাম NL খোলা। NL = coNL প্রমাণিত, এটি আলাদা কথা
Savitch-এর শর্ত f(n) ≥ log n বাদ দেওয়াপ্রমাণের configuration-গণনায় input-head-এর n অবস্থান কোথায় গেল, জিজ্ঞাসা করুন
Recursive algorithm-এর জায়গায় stack-এর গভীরতা না গোনাজায়গা = গভীরতা × frame-এর আকার; code চালিয়ে সর্বোচ্চ গভীরতা মাপুন
“P ⊊ PSPACE প্রমাণিত” বা “NP = PSPACE অজানা নয়”শৃঙ্খলে প্রমাণিত কঠোর শুধু NL ⊊ PSPACE আর P ⊊ EXP
NTIME(t) ⊆ SPACE(t)-এর যুক্তি NSPACE-এ খাটানোNSPACE-এর শাখা 2O(f) লম্বা হতে পারে; পছন্দের তালিকা রাখার জায়গা নেই
বানানো সাল বা রেফারেন্স (Savitch, Kuroda, Immerman)Sipser, Hopcroft–Motwani–Ullman বা Arora–Barak-এ নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণের প্রতিটি ধাপের জায়গার হিসাব আলাদা করে চাওয়া, আর একটি ছোট simulator চাওয়া, যা সর্বোচ্চ recursion-গভীরতা আর ডাকের সংখ্যা ছাপে, যাতে আপনি নিজে চালিয়ে মিলিয়ে নিতে পারেন।

আমি গণনার তত্ত্ব শিখছি, Savitch-এর theorem নিয়ে প্রশ্ন। ১. NSPACE(f(n)) ⊆ SPACE(f(n)^2) উপপাদ্যটি সব শর্তসহ লেখো। f(n) ≥ log n শর্তটি প্রমাণের কোন ধাপে লাগে, তা স্পষ্ট বলো। ২. CANYIELD(c1, c2, t)-এর সঠিকতার প্রমাণ t-এর ওপর আরোহ দিয়ে দাও, আর জায়গার হিসাব দাও: প্রতিটি frame-এ কী থাকে, গভীরতা কত। ৩. শুধু Python standard library দিয়ে একটি script দাও, যা একটি ছোট directed graph-এ CANYIELD চালায়, মোট ডাক আর সর্বোচ্চ গভীরতা ছাপে, আর BFS-এর উত্তরের সঙ্গে প্রতিটি জোড়া vertex-এ মেলায়। ৪. L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP-এর কোন অন্তর্ভুক্তি কঠোর বলে প্রমাণিত, আর কোনগুলো খোলা, আলাদা করে লেখো। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Nondeterminism সরাতে সময়ে exponential দাম জানা, অথচ জায়গায় শুধু বর্গ। এই অসমতার গভীর কারণ কী, আর Savitch-এর কৌশল সময়ে কেন একই সুবিধা দেয় না?

মূল কারণ এই পর্বের স্লেটের উপমা: জায়গা পুনর্ব্যবহারযোগ্য, সময় নয়। CANYIELD একটি প্রশ্নের উত্তর বের করে, তারপর সেই হিসাবের সব জায়গা ফেলে দেয়, আর পরের মধ্যবিন্দুর জন্য একই জায়গা ব্যবহার করে। ফলে মোট জায়গা নির্ভর করে শুধু একসঙ্গে কতগুলো উপ-প্রশ্ন “খোলা” থাকে তার ওপর, অর্থাৎ recursion-এর গভীরতার ওপর। গভীরতা লগারিদমিক, কারণ প্রতিবার পথের দৈর্ঘ্য অর্ধেক হয়।

সময়ের ক্ষেত্রে একই কৌশল বিপর্যয়। প্রতিটি স্তরে 2O(f)টি মধ্যবিন্দু, প্রতিটির জন্য দুটি ডাক, আর স্তর O(f)টি; মোট সময় 2O(f2). Polynomial সময়ের NTM-এর ক্ষেত্রে f হলো সময় নিজেই, তাই এটি সরাসরি BFS-এর 2O(t)-এর চেয়েও খারাপ। সময়ে কিছু “ফেরত” পাওয়া যায় না: একটি উপ-প্রশ্ন দুবার হিসাব করলে দুবারের সময়ই খরচ হয়।

আরেক দৃষ্টিকোণ: nondeterministic যন্ত্র একটি পথ “অনুমান” করে। জায়গার সীমায় পথ লম্বা হতে পারে, কিন্তু পথের প্রতিটি বিন্দু (configuration) ছোট। Savitch এই ছোটত্ব কাজে লাগায়: শুধু বিন্দু মনে রাখে, পথ নয়। সময়ের সীমায় পথ ছোট (polynomial), কিন্তু সম্ভাব্য পথের সংখ্যা exponential, আর কোনো পরিচিত কৌশল সব পথ না দেখে সঠিক পথ খুঁজে পায় না; এটিই P বনাম NP.

ইতিহাসেও এই পার্থক্য স্পষ্ট। Savitch ১৯৭০ সালে উপপাদ্যটি দেন, Cook-এর NP-completeness প্রবন্ধের (১৯৭১) প্রায় এক বছর আগে। জায়গার প্রশ্নের একটি সন্তোষজনক উত্তর তাই NP-র তত্ত্ব জন্মের আগেই ছিল, অথচ সময়ের প্রশ্ন পঞ্চাশ বছরেরও বেশি খোলা। তবু জায়গার ক্ষেত্রেও সব প্রশ্ন মীমাংসিত নয়: বর্গ কি কমানো যায়? L = NL? এই প্রশ্নগুলো খোলা।

মূল উপলব্ধি: জায়গা মুছে আবার ব্যবহার করা যায় বলে recursion-এর গভীরতাই জায়গার দাম ঠিক করে, তাই মধ্যবিন্দু-বিভাজন জায়গায় বর্গ দামে nondeterminism সরায়; সময়ে প্রতিটি পুনরাবৃত্তি নতুন খরচ, তাই একই কৌশল সেখানে কাজে আসে না।

প্র ০২“প্রথম LBA সমস্যা”, অর্থাৎ SPACE(n) = NSPACE(n)?, ১৯৬৪ থেকে খোলা। Savitch-এর theorem এটির সমাধান করে না কেন, আর দ্বিতীয় LBA সমস্যার সমাধান এ সম্পর্কে কী বলে?

S.-Y. Kuroda ১৯৬৪ সালে দেখান যে nondeterministic linear bounded automaton ঠিক context-sensitive language চেনে (পর্ব ০৬)। একই প্রবন্ধে তিনি দুটি প্রশ্ন রাখেন। প্রথমটি: deterministic LBA কি একই শ্রেণি চেনে? Complexity-র ভাষায়, SPACE(n) = NSPACE(n)? দ্বিতীয়টি: context-sensitive language-এর শ্রেণি কি complement-এ বদ্ধ?

Savitch-এর theorem প্রথম প্রশ্নে শুধু এটুকু বলে: NSPACE(n) ⊆ SPACE(n2). অর্থাৎ একটি nondeterministic LBA-কে deterministic যন্ত্রে অনুকরণ করা যায়, কিন্তু tape লাগবে n-এর বদলে n2. LBA-র সংজ্ঞায় tape-এর দৈর্ঘ্য ঠিক input-এর সমান (বা তার ধ্রুবক গুণ), তাই বর্গ জায়গা সেখানে অনুমোদিত নয়। CANYIELD-এর stack-এ O(n) গভীরতার প্রতিটি স্তরে O(n) ঘরের configuration রাখতে হয়, আর এই গুণফল এড়ানোর কোনো উপায় জানা নেই।

দ্বিতীয় প্রশ্নের উত্তর এসেছে ১৯৮৭–৮৮ সালে, Neil Immerman আর Róbert Szelepcsényi-র স্বাধীন কাজে: s(n) ≥ log n হলে NSPACE(s(n)) complement-এ বদ্ধ। কৌশলটি “inductive counting”: একটি nondeterministic যন্ত্র প্রথমে গোনে শুরু থেকে ঠিক কয়টি configuration-এ পৌঁছানো যায়, তারপর সেই সংখ্যা দিয়ে নিশ্চিত হয় যে কোনো accepting configuration-এ পৌঁছানো যায় না (পর্ব ৬৬)। এর একটি সরাসরি ফল: context-sensitive language complement-এ বদ্ধ।

লক্ষ করুন, প্রথম প্রশ্নের “হ্যাঁ” উত্তর দ্বিতীয়টির উত্তরও দিত, কারণ deterministic জায়গার শ্রেণি complement-এ স্পষ্টতই বদ্ধ। কিন্তু উল্টোটি সত্য নয়: NSPACE(n) = coNSPACE(n) প্রমাণিত হলেও SPACE(n) = NSPACE(n) অজানা রয়ে গেছে। একই ছবি log জায়গায়: NL = coNL প্রমাণিত, L = NL খোলা। Immerman আর Szelepcsényi এই কাজের জন্য ১৯৯৫ সালে Gödel Prize ভাগ করে পান বলে পরিচিত।

মূল উপলব্ধি: Savitch nondeterminism সরায় কিন্তু জায়গা বর্গ করে, যা LBA-র রৈখিক সীমায় অনুমোদিত নয়; complement-এর প্রশ্ন সমাধান হয়েছে, কিন্তু deterministic বনাম nondeterministic linear জায়গার প্রশ্ন ছয় দশক পরেও খোলা।

প্র ০৩CANYIELD ফল মনে রাখে না বলে একই প্রশ্ন বারবার হিসাব করে; memoization বা dynamic programming উল্টোটা করে। বাস্তবের software-এ জায়গা আর সময়ের এই আপস কোথায় কোথায় দেখা যায়?

Dynamic programming আর memoization-এর মূল কথা: একবার হিসাব করা উপ-প্রশ্নের ফল একটি টেবিলে রাখা, যাতে দ্বিতীয়বার হিসাব না লাগে (DSA কোর্সের পর্ব ৫২)। এতে সময় কমে, কিন্তু টেবিলের জায়গা লাগে। CANYIELD ঠিক উল্টো পথে যায়: কোনো ফল রাখে না, তাই জায়গা অতি সামান্য, কিন্তু একই উপ-প্রশ্ন exponential বার হিসাব হয়। অংশ ৫-এর ব্লকে N = 16-এ ৪৭ হাজারের বেশি ডাক লেগেছে, অথচ আলাদা উপ-প্রশ্ন (c1, c2, t) বড়জোর 16 · 16 · 5 = 1280টি। পুরো টেবিল রাখলে ডাক কমত, কিন্তু টেবিলের আকার configuration-সংখ্যার বর্গ, আসল যন্ত্রে 2O(f).

বাস্তবে এই আপস সর্বত্র। Deep learning-এ বড় network প্রশিক্ষণের সময় backpropagation-এর জন্য প্রতিটি স্তরের মধ্যবর্তী ফল রাখতে হয়; “gradient checkpointing” নামের কৌশলে কিছু স্তরের ফল ফেলে দিয়ে পরে আবার হিসাব করা হয়, যাতে মেমরি কমে আর সময় কিছুটা বাড়ে। ২০১৬ সালের একটি পরিচিত প্রবন্ধে (Chen ও সহকর্মীরা) n স্তরের network-এ প্রায় √n মেমরিতে এটি করার পদ্ধতি দেখানো হয়েছিল বলে পরিচিত। Database-এর query-তে hash join অনেক মেমরি নেয় কিন্তু দ্রুত, আর nested-loop join প্রায় মেমরি ছাড়াই চলে কিন্তু ধীর। ছোট embedded যন্ত্রে, যেমন একটি বাজার-স্কেলের microcontroller-এ, মেমরি এত কম যে টেবিলের বদলে বারবার হিসাবই একমাত্র পথ।

তত্ত্বেও এর গভীর রূপ আছে। Time-space trade-off lower bound-এর একটি গবেষণা-ধারা প্রমাণ করে যে কিছু সমস্যায় সময় আর জায়গার গুণফল একটি সীমার নিচে নামানো যায় না; যেমন সাজানো (sorting) বা element distinctness-এর জন্য কিছু model-এ এমন ফল জানা। আর অংশ ৭-এর “আরও গভীরে”-তে বলা TIME(t) ⊆ SPACE(t/log t)-এর মতো ফল দেখায়, জায়গা আসলেই সময়ের চেয়ে শক্তিশালী সম্পদ।

বাজারঘরের প্রকৌশলীর জন্য শিক্ষা: “এই হিসাবটি কি জমা রাখব, নাকি দরকার হলে আবার করব?” প্রশ্নটি প্রতিটি নকশায় আসে, আর উত্তর নির্ভর করে কোন সম্পদটি দামি তার ওপর।

মূল উপলব্ধি: ফল জমা রাখা সময় বাঁচায় আর জায়গা খরচ করে, আবার হিসাব করা জায়গা বাঁচায় আর সময় খরচ করে; Savitch এই আপসের চরম এক প্রান্ত, আর বাস্তবের checkpointing, join-কৌশল আর embedded নকশা এর মাঝামাঝি বিন্দু।

প্র ০৪NP ⊆ PSPACE, কিন্তু PSPACE-এ এমন কী আছে যা NP-তে সম্ভবত নেই? দুই খেলোয়াড়ের খেলা আর “সব প্রতিপক্ষ চালের জন্য” প্রশ্ন কেন স্বাভাবিকভাবে PSPACE-এ পড়ে?

NP-এর প্রশ্ন একটি “আছে কি?” প্রশ্ন: একটি satisfying assignment আছে কি, একটি Hamiltonian পথ আছে কি? উত্তর “হ্যাঁ” হলে একটি ছোট certificate দেখিয়ে প্রমাণ করা যায়। PSPACE-এ আসে পালাক্রমে “আছে” আর “সব” মেশানো প্রশ্ন: “এমন একটি প্রথম চাল আছে কি, যাতে প্রতিপক্ষের সব উত্তরের পরে আমার এমন একটি চাল আছে, যাতে …”। এমন প্রশ্নের “হ্যাঁ” উত্তরের সহজ ছোট প্রমাণ জানা নেই, কারণ প্রমাণে প্রতিপক্ষের প্রতিটি সম্ভাব্য খেলার উত্তর থাকতে হবে, আর সেই গাছ exponential বড়।

কিন্তু জায়গায় এমন প্রশ্নের সমাধান সহজ। খেলার গাছ depth-first ভাবে ঘোরা যায় (DSA পর্ব ৪১-এর DFS): একটি শাখার মূল্য বের করে জায়গা মুছে পরের শাখা। জায়গা লাগে গাছের গভীরতা × একটি অবস্থার আকার। খেলা যদি polynomial সংখ্যক চালে শেষ হয়, তাহলে মোট জায়গা polynomial. এটি অংশ ৩-এর NTIME(t) ⊆ SPACE(t)-এর যুক্তিরই সম্প্রসারণ, যেখানে এখন শাখাগুলোর মধ্যে OR-এর সঙ্গে AND-ও আছে।

পর্ব ৬৫-এ এর আনুষ্ঠানিক রূপ দেখবেন: TQBF, অর্থাৎ ∃x1∀x2∃x3⋯ ধরনের পূর্ণ quantified Boolean formula সত্য কি না, PSPACE-complete (Stockmeyer আর Meyer, ১৯৭৩ বলে পরিচিত)। আশ্চর্যের ব্যাপার, সেই প্রমাণের মূল কৌশল এই পর্বের CANYIELD-ই: “c1 থেকে c2 t ধাপে” প্রশ্নকে quantifier দিয়ে লেখা হয়, একটি ∀ দিয়ে দুটি অর্ধেককে একসঙ্গে প্রকাশ করে formula-র আকার ছোট রাখা হয়। Generalized geography-র মতো খেলাও PSPACE-complete, আর n × n বোর্ডের Go বা দাবার মতো কিছু খেলার সাধারণ রূপ PSPACE-hard বা EXPTIME-complete বলে পরিচিত, নিয়মের খুঁটিনাটির ওপর নির্ভর করে।

বাজারঘরের উদাহরণ: দুই প্রতিদ্বন্দ্বী কুরিয়ার কোম্পানি পালাক্রমে জেলা দখল করছে, যেখানে প্রতিটি নতুন জেলা আগের জেলার পাশে হতে হবে। “প্রথমজনের কি নিশ্চিত জেতার কৌশল আছে?” প্রশ্নটি এই ধরনের।

মূল উপলব্ধি: NP হলো একক “আছে কি” প্রশ্নের শ্রেণি; ∃ আর ∀ পালাক্রমে এলে প্রশ্নটি একটি খেলার মতো হয়, যার ছোট certificate জানা নেই, কিন্তু খেলার গাছ DFS-এ জায়গা পুনর্ব্যবহার করে polynomial জায়গায় ঘোরা যায়, তাই PSPACE খেলার স্বাভাবিক শ্রেণি।

প্র ০৫Turing machine-এ “জায়গা” মানে tape-ঘর। বাস্তব কম্পিউটারে একটি Python প্রোগ্রামের মেমরি-ব্যবহার কি একই জিনিস? Recursion-এর গভীরতা, অস্থায়ী তালিকা আর garbage collection এই হিসাবে কীভাবে মেলে?

মূল ধারণা একই, কিন্তু খুঁটিনাটি আলাদা। Turing machine-এর জায়গা = কতগুলো ঘর কখনো ছোঁয়া হয়েছে। বাস্তব প্রোগ্রামে সমতুল্য মাপ হলো peak memory: চলার সময় কোনো মুহূর্তে একসঙ্গে সর্বোচ্চ কত মেমরি ব্যবহৃত হয়েছে। দুটিই “সর্বোচ্চ”, যোগফল নয়, কারণ মুছে ফেলা মেমরি আবার ব্যবহৃত হয়।

প্রথম পার্থক্য: recursion-এর stack. CANYIELD-এর মতো recursive function-এ প্রতিটি ডাক একটি frame তৈরি করে, আর ডাক শেষ হলে frame মুছে যায়। তাই stack-এর জায়গা = সর্বোচ্চ গভীরতা × frame-এর আকার, ঠিক Savitch-এর হিসাব। CPython-এ ডিফল্ট recursion-সীমা প্রায় ১০০০ স্তর, তাই গভীর recursion বাস্তবে “RecursionError” দেয়, যদিও তাত্ত্বিক জায়গা polynomial. প্রোগ্রামাররা তখন একটি explicit stack ব্যবহার করে recursion-কে loop-এ রূপান্তর করেন (DSA কোর্সের পর্ব ০৭)।

দ্বিতীয় পার্থক্য: অস্থায়ী বস্তু। অংশ ২-এর SAT ব্লকে একটি তালিকা বারবার ব্যবহৃত হয়েছে; কিন্তু কেউ যদি itertools.product-এর সব ফল একটি তালিকায় জমায়, মেমরি 2m হয়ে যায়, যদিও algorithm একই। অর্থাৎ জায়গা-দক্ষতা algorithm-এর পাশাপাশি লেখার ধরনের ওপরও নির্ভর করে। Python-এর garbage collector ব্যবহার শেষ হওয়া বস্তু মুক্ত করে, এটি TM-এর “ঘর মুছে আবার লেখা”-র বাস্তব রূপ, তবে কখন মুক্ত হবে তা সবসময় তাৎক্ষণিক নয়।

তৃতীয় পার্থক্য: ধ্রুবক। Python-এ একটি ছোট পূর্ণসংখ্যাও কয়েক ডজন byte নেয়, একটি তালিকার প্রতিটি ঘর আলাদা pointer. Complexity তত্ত্ব O-তে এসব ধ্রুবক বাদ দেয়, কিন্তু বাস্তবে একটি 108 আকারের তালিকা মেমরি ফুরিয়ে দিতে পারে। Python-এর standard library-র tracemalloc module peak memory মাপতে পারে; এটি TM-এর জায়গার একটি বাস্তব প্রতিচ্ছবি, প্রমাণ নয়।

মূল উপলব্ধি: বাস্তবের peak memory TM-এর space complexity-র কাছাকাছি ধারণা; recursion-এর stack, অস্থায়ী সংগ্রহ আর ধ্রুবক গুণক হিসাবটিকে বাস্তবে বদলায়, তাই জায়গার দাবি যাচাই করতে গভীরতা আর peak দুটিই মাপুন।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। canyield.py-তে নিজের graph দিয়ে উত্তর যাচাইও করতে পারেন।

  1. নকশা: বাজারঘরের ডেলিভারি-ভ্যান m-টি জেলার প্রতিটিতে ঠিক একবার যাবে কি না, এই প্রশ্ন HAMPATH = {⟨G, s, t⟩ : G-তে s থেকে t-এ একটি Hamiltonian পথ আছে}. HAMPATH-এর জন্য একটি deterministic decider-এর high-level বর্ণনা দিন, যা O(n) জায়গা ব্যবহার করে (n = |⟨G, s, t⟩|), আর জায়গার হিসাব দিন। তার সময় কেমন?

    যন্ত্র = “input ⟨G, s, t⟩-এর ওপর: ১. m-টি vertex-এর একটি ক্রম π একটি সারিতে রাখা, প্রথমে 1, 2, …, m. ২. প্রতিটি ক্রমের জন্য: π-এর প্রথম vertex s আর শেষ vertex t কি না, আর প্রতিটি পাশাপাশি জোড়া (πi, πi+1) G-এর একটি তীর কি না দেখা; হলে accept. ৩. π-কে একই জায়গায় lexicographic ক্রমে পরের ক্রমে বদলানো (next permutation); আর ক্রম না থাকলে reject.”

    জায়গা: π-এ m-টি vertex-নম্বর, প্রতিটি O(log m) bit, মোট O(m log m). যুক্তিসংগত encoding-এ প্রতিটি vertex-এর নাম input-এ অন্তত log m bit জুড়ে লেখা থাকে, তাই m log m = O(n). তীর খোঁজা আর next permutation-এ কয়েকটি counter, O(log n). মোট O(n), তাই HAMPATH ∈ SPACE(n) ⊆ PSPACE. সময়: m!টি ক্রম, প্রতিটিতে polynomial কাজ, অর্থাৎ exponential. এটি অংশ ২-এর SAT-এর মতোই: certificate-গুলো একটির পর একটি একই জায়গায়।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: NSPACE(f(n)) ⊆ SPACE(f(n)) (f(n) ≥ n). প্রমাণ: NTM N-এর computation tree DFS-এ ঘুরি। প্রতিটি শাখা f(n) জায়গা ব্যবহার করে, আর একটি শাখা শেষ হলে সেই জায়গা মুছে পরের শাখায় যাই, ঠিক NTIME(t) ⊆ SPACE(t)-এর প্রমাণের মতো। শাখা চেনার জন্য পছন্দের তালিকা রাখি। তাই মোট জায়গা O(f(n)). ∎” দাবিটি কি প্রমাণিত সত্য? প্রমাণে ভুল কোথায়?

    দাবিটি প্রমাণিত নয়; f(n) = n হলে এটি SPACE(n) = NSPACE(n) বোঝাত, যা খোলা প্রথম LBA সমস্যা। ভুলটি “শাখা চেনার জন্য পছন্দের তালিকা রাখি” বাক্যে। NTIME(t)-এর প্রমাণে প্রতিটি শাখা বড়জোর t ধাপ লম্বা, তাই পছন্দের তালিকা O(t) ঘর। কিন্তু f(n) জায়গার NTM-এর একটি শাখা বড়জোর f(n) ঘর ছোঁয়, অথচ 2O(f(n)) ধাপ চলতে পারে (লেমা ৪.১-এর configuration-সংখ্যা পর্যন্ত)। তাই পছন্দের তালিকা exponential লম্বা হতে পারে।

    এই সমস্যা এড়াতেই Savitch শাখা মনে রাখেন না, শুধু মধ্যবিন্দুর configuration রাখেন, আর দাম দেন একটি বাড়তি গুণক f(n): ফল O(f(n)2), O(f(n)) নয়।

  3. Trace আর আগাম অনুমান: চারটি configuration-এর graph c0 → c1 → c2 → c3 (আর কোনো তীর নেই)। CANYIELD(c0, c3, 4)-এ মধ্যবিন্দু c0, c1, c2, c3 ক্রমে চেষ্টা হলে সবচেয়ে বাইরের ডাক কোন মধ্যবিন্দুতে সফল হয়? সর্বোচ্চ recursion-গভীরতা কত? আর CANYIELD(c0, c3, 2)-এর ফল কী?

    মধ্যবিন্দু c0: CANYIELD(c0, c0, 2) হ্যাঁ, কিন্তু CANYIELD(c0, c3, 2) না, কারণ পথে ৩টি ধাপ লাগে। মধ্যবিন্দু c1: CANYIELD(c0, c1, 2) হ্যাঁ (একটি তীর), CANYIELD(c1, c3, 2) হ্যাঁ (দুটি তীর, মধ্যবিন্দু c2). তাই বাইরের ডাক c1-এ সফল। গভীরতা ৩ (t = 4, 2, 1). CANYIELD(c0, c3, 2)-এর ফল reject.

    Scratch-এ চালিয়ে মেলানো হয়েছে: বাইরের মধ্যবিন্দু c1, মোট ২০টি ডাক (canyield.py-র সারণির N = 4, c0 -> c3 সারির সঙ্গে মেলে, গভীরতা ৩), আর t = 2-এর ডাক ৭টি ডাকে False দেয়।

  4. হিসাব: (ক) একটি deterministic decider-এর ৫টি state আর ৪টি tape-চিহ্ন, আর দৈর্ঘ্য n-এর input-এ সে 2n ঘর ব্যবহার করে। n = 3 হলে তার configuration বড়জোর কয়টি? তাহলে n = 3-এ সে সর্বোচ্চ কত ধাপ চলতে পারে? (খ) একটি NTM n3 জায়গায় L-কে decide করে। Savitch থেকে L কোন deterministic জায়গার শ্রেণিতে পড়ে? (গ) নিচের কোনটি প্রমাণিত: ১. NP ⊆ PSPACE; ২. P ⊊ PSPACE; ৩. NL ⊊ PSPACE; ৪. PSPACE = EXP.

    (ক) f = 2n = 6. Configuration ≤ |Q| · f · |Γ|f = 5 · 6 · 46 = 30 · 4096 = 122,880. Decider কোনো configuration পুনরাবৃত্ত করতে পারে না, তাই সে বড়জোর 122,880 − 1 = 122,879 ধাপ চলে (ধাপের সংখ্যা দেখা configuration-এর চেয়ে এক কম)।

    (খ) NSPACE(n3) ⊆ SPACE((n3)2) = SPACE(n6), কারণ n3 ≥ log n. (গ) ১ প্রমাণিত (উপপাদ্য ৩.২)। ২ খোলা। ৩ প্রমাণিত (Savitch + space hierarchy). ৪ খোলা; জানা শুধু PSPACE ⊆ EXP.

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

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

ক্রমSavitch-এর theorem NSPACE(f) ⊆ SPACE(f2)-এর প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. NTM N-কে বদলে একটিমাত্র accepting configuration নিশ্চিত করা
  2. Configuration গুনে একটি সীমা 2d f(n) বের করা
  3. CANYIELD(cstart, caccept, 2d f(n)) ডাকা
  4. প্রতিটি স্তরে একটি মধ্যবিন্দু ধরে t অর্ধেক করা
  5. গভীরতা O(f) আর প্রতিটি frame O(f), তাই জায়গা O(f2)

Savitch-এর theorem কী বলে (f(n) ≥ log n)?

  • NSPACE(f(n)) = SPACE(f(n))
  • NSPACE(f(n)) ⊆ SPACE(f(n)2)
  • NSPACE(f(n)) ⊆ TIME(f(n)2)
  • NTIME(f(n)) ⊆ SPACE(log f(n))

একটি deterministic decider-এর state-সংখ্যা |Q|, tape alphabet Γ, আর দৈর্ঘ্য n-এর input-এ সে f(n) ঘর ব্যবহার করে। সেই input-এ তার সম্ভাব্য configuration-এর সংখ্যার একটি সঠিক ঊর্ধ্বসীমা কোনটি?

  • |Q| + f(n) + |Γ|
  • |Q| · f(n) · |Γ|
  • |Q| · f(n) · |Γ|f(n)
  • 22f(n)

NP ⊆ PSPACE কেন সত্য?

  • NTM-এর সব শাখা (বা সব certificate) একটির পর একটি একই জায়গা মুছে আবার ব্যবহার করে পরীক্ষা করা যায়
  • কারণ P = NP, আর P ⊆ PSPACE
  • শুধু Savitch-এর theorem থেকে, কারণ NP = NSPACE(n)
  • কারণ প্রতিটি NP সমস্যা polynomial সময়ে deterministic ভাবে সমাধান করা যায়

CANYIELD(c1, c2, t) recursive পদ্ধতিতে (প্রতি ডাকে একটি মধ্যবিন্দু ধরে t অর্ধেক করা হয়) t = 2d f(n) দিয়ে শুরু করলে মোট জায়গা O(f(n)2) কেন?

  • মোট ডাকের সংখ্যা f(n)2
  • সব configuration একসঙ্গে একটি টেবিলে রাখা হয়
  • প্রতিটি উপ-প্রশ্নের ফল memoization দিয়ে রাখা হয়
  • Recursion-এর গভীরতা O(f(n)), আর প্রতিটি স্তরের frame O(f(n)) জায়গা নেয়

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

  • P ⊊ PSPACE
  • PSPACE = NPSPACE
  • L = NL
  • NP ⊊ PSPACE

L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP শৃঙ্খলে hierarchy theorem থেকে কোন কঠোর অন্তর্ভুক্তি প্রমাণিত?

  • L ⊊ P আর P ⊊ NP
  • NP ⊊ EXP আর L ⊊ NL
  • NL ⊊ PSPACE আর P ⊊ EXP
  • NP ⊊ PSPACE আর PSPACE ⊊ EXP

শব্দকোষ

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

মনে রাখুন

  1. Space complexity = দৈর্ঘ্য n-এর সব input-এ (NTM-এ সব শাখায়) scan করা ঘরের সর্বোচ্চ সংখ্যা; এই পর্বে f(n) ≥ n, log-জায়গা পর্ব ৬৬-এ।
  2. SAT ∈ SPACE(n) (একটি মান-নির্ধারণের জায়গা বারবার), NOTALLNFA ∈ NSPACE(n) (শুধু বর্তমান subset), ALBA ∈ PSPACE (configuration গোনা)।
  3. TIME(t) ⊆ SPACE(t), NTIME(t) ⊆ SPACE(t), SPACE(f) ⊆ NSPACE(f) ⊆ TIME(2O(f)); configuration ≤ |Q| · f · |Γ|f.
  4. Savitch: f(n) ≥ log n হলে NSPACE(f) ⊆ SPACE(f2); CANYIELD-এর গভীরতা O(f) × frame O(f); দাম সময়ে, 2O(f2). ফল PSPACE = NPSPACE.
  5. L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP; প্রমাণিত কঠোর শুধু NL ⊊ PSPACE আর P ⊊ EXP, বাকিগুলো খোলা।

পরের পর্বে: PSPACE-completeness: TQBF, ∃ আর ∀ পালাক্রমে, CANYIELD থেকেই PSPACE-hardness-এর প্রমাণ, আর generalized geography-র মতো দুই খেলোয়াড়ের খেলা।

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

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