এই পর্বে যা শিখবেন
- Sublinear space মাপার দুই-tape মডেল, L আর NL-এর সংজ্ঞা, আর configuration গোনার হিসাব
- {0k1k}, palindrome আর binary যোগ কীভাবে শুধু counter দিয়ে L-এ পড়ে
- PATH ∈ NL-এর প্রমাণ, log-space transducer আর reduction, আর PATH-এর NL-completeness
- NL ⊆ P, NL ⊆ SPACE(log2 n) আর কোন inclusion প্রমাণিত, কোনটি খোলা
- Immerman–Szelepcsényi উপপাদ্যের inductive counting প্রমাণের রূপরেখা, Reingold-এর উপপাদ্য আর 2SAT
১ · কেন আলাদা মডেল — read-only input tape আর work tape
বাজারঘরের গুদাম-নেটওয়ার্কের ফাইলে কয়েক লাখ লাইন: কোন গুদাম থেকে কোন গুদামে ট্রাক যায়। একটি ছোট হাতযন্ত্র ফাইলটি বারবার পড়তে পারে, কিন্তু নিজের memory-তে রাখতে পারে মাত্র কয়েকটি সংখ্যা। প্রশ্ন: এত কম memory দিয়ে কোন প্রশ্নের উত্তর দেওয়া যায়? এই পর্বের দুটি শ্রেণি, L আর NL, ঠিক এই প্রশ্নের গাণিতিক রূপ।
রেলস্টেশনের দেয়ালে টাঙানো বিশাল টাইমটেবিলের কথা ভাবুন। আপনি যতবার খুশি তাকাতে পারেন, আঙুল দিয়ে যেকোনো লাইনে যেতে পারেন, কিন্তু দেয়ালে কিছু লিখতে পারেন না। আপনার হাতে শুধু একটি ছোট চিরকুট, যাতে দুই-তিনটি সংখ্যা ধরে, যেমন “এখন ১৪৭ নম্বর লাইনে আছি” আর “এ পর্যন্ত ৩টি ট্রেন গুনেছি”। দেয়ালটি input tape, চিরকুটটি work tape. প্রশ্ন হলো, শুধু চিরকুটের মাপে কী কী হিসাব করা যায়।
পর্ব ৬৪-এ space complexity মাপা হয়েছিল এক-tape যন্ত্রে: head যত ঘর ছোঁয়, সবই গোনা। সেখানে input নিজেই n ঘর জুড়ে থাকে, তাই পুরো input পড়ে এমন প্রতিটি যন্ত্র অন্তত n ঘর ব্যবহার করে। ফলে f(n) < n হলে SPACE(f(n)) অর্থহীন হয়ে যায়। সমাধান: input-কে আলাদা একটি tape-এ রাখা, যা শুধু পড়া যায়, আর তার ঘর না গোনা।
একটি যন্ত্রের দুটি tape: (১) read-only input tape, যাতে input w লেখা, দুই পাশে সীমানা-চিহ্ন ▷ আর ◁; এর head বাঁয়ে-ডানে চলে কিন্তু কিছু লেখে না, আর সীমানার বাইরে যায় না। (২) work tape, সাধারণ পড়া-লেখার tape. যন্ত্রটি f(n) space ব্যবহার করে, যদি দৈর্ঘ্য n-এর প্রতিটি input-এ work tape-এর বড়জোর f(n)টি ঘর ছোঁয়; nondeterministic যন্ত্রে সব শাখার মধ্যে সর্বোচ্চ।
L = SPACE(log n) NL = NSPACE(log n)
এটি পর্ব ৪৫-এর multi-tape Turing machine-এরই একটি রূপ, শুধু একটি tape-এ লেখা নিষেধ। f(n) ≥ n হলে এই মডেল আর পর্ব ৬৪-এর মডেল একই শ্রেণি দেয়, কারণ input-কে work tape-এ কপি করতে n ঘর লাগে, যা f(n)-এর মধ্যেই। তাই PSPACE বা NSPACE(n)-এর সংজ্ঞা বদলায় না; নতুন মডেল দরকার শুধু n-এর নিচের সীমার জন্য।
কেন ঠিক log n? 0 থেকে n পর্যন্ত একটি সংখ্যা binary-তে লিখতে ⌊log2 n⌋ + 1 bit লাগে। তাই O(log n) space মানে মোটামুটি “স্থির সংখ্যক counter বা pointer, প্রতিটি input-এর আকার পর্যন্ত”। একটি pointer দিয়ে input-এর যেকোনো ঘর চিহ্নিত করা যায়। কিন্তু input-এর একটি অংশ কপি করা, একটি তালিকা বা “কোন vertex দেখা হয়েছে” ধরনের চিহ্ন রাখা যায় না।
দুই-tape মডেল আর transducer-এর তৃতীয় tape
ওপরে শুধু পড়ার input tape, মাঝে finite control, নিচে work tape. ড্যাশ দেওয়া output tape থাকে শুধু অংশ ৪-এর transducer-এ।
পর্ব ৬৪-এর configuration গোনার হিসাব এই মডেলেও চলে, শুধু একটু বদলে। একটি configuration এখন চারটি জিনিস: state, input head-এর অবস্থান i, work tape-এর লেখা, আর work head-এর অবস্থান j. Input w নিজে configuration-এর অংশ নয়, কারণ তা কখনো বদলায় না।
যন্ত্রটির q-টি state, work alphabet-এ g-টি চিহ্ন, আর space f(n) হলে দৈর্ঘ্য n-এর input-এ configuration-এর সংখ্যা বড়জোর
q · (n + 2) · f(n) · gf(n)
f(n) = c log2 n হলে gc log2 n = nc log2 g, তাই সংখ্যাটি n-এর একটি polynomial.
প্রমাণ: state-এর q রকম পছন্দ; input head (n + 2)টি ঘরের একটিতে (দুই সীমানা-চিহ্নসহ); work head f(n)টি ঘরের একটিতে; আর f(n)টি work ঘরের প্রতিটিতে g রকম চিহ্ন। গুণ করলেই সীমা। ∎
L ⊆ P. আরও সাধারণভাবে, log space-এর প্রতিটি deterministic decider polynomial সময়ে থামে।
প্রমাণ: একটি deterministic decider একই configuration-এ দুবার আসতে পারে না: এলে পরের ধাপগুলো হুবহু পুনরাবৃত্ত হতো আর যন্ত্রটি কখনো থামত না। তাই ধাপের সংখ্যা configuration-এর সংখ্যার চেয়ে কম, যা লেমা ১.২ অনুযায়ী polynomial. ∎
২ · L-এর উদাহরণ — কয়েকটি counter আর pointer-ই যথেষ্ট
প্রথম উদাহরণ পরিচিত: A = {0k1k : k ≥ 0}. পর্ব ৫৭-এ এর সময় মাপা হয়েছিল; এখানে প্রশ্ন জায়গার।
A = {0k1k : k ≥ 0} ∈ L.
প্রমাণ: যন্ত্রটি এমন:
- Input একবার বাঁ থেকে ডানে পড়ে দেখা, এটি 0∗1∗ আকারের কি না; একটি 0 যদি কোনো 1-এর পরে আসে, reject. — এখানে শুধু finite control লাগে, কোনো work ঘর নয়
- আবার শুরুতে ফিরে প্রতিটি 0-এ binary counter z এক বাড়ানো, প্রতিটি 1-এ counter o এক বাড়ানো। — প্রতিটি counter ≤ n, তাই ⌊log2 n⌋ + 1 bit
- ◁-এ পৌঁছে z আর o bit ধরে ধরে মেলানো; সমান হলে accept, নইলে reject. — work tape-এ মোট বড়জোর 2(⌊log2 n⌋ + 1) + 1 ঘর, একটি # বিভাজকসহ
সঠিকতা: ধাপ ১ নিশ্চিত করে input 0a1b আকারের, আর ধাপ ২–৩ যাচাই করে a = b. Space O(log n). ∎
1একবার পড়া: 0*1* আকার?20 পেলে z ← z + 131 পেলে o ← o + 14◁-এ: z = o? accept
| input head | |
| work tape | |
| work ঘর |
- আকার যাচাই। Head ▷ থেকে ◁ পর্যন্ত একবার যায়। 0-এর পরে 1 আসে, কিন্তু 1-এর পরে কোনো 0 আসে না, তাই আকার ঠিক। Work tape এখনো খালি: এই ধাপে জায়গা লাগেনি।
- প্রথম 0. Head শুরুতে ফিরে ঘর 1 পড়ে, z = 1. Work tape-এ “1 # 0”, অর্থাৎ ৩টি ঘর।
- দ্বিতীয় 0. z বেড়ে binary-তে 10 (দুই)। Counter-এ এখন ২টি bit, মোট ৪টি ঘর।
- প্রথম 1. এবার o বাড়ে: o = 1. লক্ষ করুন, input-এর কোনো অংশ কপি হচ্ছে না, শুধু গোনা হচ্ছে।
- দ্বিতীয় 1. o = 10. Work tape-এ “10 # 10”, মোট ৫টি ঘর। n = 4-এ প্রতিটি counter-এর জন্য ⌊log2 4⌋ + 1 = 3 bit যথেষ্ট।
- মেলানো। ◁-এ পৌঁছে দুই counter bit ধরে মেলানো হয়: সমান, তাই accept. n = 106 হলেও counter-প্রতি মাত্র ২০ bit লাগত।
দ্বিতীয় উদাহরণ palindrome: PAL = {w : w = wR}. দুটি pointer i আর j = n − 1 − i রাখুন; head-কে i-তে নিয়ে চিহ্নটি state-এ মনে রাখুন, তারপর j-তে গিয়ে মেলান। Head-কে নির্দিষ্ট ঘরে নিতে একটি counter গুনে গুনে হাঁটে। মোট work: n, i আর j, তিনটি binary সংখ্যা। কিন্তু এর দাম সময়ে: প্রতিটি তুলনায় head প্রায় পুরো input পার হয়, তাই মোট চলাচল প্রায় n2/2. নিচের ব্লক এই দুটি দাম পাশাপাশি গোনে, আর তুলনার জন্য একটি সরল পদ্ধতিও চালায়, যা উল্টো input পুরোটাই work tape-এ কপি করে।
# Palindrome test: read-only input head + O(log n) work bits
from itertools import product
class ReadOnlyInput:
def __init__(self, w): self.w, self.head, self.moves = w, 0, 0
def read(self, k): # walk the head cell by cell to k, then read
self.moves += abs(k - self.head)
self.head = k
return self.w[k]
def logspace_pal(w):
tape, n, peak = ReadOnlyInput(w), len(w), 0 # n: counted by one scan
for i in range(n // 2):
j = n - 1 - i # work tape holds only n, i, j in binary
peak = max(peak, n.bit_length() + i.bit_length() + j.bit_length())
if tape.read(i) != tape.read(j):
return False, peak, tape.moves
return True, peak, tape.moves
def copy_pal(w): # naive: copy the reversed input to work
rev = w[::-1]
return rev == w, len(rev) # one work cell per input symbol
ok = all(logspace_pal(w)[0] == copy_pal(w)[0]
for n in range(1, 11) for w in map("".join, product("01", repeat=n)))
print("all 2046 strings of length 1..10 agree:", ok)
print(" n log-space bits copy cells head moves")
for n in (8, 64, 512, 4096):
w = "01" * (n // 4) + "10" * (n // 4) # a palindrome of length n
res, peak, moves = logspace_pal(w)
print(f"{n:5} {peak:15} {copy_pal(w)[1]:11} {moves:11}")আসল আউটপুট (ব্রাউজারের Python):
all 2046 strings of length 1..10 agree: True
n log-space bits copy cells head moves
8 9 8 28
64 18 64 2016
512 27 512 130816
4096 36 4096 8386560
প্রথম লাইন সঠিকতার brute-force যাচাই: দৈর্ঘ্য ১ থেকে ১০-এর সব ২০৪৬টি string-এ দুই পদ্ধতির উত্তর এক। তারপর দাম: n আটগুণ হলে log-space পদ্ধতির work bit বাড়ে মাত্র ৯ করে (9, 18, 27, 36), কারণ তিনটি সংখ্যার প্রতিটিতে log2 8 = 3 bit যোগ হয়। কপি করা পদ্ধতির ঘর বাড়ে n-এর সমান হারে। অথচ head-এর চলাচল 8386560 = 4096 · 4095 / 2, ঠিক n(n − 1)/2. Space বাঁচাতে সময় দিতে হলো: এটি space আর time-এর একটি সাধারণ বিনিময়। (Python-এর memory মাপা হয়নি; bit-গুলো গোনা হয়েছে যন্ত্রের work tape-এর হিসাব ধরে।)
একই কৌশলে আরও অনেক কিছু L-এ পড়ে। দুটি binary সংখ্যার যোগ যাচাই (অনুশীলন ১), গুণ, বা একটি input DFA-কে একটি string-এ চালানো: পর্ব ৫০-এর ADFA ∈ L, কারণ শুধু বর্তমান state-এর নম্বর আর input-এর অবস্থান মনে রাখলেই চলে। সাধারণ নিয়ম: যা “কয়েকটি আঙুল আর কয়েকটি গণনা” দিয়ে করা যায়, তা L-এ। যা “কোথায় কোথায় গেছি তার তালিকা” চায়, তা নিয়ে সন্দেহ রাখুন।
৩ · NL আর PATH — অনুমান করে পথ হাঁটা
এবার বাজারঘরের আসল প্রশ্ন: গুদাম s থেকে গুদাম t-তে ট্রাক পাঠানো যায় কি, এক বা একাধিক হাত বদলে? গাণিতিক রূপ:
PATH = {⟨G, s, t⟩ : G একটি directed graph, আর G-তে s থেকে t-তে একটি directed পথ আছে}
পর্ব ৫৭-এ দেখা গেছে PATH ∈ P: BFS দিয়ে চিহ্ন দিতে দিতে এগোনো। কিন্তু BFS প্রতিটি vertex-এর জন্য একটি “দেখা হয়েছে” চিহ্ন রাখে, অর্থাৎ m vertex-এ m bit. DFS-এর stack-ও m গভীর হতে পারে। দুটিই log space-এর বাইরে। Nondeterminism থাকলে কিন্তু কাজটি সহজ।
একজন রিকশাওয়ালা অচেনা এলাকায় একটি ঠিকানা খুঁজছেন, যাঁর মনে থাকে শুধু “এখন কোন মোড়ে আছি” আর “কতবার মোড় ঘুরেছি”। প্রতিটি মোড়ে তিনি একটি রাস্তা বেছে নেন। ভাগ্য ভালো হলে পৌঁছে যান। nondeterministic যন্ত্র হলো “সবসময় ভাগ্যবান” রিকশাওয়ালা: পথ থাকলে কোনো একটি বাছাই-ক্রম তাঁকে পৌঁছে দেয়, আর তাঁর memory দুটি সংখ্যার বেশি নয়।
PATH ∈ NL.
প্রমাণ: G-এর vertex-সংখ্যা m ≤ n (input-এর দৈর্ঘ্য)। NTM N, input ⟨G, s, t⟩-এ:
- cur ← s, steps ← 0 লেখা। — দুটি সংখ্যা, প্রতিটি ≤ m: O(log n) bit
- steps < m যতক্ষণ: cur = t হলে accept. নইলে একটি vertex v অনুমান করা, input পড়ে দেখা (cur, v) একটি তীর কি না; না হলে এই শাখা reject. হলে cur ← v, steps ← steps + 1. — v-ও একটি vertex-নম্বর; তীর খুঁজতে শুধু input pointer লাগে
- steps = m হলে reject.
সঠিকতা: s থেকে t-তে পথ থাকলে একটি সরল পথ আছে, যার দৈর্ঘ্য বড়জোর m − 1; যে শাখা সেই পথের vertex-গুলো ঠিক ক্রমে অনুমান করে, সেটি accept করে। উল্টো দিকে, কোনো শাখা accept করলে তার অনুমান করা vertex-ক্রমই s থেকে t-তে একটি পথ। প্রতিটি শাখা m ধাপের মধ্যে থামে, আর work tape-এ শুধু cur, steps আর v. ∎
লক্ষ করুন একটি অসমতা। “পথ আছে” দেখাতে একটি ভাগ্যবান শাখাই যথেষ্ট। কিন্তু “পথ নেই” হলে প্রতিটি শাখা reject করে, আর বাইরে থেকে কোনো একটি শাখা দেখে তা বোঝা যায় না। NP আর coNP-এর মধ্যে ঠিক এই অসমতাই খোলা প্রশ্ন (পর্ব ৬২)। Log space-এ এর উত্তর অপ্রত্যাশিত, তা অংশ ৭-এ।
নিচের ব্লক আটটি গুদামের একটি graph নেয়। গুদাম 7 আর 8 থেকে 1-এ ট্রাক যায়, কিন্তু 1 থেকে তাদের দিকে কোনো পথ নেই। একটি শাখার অনুমানগুলো এখানে random (seed স্থির); তুলনার জন্য সব শাখা একে একে গোনা হয়েছে, যা শুধু simulation-এর কৌশল, NTM-এর কাজ নয়।
# PATH in NL: one branch remembers only (current vertex, step counter)
import random
random.seed(66)
G = {1: [2, 3], 2: [3, 4], 3: [2, 5], 4: [1, 6], 5: [4],
6: [], 7: [1, 8], 8: [7]} # warehouses; 7 and 8 only send to 1
m = len(G)
def branch(s, t): # one branch; its guesses are random here
cur, steps = s, 0 # the whole work tape: cur, steps
while cur != t and steps < m - 1 and G[cur]:
cur, steps = random.choice(G[cur]), steps + 1
return cur == t
def count_branches(s, t, cur=None, steps=0): # explore every branch (sim only)
cur = s if cur is None else cur
if cur == t or steps == m - 1 or not G[cur]:
return 1, int(cur == t)
res = [count_branches(s, t, x, steps + 1) for x in G[cur]]
return sum(r[0] for r in res), sum(r[1] for r in res)
def bfs(s):
seen, queue = {s}, [s]
for x in queue:
for y in G[x]:
if y not in seen: seen.add(y); queue.append(y)
return seen
print(f"m = {m}: work bits per branch {2 * m.bit_length()}, BFS seen-set {m} bits")
for t in (6, 8):
total, acc = count_branches(1, t)
hits = sum(branch(1, t) for _ in range(1000))
print(f"t={t}: {total} branches, {acc} accept; random 1000 -> {hits}; "
f"BFS: {t in bfs(1)}")
for n in (10 ** 3, 10 ** 6):
print(f"n = {n:>7}: branch needs {2 * n.bit_length():2} bits, BFS {n} bits")আসল আউটপুট (ব্রাউজারের Python):
m = 8: work bits per branch 8, BFS seen-set 8 bits
t=6: 54 branches, 14 accept; random 1000 -> 546; BFS: True
t=8: 54 branches, 0 accept; random 1000 -> 0; BFS: False
n = 1000: branch needs 20 bits, BFS 1000 bits
n = 1000000: branch needs 40 bits, BFS 1000000 bits
t = 6-এর জন্য ৫৪টি শাখার ১৪টি accept করে; random অনুমানে প্রায় অর্ধেক সফল (৫৪৬/১০০০), কারণ অনেক শাখা 2 ⇄ 3 বা 1 → 2 → 4 → 1-এর চক্রে ঘুরে সময় শেষ করে। কিন্তু NL-এর সংজ্ঞায় একটি accept করা শাখাই যথেষ্ট। t = 8-এর জন্য একটি শাখাও accept করে না; এই “না”-টি কোনো একক শাখা দেখে প্রমাণ হয় না। শেষ দুই লাইন আসল কথা: দশ লাখ vertex-এও একটি শাখার memory ৪০ bit, যেখানে BFS-এর চিহ্নই দশ লাখ bit. (m = 8-এ দুটি সংখ্যা সমান দেখাচ্ছে, কারণ ছোট n-এ log n আর n-এর ফারাক চোখে পড়ে না।)
৪ · Log-space reduction আর transducer
NP-এর জন্য “সবচেয়ে কঠিন” মাপা হয়েছিল polynomial-time reduction দিয়ে (পর্ব ৫৯)। NL-এর জন্য তা কাজ করে না। কারণ NL ⊆ P (অংশ ৬-এ প্রমাণ), তাই একটি polynomial সময়ের reduction নিজেই প্রশ্নটির উত্তর বের করে ফেলতে পারে, তারপর একটি স্থির “হ্যাঁ” বা “না” instance লিখে দিতে পারে। তাহলে ∅ আর Σ∗ বাদে NL-এর প্রতিটি language “NL-complete” হয়ে যেত, আর ধারণাটি অর্থহীন হতো। নিয়মটি সাধারণ: reduction-কে যে শ্রেণি নিয়ে কথা, তার চেয়ে দুর্বল হতে হবে।
একটি log-space transducer হলো তিন-tape যন্ত্র: read-only input tape, O(log n) ঘরের work tape, আর একটি write-only output tape, যার head শুধু ডানে চলে আর যার ঘর গোনা হয় না (ছবি ৬৬.১-এর ড্যাশ দেওয়া tape). থামার সময় output tape-এ f(w) লেখা থাকলে f log space-এ হিসাবযোগ্য।
A ≤L B (log-space reduction), যদি এমন f থাকে যাতে প্রতিটি w-এর জন্য w ∈ A ⇔ f(w) ∈ B. B NL-এ আর NL-এর প্রতিটি A-এর জন্য A ≤L B হলে B NL-complete.
এটি পর্ব ৫২-এর mapping reduction-এরই আরও কড়া রূপ। লেমা ১.২-এর হিসাবে একটি log-space transducer polynomial সময়ে থামে, তাই |f(w)| ≤ nk কোনো স্থির k-এর জন্য, আর A ≤L B ⇒ A ≤p B.
A ≤L B আর B ∈ L হলে A ∈ L. একই যুক্তিতে ≤L transitive.
প্রমাণ:
- স্বাভাবিক চেষ্টা: আগে f(w) লিখে নিয়ে তার ওপর B-এর decider MB চালানো। কিন্তু f(w)-এর দৈর্ঘ্য polynomial, তাকে work tape-এ রাখা যায় না। — সমস্যার মূল
- কৌশল: f(w) কখনো জমা না রাখা। MA শুধু MB-এর state, work tape আর f(w)-এর ওপর তার input head-এর অবস্থান j রাখে। — j ≤ nk, তাই O(log n) bit
- MB যখনই f(w)-এর j-তম চিহ্ন চায়, MA transducer-টি w-এর ওপর গোড়া থেকে আবার চালায়, output চিহ্নগুলো একটি counter দিয়ে গোনে আর j-তমটি ছাড়া সব ফেলে দেয়। — transducer-এর work O(log n), counter O(log n)
- মোট space O(log n) + O(log nk) = O(log n). সঠিকতা: MA হুবহু MB-কে f(w)-এর ওপর চালায়, আর w ∈ A ⇔ f(w) ∈ B. Transitivity-র জন্য MB-এর জায়গায় দ্বিতীয় transducer বসিয়ে একই কাজ। ∎
সময় অনেক বাড়ে, কারণ প্রতিটি চিহ্নের জন্য পুরো transducer আবার চলে; কিন্তু polynomial × polynomial এখনো polynomial, আর space বাড়ে না। গ্রন্থাগারের একটি বই, যা ফটোকপি করা নিষেধ, কিন্তু যতবার খুশি খুলে নির্দিষ্ট পাতা দেখা যায়: এটিই “জমা না রেখে আবার হিসাব করা” কৌশল। এর সরাসরি পরিণাম: কোনো NL-complete সমস্যা L-এ থাকলে L = NL.
৫ · PATH NL-complete — configuration graph দিয়ে প্রমাণ
PATH log-space reduction-এর অধীনে NL-complete.
মূল ধারণা: একটি log-space NTM-এর গণনা নিজেই একটি graph-এ হাঁটা। Configuration graph GM,w-এর node হলো M-এর w-এর ওপর সব configuration, আর c1 থেকে c2-তে তীর, যদি এক ধাপে c1 ⊢ c2. তাহলে “M w-কে গ্রহণ করে” মানে “শুরুর configuration থেকে accept configuration-এ পথ আছে”।
প্রমাণ:
- PATH ∈ NL, উপপাদ্য ৩.১. — NL-complete-এর প্রথম শর্ত
- যেকোনো A ∈ NL নিন; NTM M তাকে O(log n) space-এ decide করে। M-কে সামান্য বদলে নেওয়া যায়, যাতে accept করার আগে work tape মুছে দুই head বাঁ প্রান্তে ফেরায়; তাহলে accept configuration একটিই, cacc. — এতে space বাড়ে না
- Reduction: f(w) = ⟨GM,w, cstart, cacc⟩. প্রতিটি configuration একটি O(log n) দৈর্ঘ্যের string: state, i, work tape-এর লেখা, j. — লেমা ১.২: node polynomial সংখ্যক
- Transducer: দৈর্ঘ্য c log n-এর প্রতিটি string ক্রমে লিখে দেখে সেটি বৈধ configuration কি না, হলে node হিসেবে output করে। তারপর প্রতিটি জোড়া (c1, c2) নিয়ে দেখে M-এর কোনো একটি move c1-কে c2-তে নেয় কি না। এর জন্য লাগে শুধু c1-এর state, work head-এর নিচের চিহ্ন, আর w-এর i-তম চিহ্ন, যা transducer নিজের input head গুনে গুনে i-তে নিয়ে পড়ে। — work tape-এ দুটি configuration আর কয়েকটি counter: O(log n)
- সঠিকতা: w ∈ A ⇔ M-এর কোনো শাখা cacc-এ পৌঁছায় ⇔ GM,w-এ cstart থেকে cacc-এ পথ আছে ⇔ f(w) ∈ PATH. তাই A ≤L PATH. ∎
একটি ছোট উদাহরণে পুরো রূপান্তরটি দেখা যাক। বাজারঘরের একটি sensor লাইনে 1 মানে সতর্কসংকেত; প্রশ্ন, পরপর দুটি সংকেত (“11”) কখনো এসেছে কি না। NTM N-এর দুটি সক্রিয় state: q-তে সে ডানে পড়তে থাকে; একটি 1 পড়লে q-তে থেকে যেতে পারে, অথবা অনুমান করতে পারে “এখান থেকেই জোড়া শুরু” আর g-তে যায়। g-তে পরের ঘরে 1 পেলে accept. যন্ত্রটির work tape খালি থাকে, তাই প্রতিটি node মাত্র (state, input-ঘর); আসল log-space যন্ত্রে node-এ work tape-এর লেখাও থাকে, কিন্তু তাতে graph-এর আকার শুধু বড় হয়, ধারণা বদলায় না।
1node = (state, input-ঘর)2তীর: স্থানীয় নিয়ম, শুধু w-এর ঘর i3start = (q,0), শেষ = ACC4PATH: start থেকে ACC?
| এই ধাপে | |
| node | |
| তীর |
- Node. দুটি state q আর g, আর input-ঘর 0 থেকে 5 (সীমানা-চিহ্নসহ)। এছাড়া একটিমাত্র accept node ACC. মোট ২ × ৬ + ১ = ১৩টি node.
- আকারের সীমা। সাধারণ যন্ত্রে node-সংখ্যা q · (n + 2) · f(n) · gf(n); f(n) = c log n হলে এটি polynomial, তাই transducer সব node একে একে লিখতে পারে।
- স্ক্যান-তীর। q-তে যন্ত্র ▷, 0 বা 1 পড়ে ডানে যায়: (q, i) → (q, i + 1), i = 0 থেকে 4. ◁-এ (ঘর 5) কোনো তীর নেই। প্রতিটি তীর ঠিক করতে transducer w-এর শুধু ঘর i পড়ে।
- অনুমানের তীর। 1 আছে ঘর 2 আর 3-এ, তাই (q, 2) → (g, 3) আর (q, 3) → (g, 4); আর g যেখানে 1 পড়ে, সেখান থেকে ACC: (g, 2) → ACC, (g, 3) → ACC. মোট ৯টি তীর।
- পথ = গ্রহণকারী শাখা। (q,0) → (q,1) → (q,2) → (g,3) → ACC. এটি সেই শাখা, যা ঘর 2-এর 1-এ অনুমান করে “জোড়া এখানে”। তাই ⟨G, (q,0), ACC⟩ ∈ PATH ⇔ 0110 ∈ L(N).
- উল্টো উদাহরণ। w = 0101-এ 1 আছে ঘর 2 আর 4-এ। g-তে গেলে পরের ঘর 0 (ঘর 3) বা ◁ (ঘর 5), তাই ACC-তে কোনো পথ নেই, আর N সত্যিই 0101 বর্জন করে।
রূপান্তরটি সব ছোট input-এ সঠিক কি না, brute force দিয়ে মেলানো যাক। নিচের ব্লক প্রতিটি w-এর জন্য GN,w বানায়, তারপর সাধারণ reachability দিয়ে দেখে ACC-তে পথ আছে কি না, আর তা “w-এ 11 আছে কি না”-এর সঙ্গে মেলায়।
# Configuration graph G(N, w) of a tiny NTM N for "w contains 11"
from itertools import product
def graph(w): # the reduction f: w -> <G, start, ACC>
t = ">" + w + "<" # boundary markers at cells 0 and n+1
V = [(q, i) for q in "qg" for i in range(len(t))] + ["ACC"]
E = []
for i, a in enumerate(t): # local rule: looks only at cell i
if a != "<": # state q scans right
E.append((("q", i), ("q", i + 1)))
if a == "1": # q may guess "a pair 11 starts here"
E.append((("q", i), ("g", i + 1)))
E.append((("g", i), "ACC")) # g reads the second 1: accept
return V, E
def path(V, E, s, t): # plain reachability (BFS)
seen, queue = {s}, [s]
for x in queue:
for a, b in E:
if a == x and b not in seen: seen.add(b); queue.append(b)
return t in seen
V, E = graph("0110")
print("w = 0110:", len(V), "nodes,", len(E), "edges")
print("edges:", [e for e in E if e[0][0] == "g" or e[1] != ("q", e[0][1] + 1)])
print("path (q,0) -> ACC:", path(V, E, ("q", 0), "ACC"))
bad = [w for n in range(9) for w in map("".join, product("01", repeat=n))
if path(*graph(w), ("q", 0), "ACC") != ("11" in w)]
print("all 511 strings of length 0..8: mismatches =", len(bad))
print("w = 0101 path:", path(*graph("0101"), ("q", 0), "ACC"))আসল আউটপুট (ব্রাউজারের Python):
w = 0110: 13 nodes, 9 edges
edges: [(('q', 2), ('g', 3)), (('g', 2), 'ACC'), (('q', 3), ('g', 4)), (('g', 3), 'ACC')]
path (q,0) -> ACC: True
all 511 strings of length 0..8: mismatches = 0
w = 0101 path: False
১৩টি node আর ৯টি তীর stepper-এর সঙ্গে মেলে; দ্বিতীয় লাইন স্ক্যান-তীর বাদে বাকি চারটি তীর দেখায়। দৈর্ঘ্য ০ থেকে ৮-এর সব ৫১১টি string-এ “ACC-তে পথ আছে” আর “w-এ 11 আছে” হুবহু মেলে, অর্থাৎ এই ছোট যন্ত্রের জন্য w ∈ L(N) ⇔ f(w) ∈ PATH সত্যিই খাটে। লক্ষ করুন, graph() ফাংশন প্রতিটি তীরের জন্য শুধু একটি ঘর t[i] দেখে; আসল transducer-ও ঠিক এভাবে, পুরো graph মনে না রেখে, একটি একটি তীর লিখে যায়। (Python-এর list-এ সব তীর জমা রাখা হয়েছে শুধু গোনার সুবিধার জন্য।)
৬ · NL ⊆ P আর inclusion-এর মানচিত্র
NL ⊆ P.
প্রমাণ: A ∈ NL হলে A ≤L PATH (উপপাদ্য ৫.১)। Log-space reduction polynomial সময়ে চলে, আর PATH ∈ P (BFS), তাই A ∈ P. সরাসরি ভাবলে: polynomial আকারের configuration graph-এ BFS চালালেই হয়। ∎
NL ⊆ SPACE(log2 n).
প্রমাণের রূপরেখা: এটি Savitch-এর উপপাদ্য-এর f(n) = log n ক্ষেত্র (Savitch ১৯৭০; পর্ব ৬৪)। Configuration graph-এ nO(1)টি node, তাই CANYIELD recursion-এর গভীরতা O(log n), আর প্রতিটি স্তরে O(log n) bit-এর দুটি configuration. গুণফল O(log2 n). উপপাদ্যটির শর্ত f(n) ≥ log n এখানে ঠিক সীমায় পূরণ হয়। ∎
এবার পুরো ছবি। পর্ব ৬৪-এর ফলের সঙ্গে মিলিয়ে:
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE
আর পর্ব ৬৭-এর space hierarchy theorem থেকে SPACE(log2 n) ⊊ SPACE(n), তাই NL ⊊ PSPACE. এর একটি মজার পরিণাম: শৃঙ্খলের চারটি “⊆”-এর অন্তত একটি অবশ্যই কড়া (⊊), কারণ সবগুলো সমান হলে NL = PSPACE হতো। কিন্তু কোনটি কড়া, তা কেউ জানে না।
L থেকে PSPACE — প্রমাণিত আর অজানা
প্রতিটি বাক্স তার বাইরের বাক্সের ভেতরে (⊆)। পাশে পরিচিত উদাহরণ।
| বক্তব্য | অবস্থা | কোথায় |
|---|---|---|
| L ⊆ NL ⊆ P | প্রমাণিত | অনুসিদ্ধান্ত ১.৩, ৬.১ |
| NL ⊆ SPACE(log2 n) | প্রমাণিত (Savitch ১৯৭০) | পর্ব ৬৪ |
| NL ⊊ PSPACE | প্রমাণিত (space hierarchy) | পর্ব ৬৭ |
| NL = coNL | প্রমাণিত (১৯৮৭–৮৮) | অংশ ৭ |
| L = NL? | খোলা (⇔ PATH ∈ L) | অংশ ৫ |
| NL = P? L = P? | খোলা | ভাবনার প্রশ্ন ৪ |
৭ · NL = coNL — Immerman–Szelepcsényi আর inductive counting
অংশ ৩-এর অসমতায় ফিরি: “পথ আছে” দেখানো সহজ, “পথ নেই” দেখানো কঠিন মনে হয়। NP-এর ক্ষেত্রে এই অনুভূতি থেকেই বেশিরভাগ গবেষক NP ≠ coNP মনে করেন। Log space-এ কিন্তু উত্তর উল্টো, আর তা প্রায় একই সময়ে দুজন স্বাধীনভাবে খুঁজে পান।
NL = coNL, যেখানে coNL = {Ā : A ∈ NL}. সমতুল্যভাবে, PATH̄ ∈ NL: “s থেকে t-তে কোনো পথ নেই” প্রশ্নটিও log space-এ nondeterministic ভাবে decide করা যায়।
কেন PATH̄-ই যথেষ্ট: যেকোনো A ∈ NL-এর জন্য A ≤L PATH, f দিয়ে। তাহলে একই f দিয়ে w ∉ A ⇔ f(w) ∉ PATH, অর্থাৎ Ā ≤L PATH̄. PATH̄ ∈ NL হলে লেমা ৪.২-এর NL-রূপে (অনুশীলন ২) Ā ∈ NL. তাই coNL ⊆ NL, আর একই যুক্তি উল্টো দিকে খাটায় NL = coNL.
পরীক্ষার হলে একজন পরিদর্শক জানেন হলে মোট ৪০ জন পরীক্ষার্থী আছেন। কেউ জিজ্ঞেস করলেন, “রোল ১০৭ কি এই হলে আছে?” পরিদর্শক সব আসন ঘুরে প্রত্যেকের প্রবেশপত্র দেখেন, আর গোনেন। ৪০ জনকেই খুঁজে পেলেন আর তাঁদের কেউ রোল ১০৭ নয়: তাহলে রোল ১০৭ নিশ্চিতভাবে এখানে নেই। মোট সংখ্যাটি জানা থাকাই “নেই”-কে প্রমাণযোগ্য করে, কারণ কাউকে বাদ দিয়ে গেলে গণনা ৪০-এ পৌঁছাত না।
এটিই inductive counting-এর মূল কথা। ধরুন G-তে m vertex, আর Ri = s থেকে বড়জোর i ধাপে পৌঁছানো যায় এমন vertex-এর set, ci = |Ri|. Rm−1-ই s থেকে নাগালের সব vertex.
প্রমাণের রূপরেখা:
- গুনে সদস্য তালিকা। ci জানা থাকলে NTM Ri-এর সদস্যদের “প্রমাণসহ” একে একে পেতে পারে: প্রতিটি u-এর জন্য অনুমান করে u ∈ Ri কি না; হ্যাঁ অনুমান করলে s থেকে u-তে দৈর্ঘ্য ≤ i-এর একটি পথ অনুমান করে যাচাই করে (ব্যর্থ হলে শাখা reject). যাচাই হওয়া u-গুলো গোনে। শেষে গণনা ci-এর সমান না হলে reject. — টিকে থাকা প্রতিটি শাখায় যাচাই হওয়া u-গুলো ঠিক Ri
- ci থেকে ci+1. c0 = 1 (শুধু s). প্রতিটি v-এর জন্য ধাপ ১ দিয়ে Ri-এর সদস্যদের আবার তালিকা করা; কোনো যাচাই হওয়া u-এর জন্য u = v বা u → v একটি তীর হলে v ∈ Ri+1. এমন v-গুলো গুনলে ci+1. — প্রতিটি v-এর জন্য তালিকা নতুন করে, জমা রাখা নয়
- শেষ ধাপ। cm−1 পেয়ে ধাপ ১-এর মতো Rm−1-এর সদস্যদের আরেকবার তালিকা করা। t যাচাই হলে reject; গণনা cm−1-এ পৌঁছায় আর t তাদের মধ্যে নেই হলে accept. — “পথ নেই”-এর প্রমাণ
- সঠিকতা। যে শাখা accept করে, সে cm−1টি আলাদা নাগালের vertex যাচাই করেছে, যা সব নাগালের vertex, আর t তাদের মধ্যে নেই; তাই সত্যিই পথ নেই। উল্টো দিকে, পথ না থাকলে যে শাখা প্রতিটি অনুমান ঠিক করে, সে accept করে।
- Space. একসঙ্গে মনে রাখতে হয় i, ci, ci+1, v, u, যাচাইয়ের গণনা, আর পথ-অনুমানের বর্তমান vertex ও ধাপ-সংখ্যা: স্থির সংখ্যক সংখ্যা, প্রতিটি ≤ m. তাই O(log n). ∎
1c₀ = 1 (শুধু s)2প্রতিটি v: সব u ঘুরে দেখা3u ∈ Rᵢ অনুমান হলে পথ অনুমান, যাচাই4যাচাই-গণনা ≠ cᵢ হলে reject5cₘ₋₁ জন পেলাম, t নেই: accept
| রাউন্ড | |
| Rᵢ (ছবিতে) | |
| গণনা |
- শুরু। R0 = {s} = {1}, তাই c0 = 1. যন্ত্রটি set-টি মনে রাখে না, শুধু সংখ্যাটি। ডানের “Ri” সারিটি শুধু আপনার বোঝার জন্য।
- রাউন্ড ১. প্রতিটি v-এর জন্য যন্ত্র সব u ঘোরে; যাচাই হয় শুধু u = 1 (গণনা ১ = c0, ঠিক আছে)। v = 1 (নিজে), 2 আর 3 (তীর 1→2, 1→3) R1-এ পড়ে, তাই c1 = 3.
- রাউন্ড ২. এবার যাচাই হয় 1, 2, 3 (গণনা ৩ = c1). নতুন যোগ হয় 4, কারণ 2→4 আর 3→4. 5 বা 6-এ এদের কারও তীর নেই। c2 = 4.
- রাউন্ড ৩ থেকে ৫. যাচাই হয় 1, 2, 3, 4; তাদের থেকে নতুন তীর শুধু 4→1, যা পুরোনো। তাই c3 = c4 = c5 = 4. (m = 6, তাই শেষ সংখ্যা c5.) লক্ষ করুন, 6→1 তীরটি উল্টো দিকে, তাই কাজে লাগে না।
- ফাঁকি দেওয়া শাখা। রাউন্ড ৩-এ একটি শাখা অলসভাবে অনুমান করল “4 ∉ R2”. তার যাচাই-গণনা ৩, কিন্তু c2 = 4, তাই শাখাটি reject করে। এভাবেই গণনা কোনো সদস্য বাদ দেওয়া ঠেকায়।
- “পথ নেই”-এর প্রমাণ। শেষ তালিকায় যাচাই হয় 1, 2, 3, 4: গণনা ৪ = c5, আর 5 তাদের মধ্যে নেই। তাই শাখাটি accept করে: 1 থেকে 5-এ কোনো পথ নেই। পুরো সময় যন্ত্রের হাতে ছিল কয়েকটি ছোট সংখ্যা, কোনো set নয়।
একই graph-এ পদ্ধতিটি চালানো যাক। NTM-এর “পথ অনুমান” এখানে একটি ছোট brute-force খোঁজ দিয়ে বসানো, যাতে সঠিক অনুমানের শাখাটি অনুসরণ করা যায়; যন্ত্রের নিজের memory-র হিসাব শেষ লাইনে।
# Inductive counting (Immerman-Szelepcsenyi): certify "no path s -> t"
G = {1: [2, 3], 2: [4], 3: [4], 4: [1], 5: [6], 6: [5, 1]}
V, s, m = sorted(G), 1, len(G)
checks = 0
def guess_path(u, i): # an NTM branch GUESSES a path s ->..-> u of
global checks; checks += 1 # length <= i; this stand-in finds one if it
R = {s} # exists (brute force), so the branch that
for _ in range(i): # guesses right is the one we follow
R |= {y for x in R for y in G[x]}
return u in R
def next_count(c, i, skip=None): # c_{i+1} from c_i using only counters
c_next = 0
for v in V:
verified, hit = 0, False
for u in V:
if u != skip and guess_path(u, i):
verified += 1
hit = hit or u == v or v in G[u]
if verified != c: return None # count mismatch: this branch rejects
c_next += hit
return c_next
c = [1] # c_0 = |{s}|
for i in range(m - 1):
c.append(next_count(c[i], i))
print("c_0..c_5 =", c, "| check calls:", checks)
print("lazy branch skipping 4 in round 3:", next_count(c[2], 2, skip=4))
def no_path(t): # accept iff t is NOT reachable from s
found = [u for u in V if guess_path(u, m - 1)]
return len(found) == c[-1] and t not in found
for t in (5, 4):
print(f"t={t}: certified 'no path 1 -> {t}':", no_path(t))
print("work numbers: i, c, c_next, v, u, verified + path guess; each <=",
m, "->", m.bit_length(), "bits")আসল আউটপুট (ব্রাউজারের Python):
c_0..c_5 = [1, 3, 4, 4, 4, 4] | check calls: 180
lazy branch skipping 4 in round 3: None
t=5: certified 'no path 1 -> 5': True
t=4: certified 'no path 1 -> 4': False
work numbers: i, c, c_next, v, u, verified + path guess; each <= 6 -> 3 bits
গণনার ক্রম 1, 3, 4, 4, 4, 4 stepper-এর সঙ্গে হুবহু মেলে। ১৮০টি যাচাই = ৫টি রাউন্ড × ৬টি v × ৬টি u: একই সদস্য-তালিকা বারবার নতুন করে বানানো হয়, কারণ জমা রাখার জায়গা নেই; এটি polynomial, তাই সমস্যা নয়। “None” মানে অলস শাখাটি গণনা মেলাতে না পেরে reject করেছে। t = 5-এর জন্য “পথ নেই” প্রমাণিত, আর t = 4-এর জন্য ব্যর্থ, কারণ 4 সত্যিই নাগালে। শেষ লাইন memory-র হিসাব: স্থির সংখ্যক সংখ্যা, প্রতিটি ৩ bit; m বাড়লে বাড়ে শুধু log m হারে।
f(n) ≥ log n (আর space-constructible) হলে NSPACE(f(n)) = coNSPACE(f(n)). বিশেষত NSPACE(n), অর্থাৎ context-sensitive language-এর শ্রেণি, complement-এ বদ্ধ।
শেষ বাক্যটির পেছনে পুরোনো একটি প্রশ্ন। ১৯৬৪ সালে S.-Y. Kuroda linear bounded automaton নিয়ে (পর্ব ০৬) দুটি প্রশ্ন রাখেন বলে পরিচিত, যা “LBA সমস্যা” নামে পরিচিত: (১) deterministic আর nondeterministic LBA কি সমান শক্তির, অর্থাৎ SPACE(n) = NSPACE(n)? (২) context-sensitive language কি complement-এ বদ্ধ? দ্বিতীয়টির উত্তর “হ্যাঁ”, এই উপপাদ্য থেকে। প্রথমটি আজও খোলা।
ইতিহাস: Neil Immerman (যুক্তরাষ্ট্র) আর Róbert Szelepcsényi (তৎকালীন চেকোস্লোভাকিয়া) ১৯৮৭ সালে প্রায় একই সময়ে, পরস্পরের কাজ না জেনে, একই ফল পান; প্রকাশ ১৯৮৭–৮৮ সালে। দুজনে যৌথভাবে ১৯৯৫ সালের Gödel Prize পান। Immerman এসেছিলেন logic-এর দিক থেকে (ভাবনার প্রশ্ন ৫), Szelepcsényi automata-র দিক থেকে। প্রমাণটি এত ছোট যে আজ পাঠ্যবইয়ে এক-দুই পাতায় আসে, অথচ এর আগে অনেকে NL ≠ coNL মনে করতেন।
৮ · Undirected পথ L-এ, 2SAT আর NL-এর আরও সমস্যা
বাজারঘরের রাস্তাগুলো যদি দুই দিকেই চলে, অর্থাৎ graph undirected হয়, তাহলে প্রশ্নটি UPATH (undirected s–t connectivity). এটি সহজ মনে হয়, কিন্তু log space-এ প্রমাণ করতে কয়েক দশক লেগেছে।
UPATH ∈ L.
গল্পটি তিন ধাপের। ১৯৭৯ সালে Aleliunas, Karp, Lipton, Lovász আর Rackoff দেখান, undirected graph-এ একটি random walk polynomial ধাপের মধ্যে খুব বেশি সম্ভাবনায় s-এর component-এর সব vertex ঘুরে আসে; random walk-এর memory শুধু বর্তমান vertex আর একটি counter, তাই UPATH randomized log space-এ (পর্ব ৬৯-এ randomized শ্রেণি)। ১৯৮২ সালে Lewis আর Papadimitriou এমন সমস্যার জন্য SL নামে একটি শ্রেণি সংজ্ঞায়িত করেন। শেষে Omer Reingold expander graph আর “zig-zag product” দিয়ে randomness সরিয়ে দেখান UPATH ∈ L, অর্থাৎ SL = L. এই ধারার কাজের জন্য Reingold, Salil Vadhan আর Avi Wigderson ২০০৯ সালের Gödel Prize পান বলে জানা যায়।
Directed graph-এ একই কৌশল ভেঙে পড়ে। একটি পথ 1 → 2 → … → m কল্পনা করুন, যেখানে প্রতিটি vertex থেকে একটি করে তীর আবার 1-এ ফেরে। Random walk প্রতি ধাপে অর্ধেক সম্ভাবনায় শুরুতে ফিরে যায়, আর m-এ পৌঁছাতে গড়ে 2m − 2 ধাপ লাগে (scratch-এ m = 2 থেকে 11 পর্যন্ত সমীকরণ সমাধান করে মেলানো)। তাই PATH ∈ L খোলা, আর তা প্রমাণ হলে L = NL.
এবার 2SAT: প্রতিটি clause-এ বড়জোর দুটি literal থাকা CNF সূত্র satisfiable কি না। পর্ব ৬১-এ দেখানো হয় 2SAT ∈ P, যেখানে 3SAT NP-complete. Log space-এ আরও সূক্ষ্ম কথা বলা যায়।
2SAT log-space reduction-এর অধীনে NL-complete.
প্রমাণের রূপরেখা:
- φ-এর implication graph: প্রতিটি literal একটি vertex, প্রতিটি clause (α ∨ β) থেকে তীর ¬α → β আর ¬β → α. জানা ফল: φ unsatisfiable ⇔ কোনো চলক x-এর জন্য x থেকে ¬x-এ আর ¬x থেকে x-এ দুটি পথই আছে। — DSA কোর্সের পর্ব ৪৬-এ এটি SCC দিয়ে করা হয়
- তাই 2SAT-এর complement NL-এ: x অনুমান করে দুটি PATH-যাচাই। NL = coNL বলে 2SAT ∈ NL. — উপপাদ্য ৭.১-এর সরাসরি ব্যবহার
- কঠিনতা: ⟨G, s, t⟩ থেকে সূত্র φ বানানো: প্রতিটি vertex v-এর জন্য চলক xv, প্রতিটি তীর (u, v)-এর জন্য clause (¬xu ∨ xv), আর একক clause xs ও ¬xt. পথ থাকলে xs সত্য হওয়া পথ ধরে xt-কে সত্য হতে বাধ্য করে, তাই φ unsatisfiable. পথ না থাকলে “xv সত্য ⇔ v নাগালে” একটি satisfying assignment. — তাই ⟨G, s, t⟩ ∉ PATH ⇔ φ ∈ 2SAT, একটি log-space reduction PATH̄ ≤L 2SAT
- PATH̄ NL-complete (NL = coNL আর PATH NL-complete থেকে), তাই 2SAT NL-hard, আর ধাপ ২ মিলিয়ে NL-complete. ∎
(ধাপ ৩-এর reduction scratch-এ ৩০০০টি random ছোট graph-এ brute-force SAT দিয়ে মেলানো হয়েছে, কোনো অমিল পাওয়া যায়নি।) মূল ফলটি সাধারণত Neil Jones, Y. Edmund Lien আর William Laaser-এর ১৯৭৬ সালের কাজের সঙ্গে যুক্ত বলা হয়, যেখানে 2SAT-এর complement NL-complete দেখানো হয়েছিল; NL = coNL আসার পর 2SAT নিজেও NL-complete.
| সমস্যা | শ্রেণি | মূল কারণ |
|---|---|---|
| {0k1k}, PAL, binary যোগ | L | কয়েকটি counter আর pointer |
| ADFA (DFA-কে string-এ চালানো) | L | শুধু বর্তমান state মনে রাখা |
| UPATH | L | Reingold (expander) |
| PATH, PATH̄ | NL-complete | configuration graph; NL = coNL |
| NFA-র language ফাঁকা নয়? | NL-complete | start থেকে accept state-এ পথ |
| 2SAT | NL-complete | implication graph |
NFA-র সারিটির কারণ সহজ: একটি NFA-র language ফাঁকা নয় ঠিক তখন, যখন তার state diagram-এ শুরু থেকে কোনো accept state-এ পথ আছে, যা PATH-এর প্রশ্ন; উল্টো দিকে যেকোনো ⟨G, s, t⟩-কে NFA বানানো যায় (সব তীরে একই চিহ্ন, শুরু s, accept শুধু t).
আরও গভীরে: NL-এর একটি সুন্দর বিকল্প সংজ্ঞা আছে: যেসব language-এর জন্য একটি log-space verifier আছে, যা polynomial দৈর্ঘ্যের certificate শুধু একবার, বাঁ থেকে ডানে পড়ে (read-once certificate). Certificate যতবার খুশি পড়তে দিলে শ্রেণিটি NP-তে লাফ দেয়। Savitch-এর log2 n সীমা জানা মতে ১৯৭০ সালের পর সাধারণ NL-এর জন্য আর উন্নত হয়নি; randomized log space-এর জন্য Saks আর Zhou ১৯৯৯ সালে SPACE(log3/2 n)-এর সীমা দেন বলে পরিচিত। আর L = NL, NL = P, L = P তিনটিই খোলা।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Sublinear space-এর জন্য কোন মডেল, কেন? Read-only input tape আর আলাদা work tape; নইলে input নিজেই n ঘর নেয়।
- PATH ∈ NL প্রমাণ করুন। বর্তমান vertex আর ধাপ-counter রেখে পরের vertex অনুমান করা; m ধাপে থামা।
- NL-completeness-এ ≤p কেন চলে না? NL ⊆ P, তাই polynomial reduction নিজেই উত্তর বের করে ফেলে; ≤L লাগে।
- NL ⊆ P কেন? Configuration graph polynomial আকারের; তাতে BFS.
- Immerman–Szelepcsényi কী বলে? NL = coNL; inductive counting দিয়ে “পথ নেই” প্রমাণ। L = NL কিন্তু খোলা।
৯ · AI-এর যুগে L আর NL
L আর NL-এর প্রশ্নে AI assistant-এর ভুলগুলো প্রায়ই সংজ্ঞার সূক্ষ্মতায়। Input-এর ঘরও space-এ গুনে ফেলা, “DFS তো শুধু বর্তমান vertex রাখে, তাই log space” বলা, NL = coNL থেকে NP = coNP টেনে আনা, Reingold-এর ফলকে directed graph-এ খাটানো, বা NL-completeness-এ polynomial-time reduction ব্যবহার করা খুবই সাধারণ। আবার “Savitch দেখিয়েছেন L = NL” ধরনের বানানো দাবিও আসে। নিয়মটি সরল: প্রতিটি space-দাবির জন্য জিজ্ঞেস করুন, work tape-এ ঠিক কোন কোন সংখ্যা থাকে, আর প্রতিটি কত বড়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “PAL-এ n ঘর লাগে, কারণ input n দৈর্ঘ্যের” | দুই-tape মডেলে input গোনা হয় না; শুধু work tape |
| “DFS দিয়ে PATH ∈ L” | visited চিহ্ন বা stack কোথায় থাকে? m bit লাগে; ঠিক হলে L = NL প্রমাণ হতো |
| “NL = coNL, তাই NP = coNP-ও সত্য হওয়ার কথা” | Inductive counting সময়ে polynomial দামে কাজ করে না; NP বনাম coNP খোলা |
| “Reingold: সব graph-এ পথ খোঁজা L-এ” | শুধু undirected; directed PATH ∈ L খোলা |
| “PATH NL-complete, ≤p দিয়ে” | ≤p-এর অধীনে প্রায় সবকিছুই “complete” হয়ে যায়; ≤L লাগে |
| “L = NL প্রমাণিত” বা বানানো সাল | Sipser অধ্যায় ৮ বা Arora–Barak অধ্যায় ৪-এ নিজে মেলান |
AI-কে কাজে লাগানোর ভালো উপায়: প্রতিটি যন্ত্রের work tape-এর বিষয়বস্তু তালিকা আকারে চাওয়া, তারপর ছোট graph বা string-এ নিজে Python-এ চালিয়ে উত্তর brute force-এর সঙ্গে মেলানো, যেমন এই পর্বের ব্লকগুলো করেছে।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১NL = coNL প্রমাণিত, অথচ NP = coNP-কে বেশিরভাগ গবেষক মিথ্যা মনে করেন। Inductive counting space-এ কাজ করে, সময়ে করে না কেন?
দুটি প্রশ্নের গঠন একই: “না”-উত্তরের ছোট, দ্রুত যাচাইযোগ্য প্রমাণ আছে কি? NP-এর ক্ষেত্রে, যেমন একটি সূত্র unsatisfiable, এমন প্রমাণ সাধারণভাবে জানা নেই; resolution-এর মতো নির্দিষ্ট proof system-এ সূচকীয় দৈর্ঘ্যের প্রমাণ লাগে বলে প্রমাণিতও আছে। তাই বিশ্বাস, NP ≠ coNP.
Inductive counting-এর মূল চাল হলো সংখ্যা জানা থাকলে “সব সদস্য খুঁজে পেয়েছি” যাচাই করা। Log space-এ এটি সস্তা, কারণ মহাবিশ্বটি ছোট: configuration graph-এ polynomial সংখ্যক node, তাই ci একটি O(log n) bit-এর সংখ্যা, আর প্রতিটি node-কে একে একে ঘুরে দেখা polynomial সময়ে হয়। NP-এর সমতুল্য কৌশল চেষ্টা করলে “মহাবিশ্ব” হতো একটি polynomial-time NTM-এর সব configuration, যা সূচকীয় সংখ্যক। গণনাটি তখনও polynomial bit-এ লেখা যায়, কিন্তু সব সদস্য একে একে যাচাই করতে সূচকীয় সময় লাগবে। অর্থাৎ space-এ আমরা সময় অপচয় করতে পারি, সময়ের হিসাবে পারি না।
আরেকটি দিক: space পুনর্ব্যবহারযোগ্য। Inductive counting প্রতিটি v-এর জন্য পুরো সদস্য-তালিকা নতুন করে বানায় (inductive_counting.py-তে ১৮০টি যাচাই), কারণ জমা রাখা যায় না, কিন্তু একই ঘর বারবার ব্যবহার করা যায়। Savitch-এর উপপাদ্যেও (পর্ব ৬৪) একই দর্শন: সময় দিয়ে জায়গা কেনা।
ইতিহাসের শিক্ষাও আছে। ১৯৮৭ সালের আগে অনেকে NL ≠ coNL মনে করতেন, NP-এর সঙ্গে মিলিয়ে। Kuroda-র ১৯৬৪ সালের “দ্বিতীয় LBA সমস্যা” প্রায় তেইশ বছর খোলা ছিল। তারপর দুজন গবেষক, একজন logic থেকে আর একজন automata থেকে, এক-দুই পাতার একটি যুক্তিতে প্রশ্নটি মিটিয়ে দেন। তাই complexity-তে “মনে হওয়া” আর প্রমাণ আলাদা রাখতে হয়।
মূল উপলব্ধি: NL = coNL সম্ভব হয়েছে কারণ log space-এ configuration-এর সংখ্যা polynomial, তাই সব সদস্য গুনে যাচাই করা যায়; একই কৌশল NP-তে সূচকীয় সময় নেয়, আর NP বনাম coNP খোলা।
প্র ০২Undirected graph-এ পথ খোঁজা L-এ, কিন্তু directed graph-এ তা অজানা। দুই ধরনের graph-এর মধ্যে আসল পার্থক্যটা কোথায়, আর random walk এই গল্পে কী ভূমিকা রাখে?
Undirected graph-এর একটি মৌলিক সুবিধা: যে পথে এসেছেন, সেই পথে ফেরা যায়। ফলে কোথাও আটকে পড়ার ভয় নেই। এর গাণিতিক রূপ হলো random walk-এর আচরণ। Aleliunas, Karp, Lipton, Lovász আর Rackoff ১৯৭৯ সালে দেখান, m vertex আর e তীরের connected undirected graph-এ একটি random walk মোটামুটি m · e-এর অনুপাতে ধাপে, খুব বেশি সম্ভাবনায়, প্রতিটি vertex ঘুরে আসে। Walker-এর memory শুধু বর্তমান vertex আর ধাপের counter, তাই UPATH randomized log space-এ পড়ে।
Directed graph-এ এই নিশ্চয়তা নেই। এই পর্বের অংশ ৮-এর উদাহরণ: প্রতিটি vertex থেকে একটি তীর সামনে আর একটি শুরুতে ফেরার। Walker প্রতি ধাপে অর্ধেক সম্ভাবনায় শুরুতে ফিরে যায়, আর শেষে পৌঁছাতে গড়ে 2m − 2 ধাপ লাগে। একমুখী রাস্তার শহরে একজন পথিক যেমন সহজে আটকে যান, এটিও তেমন।
Randomness সরানোর কাজটি ছিল কঠিন। Lewis আর Papadimitriou ১৯৮২ সালে SL (symmetric log space) সংজ্ঞায়িত করেন, আর পরের দুই দশকে ধাপে ধাপে space-এর সীমা নামানো হয়। Omer Reingold-এর ২০০৫ সালের প্রমাণ graph-কে ধাপে ধাপে একটি expander graph-এ রূপান্তর করে, যেখানে প্রতিটি vertex থেকে O(log m) দৈর্ঘ্যের পথেই সব vertex-এ পৌঁছানো যায়; তখন সব ছোট পথ deterministic ভাবে পরীক্ষা করা যায়। মূল হাতিয়ার Reingold, Vadhan আর Wigderson-এর zig-zag product, যা graph-এর degree না বাড়িয়ে expansion বাড়ায়।
Directed ক্ষেত্রের গুরুত্ব হলো: PATH NL-complete, তাই PATH ∈ L হলে L = NL. Reingold-এর কৌশল directed graph-এ সরাসরি চলে না, কারণ ফেরার পথের প্রতিসাম্যই সেখানে নেই। Randomized log space আর L-এর সম্পর্কও (RL = L?) খোলা, যদিও এ দিকে অনেক আংশিক অগ্রগতি আছে।
মূল উপলব্ধি: Undirected graph-এর প্রতিসাম্য random walk-কে দ্রুত সব জায়গায় পৌঁছে দেয়, আর Reingold সেই randomness-ও সরিয়েছেন; directed graph-এ এই প্রতিসাম্য নেই, আর সেখানে log space-এ পথ খোঁজা মানেই L বনাম NL প্রশ্ন।
প্র ০৩বাস্তবে কম্পিউটারের memory গিগাবাইটে মাপা হয়। তাহলে log space-এর তত্ত্ব কি শুধু গণিতের খেলা, নাকি বাস্তব কোনো প্রশ্নের সঙ্গে এর যোগ আছে?
যোগ আছে, তবে সরাসরি “এই প্রোগ্রাম log n byte নেয়” আকারে নয়। মূল ধারণাটি হলো “input মস্ত, memory তার তুলনায় নগণ্য, আর input শুধু পড়া যায়”। বাস্তবে এই অবস্থা প্রায়ই আসে। বাজারঘরের দিনের সব অর্ডারের log কয়েক শো গিগাবাইট হতে পারে, যা disk-এ শুধু পড়ার জন্য রাখা; একটি বিশ্লেষণ প্রোগ্রামের RAM তার তুলনায় সামান্য। তখন প্রশ্ন ওঠে: কয়েকটি pointer আর counter রেখে ফাইলটি বারবার পড়ে কী কী বের করা যায়?
এর কাছের একটি বাস্তব মডেল হলো streaming algorithm: input একবার (বা কয়েকবার) পড়া যায়, আর memory input-এর তুলনায় খুব ছোট, সাধারণত polylog. Alon, Matias আর Szegedy-এর ১৯৯৬ সালের কাজ এই ক্ষেত্রের ভিত্তি গড়ে বলে পরিচিত, যেখানে frequency moment-এর মতো পরিমাণ ছোট memory-তে আনুমানিক হিসাবের পদ্ধতি আর নিচের সীমা দুই-ই দেখানো হয়। লক্ষ করুন পার্থক্যটি: log space-এর যন্ত্র input যতবার খুশি, যেকোনো দিকে পড়তে পারে; streaming-এ পড়ার সংখ্যা সীমিত। আরেকটি পুরোনো ধারা হলো read-only memory-তে কম জায়গায় selection আর sorting, যেমন Munro আর Paterson-এর ১৯৮০ সালের কাজ, যেখানে কম memory-র বিনিময়ে বেশি pass লাগে।
তত্ত্বের দিক থেকে L আরেকটি কারণে গুরুত্বপূর্ণ: log-space reduction এত দুর্বল যে তা “প্রায় বিনা খরচের” রূপান্তর মাপার মানদণ্ড, আর P-completeness-এর মতো ধারণাও এর ওপর দাঁড়ানো (প্রশ্ন ৪)। এছাড়া এই পর্বের palindrome ব্লকে যে বিনিময় দেখা গেল, n2/2 head চলাচলের দামে মাত্র ৩৬ bit, তা embedded যন্ত্রে বা cache-এর হিসাবে বাস্তব নকশার একটি চেনা বিনিময়।
তবে সতর্কতা: একটি তাত্ত্বিক log-space algorithm-এর সময় বড় polynomial হতে পারে (inductive counting-এর মতো), তাই বাস্তবে সরাসরি ব্যবহার কম। তত্ত্বটি সীমানা দেখায়, প্রকৌশল সেই সীমার মধ্যে ভালো বিনিময় খোঁজে।
মূল উপলব্ধি: Log space-এর মূল ছবি, “বিশাল read-only input আর কয়েকটি pointer”, বড় ডেটা প্রক্রিয়াকরণের একটি বাস্তব অবস্থা; streaming আর কম-memory algorithm এর নিকট আত্মীয়, যদিও মডেলগুলো হুবহু এক নয়।
প্র ০৪P-completeness কী, আর তার সংজ্ঞায়ও কেন polynomial-time reduction নয়, log-space reduction ব্যবহার হয়? L = P প্রশ্নের সঙ্গে এর সম্পর্ক কী?
অংশ ৪-এর যুক্তি এখানে আরও তীব্র। P-এর ভেতরের সমস্যার মধ্যে “সবচেয়ে কঠিন” খুঁজতে polynomial-time reduction দিলে reduction নিজেই সমস্যাটি সমাধান করে ফেলতে পারে, তাই ∅ আর Σ∗ বাদে P-এর প্রতিটি language “P-complete” হয়ে যেত। তাই P-completeness-এর সংজ্ঞা: B ∈ P, আর P-এর প্রতিটি A-এর জন্য A ≤L B.
সবচেয়ে পরিচিত উদাহরণ CVP (circuit value problem): একটি Boolean circuit আর তার input দেওয়া আছে, output কি 1? Richard Ladner ১৯৭৫ সালে এর P-completeness দেখান বলে পরিচিত। প্রমাণের ধারণা Cook–Levin-এর tableau-র মতো (পর্ব ৬০): একটি polynomial সময়ের যন্ত্রের গণনাকে স্তরে স্তরে একটি circuit হিসেবে লেখা, আর এই লেখার কাজটি log space-এ করা যায়, কারণ প্রতিটি gate শুধু আগের স্তরের কয়েকটি gate-এর ওপর নির্ভর করে। আরও কিছু P-complete সমস্যা: linear programming-এর একটি decision রূপ, Horn-SAT, আর একটি নির্দিষ্ট ক্রমের greedy পদ্ধতির ফল নির্ধারণ।
এর মানে কী? যদি কোনো P-complete সমস্যা L-এ পড়ে, তাহলে লেমা ৪.২-এর যুক্তিতে P = L; NL-এ পড়লে P = NL. তাই P-complete সমস্যাগুলো “log space-এ সম্ভবত করা যায় না” এমন সমস্যার প্রতিনিধি। আরও ব্যবহারিক একটি দিক: এগুলো “parallel-এ সম্ভবত দ্রুত করা যায় না” সমস্যারও প্রতিনিধি, কারণ NC নামের শ্রেণি (polylog গভীরতার circuit, পর্ব ৭০) log space-এর কাছাকাছি, আর P-complete সমস্যা NC-তে থাকলে P = NC হতো, যা অসম্ভাব্য মনে করা হয়। তাই কোনো সমস্যা P-complete প্রমাণ হলে সাধারণত ধরা হয় এটি “স্বভাবে ক্রমিক” (inherently sequential).
কিন্তু এগুলো সবই শর্তসাপেক্ষ: L = P, NL = P, NC = P সব খোলা। শুধু L ⊊ PSPACE প্রমাণিত, তাই শৃঙ্খলের কোথাও না কোথাও ফারাক আছে।
মূল উপলব্ধি: একটি শ্রেণির ভেতরের completeness মাপতে reduction-কে শ্রেণিটির চেয়ে দুর্বল হতে হয়; তাই P-complete আর NL-complete দুটিই log-space reduction দিয়ে সংজ্ঞায়িত, আর CVP-এর মতো P-complete সমস্যা L-এ পড়লে L = P হতো।
প্র ০৫Immerman logic থেকে এসে NL = coNL প্রমাণ করেন। Descriptive complexity কী, আর logic দিয়ে complexity শ্রেণি বর্ণনা করার ধারণা কোথা থেকে এল?
সাধারণভাবে complexity শ্রেণি সংজ্ঞায়িত হয় যন্ত্র দিয়ে: কত সময়, কত জায়গা। Descriptive complexity প্রশ্নটি উল্টে দেয়: একটি ধর্ম লিখতে কোন ধরনের logic-এর বাক্য লাগে? এখানে input হলো একটি গাণিতিক কাঠামো, যেমন একটি graph, আর প্রশ্ন হলো “এই graph-এ এই ধর্ম আছে কি না” লেখার জন্য logic-এর কোন শক্তি যথেষ্ট।
সূচনা Ronald Fagin-এর ১৯৭৪ সালের উপপাদ্য: NP ঠিক সেই ধর্মগুলো, যা existential second-order logic-এ লেখা যায়, অর্থাৎ “এমন একটি সম্পর্ক (যেমন একটি রং-ভাগ) আছে, যাতে প্রথম-ক্রমের একটি শর্ত সত্য”। এটি verifier-সংজ্ঞার logic-রূপ: অস্তিত্বসূচক সম্পর্কটিই certificate. যন্ত্রের কোনো উল্লেখ ছাড়াই NP-এর একটি সংজ্ঞা।
১৯৮০-এর দশকে Immerman আর অন্যরা ক্রম-সহ কাঠামোর ওপর আরও এমন মিল দেখান: first-order logic-এর সঙ্গে transitive closure নামের একটি operator যোগ করলে ঠিক NL পাওয়া যায় (FO(TC) = NL); deterministic transitive closure দিলে L; আর least fixed point operator দিলে P, যা Immerman আর Vardi স্বাধীনভাবে দেখান বলে পরিচিত। Transitive closure মানে “x থেকে y-তে কোনো পথ আছে”, তাই NL-এর প্রতিনিধি যে PATH, তা logic-এর দিক থেকেও স্বাভাবিক।
এই ভাষায় NL = coNL-এর প্রশ্ন দাঁড়ায়: transitive closure-এর আগে “না” বসালে কি আবার একই logic-এ লেখা যায়? Immerman এই প্রশ্ন থেকেই inductive counting-এর ধারণায় পৌঁছান বলে জানা যায়। তাঁর ১৯৯৯ সালের বই “Descriptive Complexity” এই ক্ষেত্রের প্রধান পাঠ্য।
লাভ কী? Logic-এর বর্ণনা যন্ত্র-নিরপেক্ষ, তাই শ্রেণিগুলো কৃত্রিম নয় বলে আস্থা বাড়ে। Database তত্ত্বেও এর সরাসরি প্রভাব আছে, কারণ query ভাষাগুলো মূলত logic, আর কোন query কত খরচে চলে তা এই মিল থেকে বোঝা যায়।
মূল উপলব্ধি: Descriptive complexity দেখায় complexity শ্রেণিগুলো logic-এর স্বাভাবিক ভাষার সঙ্গে মেলে (NP = existential second-order, NL = FO(TC)); এই দৃষ্টিভঙ্গি থেকেই NL = coNL-এর প্রমাণ এসেছিল।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের graph বা string বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা (log-space যন্ত্র): ADD = {x#y#z : x, y, z binary string, বাঁ দিকে বড় bit, আর সংখ্যা হিসেবে x + y = z}. শুধু read-only input আর O(log n) work tape দিয়ে ADD-এর একটি decider-এর high-level বর্ণনা নকশা করুন, work tape-এ কী কী থাকে তা বলুন, আর input 11#01#100-এ চালিয়ে দেখান।
প্রথমে একবার পড়ে আকার যাচাই (ঠিক দুটি #) আর দৈর্ঘ্য তিনটি গোনা। ধরুন Lmax = তিন দৈর্ঘ্যের সর্বোচ্চ। তারপর k = 0, 1, …, Lmax − 1-এর জন্য (ডান থেকে k-তম bit): x, y আর z-এর k-তম bit পড়া, প্রতিটির জন্য head-কে সংশ্লিষ্ট # বা ◁ থেকে বাঁয়ে k ঘর গুনে নিয়ে গিয়ে (string ছোট হলে bit 0 ধরা); t = xk + yk + carry হিসাব; t mod 2 ≠ zk হলে reject; carry ← ⌊t/2⌋. শেষে carry = 0 হলে accept. Work tape-এ: তিনটি দৈর্ঘ্য, k, head সরানোর একটি counter (প্রতিটি ≤ n, O(log n) bit), আর carry (১ bit). মোট O(log n), তাই ADD ∈ L.
11#01#100 (৩ + ১ = ৪): Lmax = 3. k = 0: 1 + 1 + 0 = 2, bit 0, z0 = 0 মেলে, carry 1. k = 1: 1 + 0 + 1 = 2, bit 0, z1 = 0 মেলে, carry 1. k = 2: 0 + 0 + 1 = 1, z2 = 1 মেলে, carry 0. শেষে carry 0: accept. (এই পদ্ধতি scratch-এ দৈর্ঘ্য ১–৩-এর x, y আর ১–৪-এর z-এর সব ৫৮৮০টি জোড়ায় সাধারণ যোগের সঙ্গে মেলানো হয়েছে।)
-
প্রমাণ: প্রমাণ করুন: A ≤L B আর B ∈ NL হলে A ∈ NL. (অংশ ৭-এ NL = coNL-এর যুক্তিতে এটি লেগেছে।)
f একটি log-space transducer T দিয়ে হিসাব হয়, আর NTM MB B-কে O(log m) space-এ decide করে, m = |f(w)|. T polynomial সময়ে থামে (লেমা ১.২), তাই m ≤ nk. NTM MA, input w-এ: MB-কে f(w)-এর ওপর simulate করে, কিন্তু f(w) জমা রাখে না। শুধু রাখে MB-এর state, work tape আর f(w)-এর ওপর তার head-অবস্থান j. MB যখন j-তম চিহ্ন চায়, MA T-কে w-এর ওপর গোড়া থেকে চালায়, output গোনে, j-তম চিহ্নটি নেয়, বাকি ফেলে দেয়। MB-এর nondeterministic পছন্দ MA হুবহু নিজের পছন্দ হিসেবে নেয়।
Space: MB-এর work O(log nk) = O(log n), j-এর জন্য O(log n), T-এর work O(log n), আর output-counter O(log n). সঠিকতা: T deterministic, তাই প্রতিবার আবার চালালে একই চিহ্ন দেয়; ফলে MA-এর শাখাগুলো ঠিক MB-এর f(w)-এর ওপর শাখাগুলোর সঙ্গে মেলে। তাই MA w গ্রহণ করে ⇔ MB f(w) গ্রহণ করে ⇔ f(w) ∈ B ⇔ w ∈ A. ∎
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: PATH ∈ L. প্রমাণ: s থেকে DFS চালাই। প্রতি মুহূর্তে শুধু বর্তমান vertex-এর নম্বর জানা দরকার, যা O(log n) bit. প্রতিটি vertex থেকে তার তীরগুলো input-এ পড়ে একটির পর একটি ধরে এগোই। t-তে পৌঁছালে accept, সব শেষ হলে reject. ∎” ভুলটি কোথায়?
DFS-এর দুটি জিনিস লাগে, যা “শুধু বর্তমান vertex”-এ নেই। প্রথমত, ফেরার পথ: একটি শাখা শেষ হলে আগের vertex-এ ফিরে তার পরের তীর ধরতে হয়, তাই পথের সব vertex আর প্রতিটির “কোন তীর পর্যন্ত দেখা হয়েছে” মনে রাখতে হয়, যা m গভীর stack, O(m log m) bit. Directed graph-এ তীর উল্টো দিকে চলে না, তাই input থেকে ফেরার পথ বের করা যায় না। দ্বিতীয়ত, চক্র: “দেখা হয়েছে” চিহ্ন (m bit) না থাকলে যন্ত্র 2 → 3 → 2-এর মতো চক্রে চিরকাল ঘুরতে পারে, অথবা একই অংশ সূচকীয় বার ঘোরে।
একটি সংকেতও আছে: দাবিটি সত্য হলে PATH NL-complete বলে L = NL প্রমাণ হয়ে যেত, যা বিখ্যাত খোলা প্রশ্ন। এত ছোট “প্রমাণে” এমন ফল প্রায় নিশ্চিতভাবে ভুল। (Undirected graph-এ Reingold সত্যিই L-এ পথ খোঁজেন, কিন্তু সম্পূর্ণ ভিন্ন, অনেক গভীর কৌশলে।)
-
হিসাব (trace): G-এর vertex 1–5, তীর 1→2, 2→3, 3→1, 4→5, 5→4; s = 1, t = 4. Inductive counting চালিয়ে c0, c1, …, c4 বের করুন, আর বলুন “1 থেকে 4-এ পথ নেই” প্রমাণ হয় কি না। inductive_counting.py-র মতো গুনলে রাউন্ডগুলোতে মোট কতগুলো পথ-যাচাই হয়?
R0 = {1}, c0 = 1. R1 = {1, 2} (1→2), c1 = 2. R2 = {1, 2, 3} (2→3), c2 = 3. 3→1 পুরোনো, তাই R3 = R4 = {1, 2, 3}, c3 = c4 = 3. শেষ তালিকায় যাচাই হয় 1, 2, 3; গণনা ৩ = c4, আর 4 নেই, তাই accept: পথ নেই প্রমাণিত। (4 আর 5-এর মধ্যে দুই দিকের তীর আছে, কিন্তু 1-এর component থেকে সেখানে কোনো তীর নেই।)
যাচাইয়ের সংখ্যা: m = 5, রাউন্ড ৪টি (c1 থেকে c4), প্রতি রাউন্ডে ৫টি v × ৫টি u = ২৫, মোট ১০০; শেষ তালিকায় আরও ৫টি। (c-এর মানগুলো scratch-এ BFS-এর স্তর গুনে মেলানো: [1, 2, 3, 3, 3].)
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রম“প্রতিটি NL language PATH-এ log-space reduce হয়” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- A ∈ NL নেওয়া, যাকে একটি NTM M O(log n) space-এ decide করে
- M-কে এমনভাবে বদলানো, যাতে accept configuration ঠিক একটি থাকে
- w-এর জন্য GM,w: node মানে configuration, তীর মানে এক ধাপের move
- Transducer প্রতিটি configuration-জোড়া O(log n) work ঘরে পরীক্ষা করে তীর লেখে
- w ∈ A ⇔ GM,w-এ cstart থেকে cacc-এ পথ আছে
L = SPACE(log n) সংজ্ঞায়িত করতে read-only input tape আর আলাদা work tape-এর মডেল কেন লাগে?
- যাতে input head শুধু ডানে চলে আর যন্ত্র দ্রুত হয়
- নইলে input-এর n ঘরই গোনা হতো, আর n-এর কম space অর্থহীন হতো
- যাতে nondeterminism ব্যবহার করা যায়
- কারণ এক-tape মডেলে PSPACE ভুলভাবে সংজ্ঞায়িত হয়
নিচের কোন বক্তব্যটি এখনো খোলা প্রশ্ন (প্রমাণিত বা খণ্ডিত নয়)?
- NL = coNL
- L ⊆ P
- NL ≠ PSPACE
- L = NL
PATH ∈ NL প্রমাণের NTM-এর একটি শাখা work tape-এ কী রাখে?
- বর্তমান vertex, পরের অনুমিত vertex আর একটি ধাপ-counter
- প্রতিটি vertex-এর জন্য একটি “দেখা হয়েছে” চিহ্ন
- s থেকে এ পর্যন্ত হাঁটা পুরো পথ
- DFS-এর recursion stack
NL-completeness সংজ্ঞায়িত করতে polynomial-time reduction (≤p) না নিয়ে log-space reduction (≤L) নেওয়া হয় কেন?
- কারণ ≤L ≤p-এর চেয়ে বেশি শক্তিশালী
- কারণ PATH-এ কোনো polynomial-time reduction নেই
- NL ⊆ P বলে polynomial-time reduction নিজেই সমস্যাটি সমাধান করে ফেলতে পারে
- কারণ ≤p nondeterministic
Immerman–Szelepcsényi উপপাদ্যের (NL = coNL) একটি সরাসরি পরিণাম কোনটি?
- NP = coNP
- Context-sensitive language-এর complement-ও context-sensitive
- L = NL
- SPACE(n) = NSPACE(n)
Reingold-এর উপপাদ্য (সম্মেলনে ২০০৫) সম্পর্কে কোন বক্তব্যটি সঠিক?
- এটি দেখায় directed PATH ∈ L, তাই L = NL
- এটি দেখায় undirected পথ খোঁজা শুধু randomized log space-এ
- এটি NL = coNL প্রমাণ করে
- Undirected graph-এ s–t সংযোগ deterministic log space-এ decide করা যায়
একটি 2CNF সূত্র φ-এর implication graph-এ (প্রতিটি clause (α ∨ β) থেকে তীর ¬α → β আর ¬β → α) কোন অবস্থায় φ unsatisfiable?
- কোনো চলক x-এর জন্য x থেকে ¬x-এ আর ¬x থেকে x-এ দুটি পথই আছে
- কোনো চলক x-এর জন্য x থেকে ¬x-এ একটি পথ আছে
- Graph-এ কোনো একটি চক্র আছে
- তীরের সংখ্যা চলকের সংখ্যার দ্বিগুণের বেশি
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Sublinear space মাপতে input tape শুধু পড়া যায় আর গোনা হয় না; L = SPACE(log n), NL = NSPACE(log n). O(log n) মানে স্থির সংখ্যক counter বা pointer.
- Log-space যন্ত্রের configuration polynomial সংখ্যক, তাই L ⊆ P; {0k1k}, palindrome, binary যোগ, ADFA L-এ।
- PATH ∈ NL (বর্তমান vertex + counter), আর log-space reduction-এর অধীনে PATH NL-complete, configuration graph দিয়ে; তাই NL ⊆ P আর PATH ∈ L ⇔ L = NL.
- L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE আর NL ⊊ PSPACE প্রমাণিত; L = NL আর NL = P খোলা।
- NL = coNL (Immerman–Szelepcsényi): ci গুনে “পথ নেই” প্রমাণ; ফলে context-sensitive language complement-এ বদ্ধ। Undirected PATH ∈ L (Reingold), 2SAT NL-complete.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৪ · Space complexity আর Savitch-এর theoremফিরে দেখুনSPACE আর NSPACE, configuration গোনা আর CANYIELD দিয়ে Savitch-এর প্রমাণ।
- পর্ব ৫৭ · Time complexity আর class Pফিরে দেখুনPATH ∈ P (BFS), আর {0k1k}-এর সময়ের হিসাব।
- পর্ব ৪৫ · Turing machine-এর রূপভেদফিরে দেখুনMulti-tape যন্ত্র, যার একটি রূপ এই পর্বের দুই-tape মডেল।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৬৭-এ hierarchy theorem.
- DSA · পর্ব ৪০ — Breadth-first search (BFS)পাশের ট্র্যাকPATH-এর polynomial সময়ের algorithm, code-সহ।
- DSA · পর্ব ৪৬ — SCC, bridge আর articulation pointপাশের ট্র্যাকSCC দিয়ে 2SAT সমাধান, implication graph-এর ব্যবহার।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৫৯ — Connectivityগণিতের ভিত্তিPath, component আর directed graph-এর সংযোগের গণিত।