এই পর্বে যা শিখবেন
- NTM-এর formal definition, configuration, ⊢ আর গ্রহণ, বর্জন ও loop-এর অর্থ
- Computation tree আঁকা আর একটি input-এ সব শাখা স্তরে স্তরে লেখা
- DFS কেন ব্যর্থ, আর Sipser-এর তিন-tape address পদ্ধতিতে NTM ⇒ DTM-এর প্রমাণ
- König-এর lemma দিয়ে decider NTM-এর simulation-ও যে decider, তার প্রমাণ
- Simulation-এর সূচকীয় দাম, guess and verify নকশা, আর NP-এর দিকে সেতু
১ · Nondeterminism ফিরে দেখা — NFA, PDA, আর এবার Turing machine
Nondeterminism এই কোর্সে নতুন নয়। পর্ব ০৯-এ NFA একই চিহ্নে একাধিক state-এ যেতে পারত, আর অন্তত একটি পথ accept state-এ শেষ হলেই string গৃহীত হতো। পর্ব ৩২-এ PDA wwR-এর মাঝখান অনুমান করত। দুই জায়গায় ফল আলাদা ছিল: পর্ব ১০-এর subset construction দেখাল, NFA আর DFA-র ক্ষমতা সমান; কিন্তু deterministic PDA nondeterministic PDA-র চেয়ে দুর্বল। এবার একই প্রশ্ন সবচেয়ে শক্তিশালী যন্ত্রের জন্য: Turing machine-কে অনুমান করার ক্ষমতা দিলে সে কি নতুন কোনো language চিনতে পারে?
উত্তর না। এই পর্বের মূল উপপাদ্য: প্রতিটি NTM-এর জন্য একটি সাধারণ (deterministic) Turing machine আছে, যা ঠিক একই language চেনে। কিন্তু এই সমতার একটি দাম আছে, আর সেই দামই পরের মডিউলগুলোর সবচেয়ে বিখ্যাত খোলা প্রশ্ন, P বনাম NP-এর জন্ম দেয়। Turing machine-এর মূল সংজ্ঞা, configuration আর tape-এর নিয়ম পর্ব ৪৩-এ, নকশার কৌশল পর্ব ৪৪-এ, আর multi-tape যন্ত্র পর্ব ৪৫-এ আসছে; এখানে সেগুলো ধরে নিয়ে শুধু nondeterminism যোগ করা হলো। গণিতের দিক থেকে প্রথম পরিচয় চাইলে দেখুন ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৫.
বাসায় চাবি হারিয়েছে। আপনি একা হলে ঘরগুলো একটির পর একটি খুঁজবেন। এখন কল্পনা করুন, প্রতিটি দরজার সামনে দাঁড়িয়ে আপনি নিজের একটি করে কপি বানাতে পারেন: একজন রান্নাঘরে, একজন শোবার ঘরে, একজন বারান্দায়। প্রতিটি কপি আবার আলমারির সামনে ভাগ হয়ে যায়, এক কপি ওপরের তাকে, আরেক কপি নিচের তাকে। কোনো একটি কপি চাবি পেলেই খোঁজা সফল; বাকিরা খালি হাতে ফিরলে কিছু আসে যায় না। NTM ঠিক এভাবে “ভাগ হয়”। কিন্তু বাস্তবে আপনার কপি বানানোর ক্ষমতা নেই, তাই একজন মানুষকে (deterministic যন্ত্রকে) সব কপির কাজ পালা করে করতে হয়। সেটি সম্ভব, কিন্তু সময় লাগে অনেক বেশি।
একটি ভুল ধারণা শুরুতেই দূর করা দরকার: NTM কোনো বাস্তব যন্ত্র নয়, আর এলোমেলো (random) পছন্দও করে না। এটি একটি গাণিতিক প্রশ্ন: “অন্তত একটি সফল পছন্দের ক্রম কি আছে?” পছন্দ কে করে, তা সংজ্ঞার অংশ নয়।
২ · Formal definition — N = (Q, Σ, Γ, δ, q0, qaccept, qreject)
এই মডিউলের রীতি: Turing machine হলো 7-tuple, Σ ⊆ Γ, blank ␣ ∈ Γ \ Σ, tape ডান দিকে অসীম, আর প্রথম ঘরে থাকা অবস্থায় L move এলে head জায়গায় থাকে (Sipser-এর রীতি)। Q′ = Q \ {qaccept, qreject}, অর্থাৎ থামার state বাদে বাকিগুলো। NTM-এ বদল একটাই: δ এখন একটি set ফেরত দেয়।
একটি NTM হলো N = (Q, Σ, Γ, δ, q0, qaccept, qreject), যেখানে Q, Σ, Γ, q0, qaccept, qreject সাধারণ TM-এর মতো, আর transition function
δ: Q′ × Γ → P(Q × Γ × {L, R})
P(·) মানে power set. δ(q, a) = {(r1, b1, D1), …, (rk, bk, Dk)} মানে: state q-তে head-এর নিচে a থাকলে যন্ত্র k-টি move-এর যেকোনো একটি নিতে পারে, অর্থাৎ bi লিখে Di দিকে সরে ri-এ যেতে পারে। k = 0 হলে (δ(q, a) = ∅) সেই পথে আর কোনো move নেই; সেটিকে বর্জন হিসেবে ধরা হয়।
Configuration আগের মতোই u q v: tape-এর বিষয়বস্তু uv (তার পরে শুধু blank), state q, আর head v-এর প্রথম চিহ্নে। এই পর্বের code আর stepper-এ state-টি বন্ধনীতে লেখা হয়েছে, যাতে চোখে আলাদা থাকে: 01[q1]1 মানে tape 011, state q1, head তৃতীয় ঘরে। পার্থক্যটি yields সম্পর্কে। DTM-এ C ⊢ C′ একটি function: প্রতিটি C-এর বড়জোর একটি পরের configuration. NTM-এ C ⊢ C′ শুধু একটি relation: δ-এর set-এর কোনো একটি move C থেকে C′ দিলে C ⊢ C′, তাই একটি C-এর অনেক C′ থাকতে পারে।
w-এর ওপর N-এর একটি শাখা (branch) হলো C0 = q0w থেকে শুরু configuration-ক্রম C0 ⊢ C1 ⊢ C2 ⊢ ⋯, যা হয় একটি থামার configuration-এ শেষ হয়, নয়তো অসীম।
১. N w-কে গ্রহণ করে, যদি অন্তত একটি শাখা একটি accepting configuration-এ (state qaccept) পৌঁছায়। L(N) = {w : N w-কে গ্রহণ করে}.
২. N w-কে বর্জন করে, যদি প্রতিটি শাখা থামে আর কোনোটিই গ্রহণ না করে।
৩. বাকি ক্ষেত্রে (কোনো শাখা গ্রহণ করে না, কিন্তু অন্তত একটি শাখা অসীম) N w-এ loop করে।
৪. N একটি decider, যদি প্রতিটি input-এ প্রতিটি শাখা থামে।
লক্ষ করুন অসমতাটি। গ্রহণের জন্য একটি সফল শাখাই যথেষ্ট, বাকি শাখা বর্জন করুক বা চিরকাল চলুক। কিন্তু বর্জনের জন্য সব শাখার থামা আর হারা লাগে। একটি শাখা “reject” বললেই NTM-এর উত্তর “না” নয়। এই অসমতা পরে coNP-এর প্রশ্নে (পর্ব ৬২) বড় ভূমিকা নেবে।
চলমান উদাহরণ N1. Σ = {0, 1}, L(N1) = {w : w-এ পাশাপাশি দুটি 1 আছে}. বাজারঘরের একটি সেন্সর-লাইনে “পরপর দুটি 1” মানে দুবার পরপর সতর্কসংকেত; প্রশ্নটি তাই “লগে কোথাও পরপর দুটি সংকেত আছে কি?” N1 বাঁ থেকে ডানে যায়; প্রতিটি 1-এ সে অনুমান করতে পারে “জোড়াটি এখান থেকে শুরু”। একটি অসাবধান শাখাও রাখা হয়েছে: input শেষে blank পেলে যন্ত্র বর্জনও করতে পারে, আবার qloop-এ গিয়ে চিরকাল ডানে হাঁটতেও পারে। এমন শাখা ভুল নকশার ফল হতে পারে, কিন্তু simulation-কে এমন যন্ত্রেও কাজ করতে হবে।
| state, পড়া | পছন্দ ১ | পছন্দ ২ | অর্থ |
|---|---|---|---|
| q0, 0 | (q0, 0, R) | — | এগিয়ে যাওয়া |
| q0, 1 | (q0, 1, R) | (q1, 1, R) | এগোনো, নাকি অনুমান “জোড়া এখানে” |
| q0, ␣ | (qloop, ␣, R) | (qreject, ␣, R) | অসাবধান শাখা, নাকি বর্জন |
| q1, 1 | (qaccept, 1, R) | — | অনুমান সত্য: গ্রহণ |
| q1, 0 বা ␣ | (qreject, ·, R) | — | অনুমান ভুল: এই শাখা বর্জন |
| qloop, ␣ | (qloop, ␣, R) | — | চিরকাল ডানে হাঁটা |
Code-এ qaccept আর qreject-কে qacc আর qrej লেখা হয়েছে। যেকোনো input-এ q0 শাখাটি একসময় শেষের blank-এ পৌঁছায় আর qloop-এ ঢুকতে পারে, তাই N1-এর প্রতিটি input-এ অন্তত একটি অসীম শাখা আছে: N1 decider নয়। তবু এটি L(N1)-কে সঠিকভাবে চেনে (recognize করে): 11-যুক্ত প্রতিটি string-এ একটি গ্রহণকারী শাখা আছে, আর অন্য string-এ কোনো শাখা গ্রহণ করে না। qloop-এর move-টি বাদ দিলে যে যন্ত্র পাওয়া যায়, তাকে বলব N1′; সেটি decider.
সময়ের সংজ্ঞা। Decider NTM-এর running time হলো f(n) = দৈর্ঘ্য n-এর যেকোনো input-এ যেকোনো শাখার সর্বোচ্চ ধাপসংখ্যা। অর্থাৎ সবচেয়ে লম্বা শাখা হিসাব হয়, ভাগ্যবান শাখা নয়। এই সংজ্ঞাই পর্ব ৫৮-এ NP-এর ভিত্তি হবে।
৩ · Computation tree — একটি input-এ সব পথ একসঙ্গে
একটি নির্দিষ্ট input w-এ NTM-এর সব শাখা একসঙ্গে একটি গাছ গড়ে। মূল (root) হলো শুরুর configuration q0w; প্রতিটি node একটি configuration, আর তার সন্তান হলো এক ধাপে যেসব configuration পাওয়া যায়, δ-এর set-এর ক্রম অনুযায়ী পছন্দ ১, পছন্দ ২, …। থামার configuration পাতা (leaf). গাছের প্রতিটি পথ একটি শাখা। NFA-র computation tree-তে প্রতিটি স্তর একটি চিহ্ন পড়া বোঝাত; এখানে প্রতিটি স্তর একটি TM ধাপ, আর একটি শাখা অসীম লম্বাও হতে পারে।
b = N-এর সর্বোচ্চ branching factor, অর্থাৎ সব (q, a)-এর ওপর |δ(q, a)|-এর সর্বোচ্চ মান; δ সসীম বলে b সসীম। গাছের প্রতিটি node-এর বড়জোর b-টি সন্তান। Root থেকে একটি node-এ যাওয়ার পছন্দগুলোর ক্রম, যেমন 1, 2, 1, হলো সেই node-এর address “121”, যা {1, …, b}-এর ওপর একটি string. Root-এর address ε.
N1-এর computation tree, input 011
প্রতিটি বাক্স একটি configuration; তীরের পাশে পছন্দের নম্বর। সবুজ পথ গ্রহণকারী শাখা, address 121. বাঁ দিকের হলুদ শাখা কখনো থামে না।
নিচের stepper গাছটি স্তরে স্তরে খোলে, ঠিক যেভাবে একটি BFS খোলে: আগে স্তর ০-এর সব node, তারপর স্তর ১-এর সব, এভাবে। বাঁ পাশে উজ্জ্বল লাইন দেখায়, সেই ধাপে N1-এর কোন নিয়ম কাজে লাগল।
1q0,0 → (q0,0,R)2q0,1 → (q0,1,R) / (q1,1,R)3q0,␣ → (qloop,␣,R) / (qrej,␣,R)4q1,1 → (qacc,1,R)5q1,0 বা ␣ → (qrej,·,R)6qloop,␣ → (qloop,␣,R)
| স্তর | |
| configuration | |
| node এই স্তরে |
- স্তর ০. শুরুর configuration [q0]011: state q0, head প্রথম ঘরে, নিচে 0. এখনো কোনো পছন্দ হয়নি।
- স্তর ১. δ(q0, 0)-এ একটিই move, তাই গাছ এখানে ভাগ হয় না। 0 লিখে ডানে: 0[q0]11.
- স্তর ২. নিচে 1, আর δ(q0, 1)-এ দুটি move. পছন্দ ১: q0-তে থেকে এগোনো, 01[q0]1. পছন্দ ২: অনুমান “জোড়া এখান থেকে শুরু”, 01[q1]1. গাছে প্রথম ভাগ।
- স্তর ৩. 01[q0]1 আবার দুই ভাগ: 011[q0]␣ আর 011[q1]␣. আর 01[q1]1-এর নিচে 1, অনুমান সত্য: 011[qacc]␣. একটি শাখা গ্রহণ করেছে, তাই 011 ∈ L(N1), address 121 (পছন্দ ১, ২, ১).
- স্তর ৪. সংজ্ঞার জন্য আর দেখার দরকার নেই, তবু গাছটি থামে না। 011[q1]␣-এর নিচে blank, অনুমান ভুল: বর্জন। 011[q0]␣ দুই ভাগ: বর্জন, আর qloop. স্তর ৫ থেকে শুধু qloop শাখাটি বেঁচে থাকে আর প্রতি স্তরে এক ঘর ডানে যায়, চিরকাল।
এবার একই কাজ Python-এ। ব্লকটি N1-কে একটি dict হিসেবে রাখে, যেখানে (state, চিহ্ন) থেকে move-এর একটি তালিকা পাওয়া যায়; তালিকার ক্রমই পছন্দের নম্বর। bfs function গাছটি স্তরে স্তরে খোলে। গাছ অসীম হতে পারে, তাই একটি ধাপের সীমা (step cap) রাখা হয়েছে: সীমার মধ্যে উত্তর না এলে ফল “NO ANSWER (cap)”, যার মানে “এখনো জানি না”, বর্জন নয়। শেষে দৈর্ঘ্য ৮ পর্যন্ত প্রতিটি string-এ ফলটি “w-এ 11 আছে” সংজ্ঞার সঙ্গে brute force-এ মেলানো হয়েছে। সীমা |w| + 3 নেওয়া নিরাপদ, কারণ গ্রহণকারী শাখা কখনো |w|-এর বেশি ধাপ নেয় না।
from itertools import product
B = "␣" # blank; a halting state has no moves
N1 = {("q0", "0"): [("q0", "0", "R")],
("q0", "1"): [("q0", "1", "R"), ("q1", "1", "R")], # go on, or GUESS
("q0", B): [("qloop", B, "R"), ("qrej", B, "R")], # careless branch
("q1", "1"): [("qacc", "1", "R")],
("q1", "0"): [("qrej", "0", "R")], ("q1", B): [("qrej", B, "R")],
("qloop", B): [("qloop", B, "R")]}
def start(w): return ("q0", w + B, 0) # (state, tape, head)
def moves(D, c): # all children of c, in order
q, t, h = c; out = []
for r, x, m in D.get((q, t[h]), []):
t2 = t[:h] + x + t[h + 1:]
h2 = h + 1 if m == "R" else max(h - 1, 0) # left end: stay put
out.append((r, t2 + B if h2 == len(t2) else t2, h2))
return out
def show(c): # u[q]v
q, t, h = c
t = t.rstrip(B).ljust(h + 1, B)
return t[:h] + "[" + q + "]" + t[h:]
def bfs(D, w, cap, verbose=False): # level by level, step cap
level = [start(w)]
for d in range(cap + 1):
if verbose: print(d, " ".join(show(c) for c in level))
if any(c[0] == "qacc" for c in level): return "ACCEPT", d
level = [n for c in level for n in moves(D, c)]
if not level: return "REJECT", d # every branch halted
return "NO ANSWER (cap)", cap
print(bfs(N1, "011", 10, verbose=True))
print(bfs(N1, "010", 10))
words = ["".join(t) for k in range(9) for t in product("01", repeat=k)]
res = {w: bfs(N1, w, len(w) + 3)[0] for w in words}
print(len(words), "strings:", sum(r == "ACCEPT" for r in res.values()),
"accepted, all agree with '11 in w':",
all((r == "ACCEPT") == ("11" in w) for w, r in res.items()))আসল আউটপুট (ব্রাউজারের Python):
0 [q0]011
1 0[q0]11
2 01[q0]1 01[q1]1
3 011[q0]␣ 011[q1]␣ 011[qacc]␣
('ACCEPT', 3)
('NO ANSWER (cap)', 10)
511 strings: 369 accepted, all agree with '11 in w': True
প্রথম চারটি লাইন stepper-এর স্তর ০–৩-এর সঙ্গে হুবহু মেলে, আর স্তর ৩-এ গ্রহণ। 010-এ ১০ স্তর পরেও উত্তর নেই: এর কোনো শাখা গ্রহণ করে না, কিন্তু qloop শাখাটি বেঁচে থাকে, তাই “সব শাখা থেমেছে” অবস্থাও আসে না। এটিই loop-এর চেহারা; simulator সীমা না রাখলে এখানে চিরকাল চলত। দৈর্ঘ্য ০ থেকে ৮ পর্যন্ত ৫১১টি string-এর ৩৬৯টি গৃহীত, আর প্রতিটি ফল সংজ্ঞার সঙ্গে মেলে। হাতেও মেলানো যায়: 11-বিহীন string-এর সংখ্যা দৈর্ঘ্য n-এ একটি Fibonacci সংখ্যা (1, 2, 3, 5, 8, 13, 21, 34, 55), যোগফল ১৪২, আর 511 − 142 = 369.
৪ · DFS কেন ব্যর্থ হয় — অসীম শাখার ফাঁদ
একটি গাছে কিছু খোঁজার দুটি স্বাভাবিক উপায়। DFS (depth-first search) একটি পথ ধরে যতদূর যায়, শেষ হলে পিছিয়ে এসে পরের পথ ধরে। BFS স্তরে স্তরে খোঁজে। Programming-এ DFS প্রায়ই সহজ আর কম স্মৃতি খায়, আর recursion দিয়ে লিখতেও সুবিধা। কিন্তু NTM-এর গাছে একটি শাখা অসীম হতে পারে, আর DFS সেই শাখায় ঢুকলে আর কখনো ফেরে না: “শাখা শেষ হলে পিছিয়ে আসা” কখনো ঘটে না। নিচের stepper N1-এ input 011 নিয়ে DFS চালায়, প্রতিবার পছন্দ ১ আগে।
1c = stack থেকে ওপরেরটি তোলা2c-তে qacc? তাহলে ACCEPT3c-এর সন্তানদের উল্টো ক্রমে push
| এখন দেখছে | |
| stack-এ অপেক্ষায় | |
| দেখা configuration |
- শুরু। Stack-এ শুধু root [q0]011. সেটি তুলে দেখা হলো; একটিই সন্তান, push করা হলো।
- 0 পেরোনো। 0[q0]11-এর দুটি সন্তান। উল্টো ক্রমে push, তাই পছন্দ ১ (01[q0]1) ওপরে, পছন্দ ২ (01[q1]1) তার নিচে।
- পছন্দ ১ আগে। 01[q0]1 দেখা হলো। গ্রহণকারী শাখার শুরু, 01[q1]1, stack-এর তলায় অপেক্ষা করছে, মাত্র এক ধাপ দূরে।
- আবার পছন্দ ১. 011[q0]␣: head blank-এ। দুটি সন্তান: qloop (পছন্দ ১) আর বর্জন (পছন্দ ২)। Stack-এ এখন অপেক্ষমাণ তিনটি।
- ফাঁদে পা। 011␣[qloop]␣ তোলা হলো। এর একটিই সন্তান, আরও এক ঘর ডানে একই state.
- চলতেই থাকে। প্রতিবার ঠিক একটি সন্তান push হয় আর সেটিই পরেরবার ওঠে। অপেক্ষমাণ তিনটি configuration কখনো ওপরে আসে না।
- সীমা। ১০০০টি configuration দেখার পরেও DFS qloop-এ, head ঘর 999-এ। গ্রহণকারী শাখা, যা BFS স্তর ৩-এ পেয়েছিল, DFS কখনো ছোঁয়নি। সীমা না থাকলে DFS কোনো উত্তরই দিত না, যদিও 011 ∈ L(N1).
অর্থাৎ DFS দিয়ে বানানো “simulator” একটি গৃহীত string-এও চিরকাল চলতে পারে, তাই এটি L(N)-কে চেনে না। পছন্দের ক্রম উল্টে দিলে এই উদাহরণ বেঁচে যায়, কিন্তু অন্য NTM-এ অন্য ক্রমে একই ফাঁদ বানানো যায়; কোনো নির্দিষ্ট ক্রম সব যন্ত্রে নিরাপদ নয়। BFS-এর গ্যারান্টি অন্যরকম: গ্রহণকারী শাখা যদি k ধাপে গ্রহণ করে, তাহলে BFS স্তর k-তে পৌঁছানোর আগে মাত্র সসীম সংখ্যক node দেখে (বড়জোর 1 + b + ⋯ + bk), তাই একসময় সেটি পাবেই, অন্য শাখা যত অসীমই হোক।
নিচের JavaScript ব্লক গাছটি লেখার আকারে আঁকে, একটি গভীরতার সীমা (depth cap) সহ: সীমায় পৌঁছানো শাখার পাশে “... (cap)” লেখা থাকে। প্রতিটি লাইনের শুরুর সংখ্যা সেই ধাপের পছন্দ, তাই root থেকে কোনো node পর্যন্ত সংখ্যাগুলো পরপর পড়লে তার address পাওয়া যায়।
// Text drawing of an NTM computation tree, with a depth cap.
const B = "␣";
const N1 = { // "state,symbol" -> list of [next, write, move]
"q0,0": [["q0", "0", "R"]],
"q0,1": [["q0", "1", "R"], ["q1", "1", "R"]], // go on, or guess "11 here"
"q0,␣": [["qloop", B, "R"], ["qrej", B, "R"]],
"q1,1": [["qacc", "1", "R"]],
"q1,0": [["qrej", "0", "R"]], "q1,␣": [["qrej", B, "R"]],
"qloop,␣": [["qloop", B, "R"]] };
const kids = ([q, t, h]) => (N1[q + "," + t[h]] || []).map(([r, x, m]) => {
const t2 = t.slice(0, h) + x + t.slice(h + 1);
const h2 = m === "R" ? h + 1 : Math.max(h - 1, 0); // left end: stay put
return [r, h2 === t2.length ? t2 + B : t2, h2];
});
const show = ([q, t, h]) => { // u[q]v, trailing blanks trimmed
t = t.replace(/␣+$/, "").padEnd(h + 1, B);
return t.slice(0, h) + "[" + q + "]" + t.slice(h);
};
function draw(w, cap) {
const n = { nodes: 1, accept: 0, reject: 0, cut: 0 }, root = ["q0", w + B, 0];
console.log(`N1 on ${w}: ` + show(root));
(function rec(c, pad, depth) {
kids(c).forEach((k, i, ks) => {
const last = i === ks.length - 1;
let tag = k[0] === "qacc" ? " ACCEPT" : k[0] === "qrej" ? " reject" : "";
if (!tag && depth + 1 === cap) { tag = " ... (cap)"; n.cut++; }
n.nodes++; n.accept += k[0] === "qacc"; n.reject += k[0] === "qrej";
console.log(pad + (last ? "└─" : "├─") + (i + 1) + " " + show(k) + tag);
if (!tag) rec(k, pad + (last ? " " : "│ "), depth + 1);
});
})(root, "", 0);
console.log(` ${n.nodes} nodes, ${n.accept} accepting, ` +
`${n.reject} rejecting, ${n.cut} cut at depth ${cap}`);
}
draw("011", 5); draw("10", 5);আসল আউটপুট (ব্রাউজারের JavaScript):
N1 on 011: [q0]011
└─1 0[q0]11
├─1 01[q0]1
│ ├─1 011[q0]␣
│ │ ├─1 011␣[qloop]␣
│ │ │ └─1 011␣␣[qloop]␣ ... (cap)
│ │ └─2 011␣[qrej]␣ reject
│ └─2 011[q1]␣
│ └─1 011␣[qrej]␣ reject
└─2 01[q1]1
└─1 011[qacc]␣ ACCEPT
11 nodes, 1 accepting, 2 rejecting, 1 cut at depth 5
N1 on 10: [q0]10
├─1 1[q0]0
│ └─1 10[q0]␣
│ ├─1 10␣[qloop]␣
│ │ └─1 10␣␣[qloop]␣
│ │ └─1 10␣␣␣[qloop]␣ ... (cap)
│ └─2 10␣[qrej]␣ reject
└─2 1[q1]0
└─1 10[qrej]␣ reject
9 nodes, 0 accepting, 2 rejecting, 1 cut at depth 5
011-এর গাছটি ছবি ৪৬.১-এর সঙ্গে হুবহু এক: ACCEPT লাইনে পৌঁছাতে পছন্দগুলো 1, 2, 1, অর্থাৎ address 121. লক্ষ করুন, এই ব্লক নিজেই recursion দিয়ে DFS করে আঁকছে; সেটি নিরাপদ শুধু গভীরতার সীমা আছে বলে। 10-এ কোনো ACCEPT নেই, দুটি শাখা বর্জন করে, আর qloop শাখা সীমায় কাটা পড়ে। তাই 10 ∉ L(N1), কিন্তু N1 এটি বর্জন করে না, loop করে; আর সাধারণ NTM-এ একটি কাটা শাখা পরে কী করবে, তা আগে থেকে জানার উপায় নেই। দুটি ইনপুট বদলে নিজে চালিয়ে দেখুন, যেমন draw("0110", 6).
৫ · Deterministic simulation — Sipser-এর তিন-tape address পদ্ধতি
BFS-এর ধারণা পরিষ্কার, কিন্তু একটি Turing machine কীভাবে “একটি স্তরের সব configuration” মনে রাখবে? একটি উপায় হলো সব configuration একটি tape-এ পাশাপাশি লিখে রাখা (queue). Sipser-এর বইয়ে আরও সরল একটি কৌশল আছে, যাতে কিছুই মনে রাখতে হয় না: প্রতিটি node-কে তার address দিয়ে চেনা, আর প্রতিবার root থেকে নতুন করে চালানো। Address-গুলো shortlex ক্রমে নিলে (ε, 1, 2, …, b, 11, 12, …) node-গুলো ঠিক BFS-এর ক্রমে আসে।
প্রতিটি nondeterministic Turing machine N-এর জন্য একটি deterministic Turing machine D আছে, যাতে L(D) = L(N).
গঠন। D-এর তিনটি tape (তিন-tape যন্ত্র এক-tape যন্ত্রের সমান শক্তিশালী, পর্ব ৪৫-এর multi-tape উপপাদ্য)। Tape ১-এ input w, যা কখনো বদলায় না। Tape ২ হলো N-এর tape-এর একটি কাজের কপি, একটি শাখা চালানোর জন্য। Tape ৩-এ একটি address, Σb = {1, …, b}-এর ওপর একটি string. D-এর কাজ:
- শুরুতে tape ১-এ w; tape ৩-এ address ε.
- Tape ২ মুছে tape ১ থেকে w কপি করা।
- Tape ২-এ N-কে চালানো, প্রতিটি ধাপের আগে tape ৩-এর পরের চিহ্ন দেখে ঠিক করা কোন পছন্দ নেওয়া হবে। Tape ৩-এর চিহ্ন ফুরিয়ে গেলে, পছন্দটি অবৈধ হলে (যেমন δ-এ মাত্র ১টি move অথচ চিহ্ন 2), বা একটি rejecting configuration এলে ধাপ ৪-এ যাওয়া। Accepting configuration এলে D গ্রহণ করে।
- Tape ৩-এর address-কে shortlex ক্রমের পরের string দিয়ে বদলানো, তারপর ধাপ ২-এ ফেরা।
নিচের stepper N1-এ input 011 নিয়ে D-এর প্রথম দশটি address দেখায়। “invalid” মানে address-টি গাছের কোনো node নয়; “running” মানে node আছে, কিন্তু এখনো থামেনি।
1tape ৩ = ε দিয়ে শুরু2tape ২ = w-এর নতুন কপি3tape ৩ অনুযায়ী N চালানো4qacc এলে ACCEPT5নইলে tape ৩ = পরের address
| address | |
| ফল | |
| শেষ configuration | |
| মোট অনুকৃত ধাপ |
- ε. শূন্য ধাপ চালানো হলো: শুধু root [q0]011. থামেনি, তাই পরের address.
- 1. এক ধাপ, পছন্দ ১: 0[q0]11. এখনো চলছে।
- 2. প্রথম ধাপেই সমস্যা: δ(q0, 0)-এ মাত্র একটি move, পছন্দ ২ নেই। Address অবৈধ, শূন্য ধাপ খরচ।
- 11. আবার w-এর নতুন কপি থেকে শুরু; দুই ধাপ, দুবারই পছন্দ ১: 01[q0]1. মোট ধাপ এখন ৩.
- 12. দ্বিতীয় ধাপে পছন্দ ২, অর্থাৎ অনুমান: 01[q1]1. থামেনি।
- 21. প্রথম চিহ্ন 2, আবার ধাপ ১-এই অবৈধ।
- 22. একই কারণে অবৈধ। দৈর্ঘ্য ২-এর সব address শেষ; স্তর ২-এর দুটি node-ই চলমান।
- 111. তিন ধাপ: 011[q0]␣. মোট ধাপ ৮.
- 112. তিন ধাপ: 011[q1]␣. মোট ১১. লক্ষ করুন, প্রতিটি address-এ D root থেকে নতুন করে সব ধাপ আবার চালায়।
- 121. পছন্দ ১, ২, ১: 011[qacc]␣. D গ্রহণ করে। দশটি address চেষ্টা আর মোট ১৪টি অনুকৃত ধাপ লেগেছে; BFS-এ গ্রহণকারী node-টি স্তর ৩-এ।
শেষ address 121-এর ভেতরে তিনটি tape কীভাবে একসঙ্গে কাজ করে, নিচের stepper তা ঘর ধরে দেখায়। ^ চিহ্ন প্রতিটি tape-এ head-এর অবস্থান।
1tape ৩: পরের address বসানো2tape ২ মুছে w কপি3tape ৩-এর চিহ্ন পড়ে N-এর এক ধাপ4qacc: D ACCEPT
| tape ১ (input) | |
| tape ২ (N-এর কপি) | |
| tape ৩ (address) |
- পরের address. আগের address 112-এর শাখা চলমান অবস্থায় থেমেছিল। Shortlex ক্রমে পরের string 121 (112-কে b = 2 ভিত্তির একটি “সংখ্যা” ধরে এক বাড়ানো, যেখানে অঙ্ক 1 আর 2).
- নতুন কপি। Tape ২-এ আগের শাখার যা ছিল, সব মুছে tape ১ থেকে 011 কপি। Simulation-এর head প্রথম ঘরে, state q0.
- চিহ্ন 1. Tape ৩-এর প্রথম চিহ্ন 1. δ(q0, 0)-এর প্রথম move: 0 লিখে ডানে, 0[q0]11.
- চিহ্ন 2. δ(q0, 1)-এ দুটি move; দ্বিতীয়টি নেওয়া হলো: q1-এ গিয়ে ডানে, 01[q1]1. এটিই N-এর “ভাগ্যবান অনুমান”, এখানে address-এর একটি অঙ্ক মাত্র।
- চিহ্ন 1, গ্রহণ। δ(q1, 1)-এর একমাত্র move: 011[qacc]␣. N গ্রহণ করেছে, তাই D গ্রহণ করে আর থামে।
প্রমাণ (L(D) = L(N)):
- ধরুন w ∈ L(N). তাহলে কোনো শাখা কোনো k ধাপে qaccept-এ পৌঁছায়; তার পছন্দগুলোর ক্রম একটি address a, |a| = k. — গ্রহণের সংজ্ঞা ২.২
- Shortlex ক্রমে a-এর আগে মাত্র সসীম সংখ্যক string আছে (বড়জোর 1 + b + ⋯ + bk-টি)। — দৈর্ঘ্য ≤ k-এর string গোনা
- প্রতিটি address-এর simulation বড়জোর |address| ধাপ চলে, তাই প্রতিটি সসীম সময়ে শেষ হয়। — ধাপ ৩: tape ৩-এর চিহ্ন ফুরোলে থামা
- অতএব D সসীম সময়ে address a-তে পৌঁছায়, আর তখন tape ২-এ ঠিক সেই শাখা চলে qaccept-এ পৌঁছায়; D গ্রহণ করে। (তার আগেই অন্য কোনো address-এ গ্রহণ হলেও D গ্রহণ করে।) — ধাপ ১–৩
- উল্টো দিকে, D গ্রহণ করে শুধু তখন, যখন কোনো address-এর simulation একটি accepting configuration-এ পৌঁছায়। সেই simulation N-এর একটি আসল শাখা, কারণ প্রতিটি ধাপ δ-এর একটি বৈধ move. তাই w ∈ L(N). — ধাপ ৩-এর গঠন
- D তিন-tape যন্ত্র; পর্ব ৪৫-এর উপপাদ্যে একে এক-tape DTM-এ রূপান্তর করা যায়, language না বদলে। ∎
একটি language Turing-recognizable, যদি এবং কেবল যদি কোনো nondeterministic Turing machine তাকে চেনে। (একটি দিক উপপাদ্য ৫.১; অন্য দিকটি সহজ, কারণ প্রতিটি DTM নিজেই একটি NTM, যার প্রতিটি δ-set-এ বড়জোর একটি move.)
লক্ষ করুন, w ∉ L(N) হলে D কখনো থামে না: সে চিরকাল নতুন address চেষ্টা করে। N1-এর মতো যন্ত্রে এটি অনিবার্য, কারণ N নিজেই loop করে। Decider-এর প্রশ্ন অংশ ৬-এ।
from itertools import product
def run_address(D, w, addr): # tape 3 = addr, tape 2 = fresh copy of w
c = start(w)
for i, a in enumerate(addr):
if c[0] in ("qacc", "qrej"): return "halted early", c, i
kids = moves(D, c)
if int(a) > len(kids): return "invalid", c, i
c = kids[int(a) - 1]
return {"qacc": "ACCEPT", "qrej": "reject"}.get(c[0], "running"), c, len(addr)
def address_sim(D, w, b=2, cap=12, verbose=False):
tried = steps = 0
for k in range(cap + 1): # shortlex: e, 1, 2, 11, 12, ...
for t in product("123456789"[:b], repeat=k):
a = "".join(t); tried += 1
res, c, s = run_address(D, w, a); steps += s
if verbose: print(f" {a or 'e':5} {res:8} {show(c)}")
if res == "ACCEPT": return f"ACCEPT at {a}", tried, steps
return "NO ANSWER (cap)", tried, steps
print(address_sim(N1, "011", verbose=True))
for w in ["11", "0110", "0000011", "010"]:
print(f"{w:8}", address_sim(N1, w, cap=8))
def dfs_first_choice(D, w, cap): # always try choice 1 first
todo, n = [start(w)], 0
while todo and n < cap:
c = todo.pop(); n += 1
if c[0] == "qacc": return "ACCEPT", n
todo += reversed(moves(D, c))
return "NO ANSWER (cap)", n, f"[{c[0]}] on cell {c[2]}"
print("DFS:", dfs_first_choice(N1, "011", 1000))আসল আউটপুট (ব্রাউজারের Python; এই ব্লক আগের ব্লকের N1, start, moves আর show ব্যবহার করে, তাই আগে সেটি চালান):
e running [q0]011
1 running 0[q0]11
2 invalid [q0]011
11 running 01[q0]1
12 running 01[q1]1
21 invalid [q0]011
22 invalid [q0]011
111 running 011[q0]␣
112 running 011[q1]␣
121 ACCEPT 011[qacc]␣
('ACCEPT at 121', 10, 14)
11 ('ACCEPT at 21', 6, 8)
0110 ('ACCEPT at 121', 10, 14)
0000011 ('ACCEPT at 1111121', 130, 142)
010 ('NO ANSWER (cap)', 511, 723)
DFS: ('NO ANSWER (cap)', 1000, '[qloop] on cell 999')
প্রথম দশ লাইন address stepper-এর দশটি ধাপ, “e” মানে ε. গ্রহণ address 121-এ, দশটি চেষ্টায়, মোট ১৪টি অনুকৃত ধাপে। 0000011-এ গ্রহণকারী শাখা ৭ ধাপের (পাঁচটি 0 পেরিয়ে, তারপর অনুমান), আর D-কে ১৩০টি address চেষ্টা করতে হয়েছে: দৈর্ঘ্য ৬ পর্যন্ত সব 27 − 1 = 127টি, তারপর দৈর্ঘ্য ৭-এর তিনটি (1111111, 1111112, 1111121). এক ধাপ বেশি গভীর উত্তর মানে মোটামুটি দ্বিগুণ কাজ, এটিই সূচকীয় দামের প্রথম ছায়া। 010-এ দৈর্ঘ্য ৮ পর্যন্ত সব ৫১১টি address শেষ, তবু উত্তর নেই; D নিজে কোনো সীমা মানে না, তাই আসল D এখানে চিরকাল চলত। শেষ লাইন অংশ ৪-এর DFS stepper-এর শেষ ধাপ: ১০০০টি configuration-এর পরেও qloop-এ।
একটি সত্যিকারের library দিয়ে যাচাই। নিজের simulator-এর ভুল ধরতে একই N1 একটি স্বাধীন library-তে চালানো হলো। automata-lib (MIT licence) Python-এ DFA, NFA, PDA আর Turing machine-এর class দেয়; এর NTM class প্রতিটি ধাপে সব জীবিত configuration-এর একটি set রাখে, অর্থাৎ স্তরে স্তরে BFS, address ছাড়া। Library-টিতে কোনো network বা usage-reporting কোড নেই। Library-র নিজস্ব কোনো ধাপের সীমা নেই, তাই 010-এর জন্য script নিজে ৮ round পরে থামায়। Library-র tape দুই দিকে অসীম, কিন্তু N1 কখনো বাঁয়ে যায় না বলে পার্থক্য পড়ে না। uv দিয়ে বানানো একটি ছোট প্রকল্পে script-এর মূল অংশ:
from automata.tm.ntm import NTM
B = "␣"
def make(with_loop): # {state: {read: {(next, write, move), ...}}}
d = {"q0": {"0": {("q0", "0", "R")},
"1": {("q0", "1", "R"), ("q1", "1", "R")},
B: {("qrej", B, "R")}},
"q1": {"1": {("qacc", "1", "R")}, "0": {("qrej", "0", "R")},
B: {("qrej", B, "R")}}}
if with_loop:
d["q0"][B].add(("qloop", B, "R"))
d["qloop"] = {B: {("qloop", B, "R")}}
return NTM(states={"q0", "q1", "qloop", "qacc", "qrej"},
input_symbols={"0", "1"}, tape_symbols={"0", "1", B},
transitions=d, initial_state="q0", blank_symbol=B,
final_states={"qacc"})
N1 = make(True)
for i, S in enumerate(N1.read_input_stepwise("011")):
print(i, sorted(show(c) for c in S)) # show(): u[q]v, as on this page
# ... the same for "010", stopped by our own cap after 8 rounds
N1d = make(False) # the decider version: no looping branch
# ... N1d.accepts_input(w) on all 511 strings of length 0 to 8সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13):
~/bazarghar-toc$ uv run python run_ntm.py
automata-lib 9.2.0
0 ['[q0]011']
1 ['0[q0]11']
2 ['01[q0]1', '01[q1]1']
3 ['011[q0]␣', '011[q1]␣', '011[qacc]␣']
--- 010 on N1 (has a looping branch), our cap = 8 rounds ---
0 ['[q0]010']
4 ['010␣[qloop]␣', '010␣[qrej]␣']
8 ['010␣␣␣␣␣[qloop]␣']
still 1 live configuration(s) after 8 rounds: no answer
511 strings, 369 accepted, agree with '11 in w': True
Library-র round 0–3 আমাদের bfs-এর স্তর ০–৩-এর সঙ্গে হুবহু এক, আর round 3-এ qacc দেখে সে থামে। 010-এ round 4-এ দুটি configuration: একটি বর্জন (পরের round-এ বাদ), একটি qloop. Round 8-এও একটি configuration বেঁচে আছে; library নিজে থামত না, ঠিক N1-এর loop-এর মতো। Decider রূপ N1′-এ (qloop ছাড়া) দৈর্ঘ্য ৮ পর্যন্ত ৫১১টি string-এ ৩৬৯টি গৃহীত, প্রতিটি সংজ্ঞার সঙ্গে মেলে, আমাদের সংখ্যার সঙ্গেও।
৬ · Decider NTM আর König-এর lemma
উপপাদ্য ৫.১-এর D, N decider হলেও, কখনো থামে না যখন w ∉ L(N): সে নতুন address চেষ্টা করেই যায়। একটি decidable language-এর জন্য আমাদের এমন D চাই, যা প্রতিটি input-এ থামে। সমাধানের চাবি একটি পুরোনো গ্রাফ-তত্ত্বের ফল।
একটি rooted tree-র প্রতিটি node-এর সন্তান সসীম সংখ্যক হলে (finitely branching), আর tree-টি অসীম হলে, root থেকে শুরু একটি অসীম পথ আছে। সমতুল্যভাবে: finitely branching tree-র প্রতিটি পথ সসীম হলে tree-টি নিজেই সসীম।
প্রমাণ:
- ধরুন tree T অসীম আর finitely branching. v0 = root; v0-এর নিচে (নিজেসহ) অসীম সংখ্যক node আছে। — T অসীম
- ধরুন vi-এর নিচে অসীম সংখ্যক node. vi-এর সন্তান সসীম, আর vi-এর নিচের প্রতিটি node (vi নিজে বাদে) কোনো একটি সন্তানের নিচে। — finitely branching
- তাই কোনো একটি সন্তানের নিচে অসীম সংখ্যক node; তাকে vi+1 বলুন। — pigeonhole: সসীম সংখ্যক অংশে ভাগ করা অসীম set-এর একটি অংশ অসীম
- Induction-এ v0, v1, v2, … একটি অসীম পথ। ∎
N একটি decider NTM হলে একটি deterministic decider D আছে, যাতে L(D) = L(N). অতএব একটি language decidable, যদি এবং কেবল যদি কোনো NTM decider তাকে decide করে।
প্রমাণের রূপরেখা: w-এ N-এর computation tree finitely branching (প্রতি node-এ বড়জোর b সন্তান), আর N decider বলে এর প্রতিটি পথ সসীম। König-এর lemma বলে tree-টি সসীম, তাই এর একটি সর্বোচ্চ গভীরতা h আছে। এবার D-কে একটু বদলান: দৈর্ঘ্য k-এর সব address শেষ করার পর D দেখে, এদের কোনোটির simulation কি tape ৩-এর চিহ্ন ফুরোনোর সময়ও “running” ছিল? যদি না থাকে, তাহলে গভীরতা k-তে কোনো চলমান node নেই, অর্থাৎ গাছ পুরো দেখা শেষ; কোনো শাখা গ্রহণ না করে থাকলে D বর্জন করে। k = h + 1 হলে এই শর্ত অবশ্যই সত্য, তাই D সসীম সময়ে থামে। গ্রহণের দিক উপপাদ্য ৫.১-এর মতোই। ∎
N1′-এর জন্য এই বদলানো D প্রতিটি input-এ থামে; N1-এর জন্য থামে না, কারণ qloop শাখা প্রতিটি গভীরতায় “running” থাকে। পার্থক্যটি D-তে নয়, N-এ: König-এর lemma-র শর্ত, “প্রতিটি পথ সসীম”, N1-এ ভাঙা। “Finitely branching” শর্তটিও জরুরি: একটি root-এর অসীম সংখ্যক সন্তান থাকলে (প্রতিটি থেকে সসীম পথ) গাছ অসীম, অথচ কোনো অসীম পথ নেই। NTM-এ δ সসীম বলে এই সমস্যা কখনো ওঠে না।
সাবধান: NTM-এর “বর্জন” আর DTM-এর “বর্জন” এক জিনিস নয়। একটি NTM decider w বর্জন করে যখন সব শাখা বর্জন করে। তাই একটি NTM decider-এর accept আর reject state অদলবদল করলে complement পাওয়া যায় না: নতুন যন্ত্র w গ্রহণ করবে যদি কোনো শাখা আগে বর্জন করত। DTM-এ এই অদলবদল কাজ করে। Decidable language complement-এ বদ্ধ (পর্ব ৫০), কিন্তু সেই প্রমাণ deterministic decider দিয়ে, উপপাদ্য ৬.২-এর পরে। Polynomial সময়ের NTM-এর জন্য এই অসমতা NP বনাম coNP প্রশ্নের জন্ম দেয় (পর্ব ৬২), যা এখনো খোলা।
৭ · দামের হিসাব — সূচকীয় সময়, guess and verify আর NP-এর সেতু
ক্ষমতা সমান, কিন্তু সময়? ধরুন N একটি decider NTM, যার প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ বড়জোর t(n) ধাপে থামে, আর branching factor b. গাছের গভীরতা ≤ t(n), তাই node বড়জোর 1 + b + ⋯ + bt(n) ≤ bt(n)+1. Address পদ্ধতি প্রতিটি node-এর জন্য root থেকে বড়জোর t(n) ধাপ চালায়।
t(n) ≥ n হলে, t(n) সময়ের প্রতিটি single-tape NTM decider-এর একটি সমতুল্য single-tape deterministic decider আছে, যার সময় 2O(t(n)).
প্রমাণের রূপরেখা: তিন-tape D-র সময় O(t(n) · bt(n)), প্রতিটি address-এর কপি, simulation আর address বাড়ানো মিলিয়ে। t(n) · bt(n) = 2log t(n) + t(n) log b = 2O(t(n)). পর্ব ৪৫-এর রূপান্তর তিন-tape যন্ত্রের T ধাপ এক-tape-এ O(T2) ধাপে চালায়, আর (2O(t(n)))2 = 2O(2t(n)) = 2O(t(n)). ∎ (Sipser-এর বইয়ে এটি Theorem 7.11.)
| b | t | দৈর্ঘ্য ≤ t-এর address | অনুকৃত ধাপের ঊর্ধ্বসীমা (Σ i · bi) |
|---|---|---|---|
| 2 | 10 | 2,047 | 18,434 |
| 2 | 20 | 2,097,151 | 39,845,890 |
| 2 | 30 | 2,147,483,647 | 62,277,025,794 |
| 3 | 10 | 88,573 | 841,449 |
| 3 | 20 | 5,230,176,601 | 101,988,443,730 |
৩০ ধাপের একটি দুই-পছন্দের NTM, যা নিজে মুহূর্তে শেষ হয়, তার deterministic simulation-এ ছয় হাজার কোটির বেশি ধাপ লাগতে পারে। (সংখ্যাগুলো একটি ছোট script-এ গোনা।) এই বিস্ফোরণ কি অনিবার্য, নাকি শুধু এই পদ্ধতির দোষ? কেউ জানে না। কোনো চতুর পদ্ধতি সব polynomial-সময়ের NTM-কে polynomial সময়ে অনুকরণ করতে পারলে P = NP হতো; উল্টোটিও সত্য। এটি গণিতের সবচেয়ে বিখ্যাত খোলা প্রশ্নগুলোর একটি (পর্ব ৬৩)। প্রমাণিত শুধু উপপাদ্য ৭.১-এর ঊর্ধ্বসীমা।
Guess and verify. NTM নকশার সবচেয়ে কাজের ছক পর্ব ০৯-এর guess and verify: প্রথমে nondeterministic ভাবে একটি উত্তর-প্রার্থী লিখুন, তারপর deterministic ভাবে যাচাই করুন। উদাহরণ COMPOSITES = {n : n > 1, আর 1 < p < n এমন কোনো p n-কে ভাগ করে}, যেখানে n binary-তে k bit. NTM-এর high-level বর্ণনা: “k-টি bit একটি একটি করে অনুমান করে একটি সংখ্যা p লিখুন; 1 < p < n আর p ভাগ করে n কি না, ভাগ করে দেখুন; হলে গ্রহণ, না হলে বর্জন।” প্রতিটি শাখা k-এর একটি polynomial সময়ে থামে, কারণ অনুমান k ধাপের আর সাধারণ ভাগ মোটামুটি k2 bit-কাজের। কিন্তু গাছে 2k-টি পাতা, আর একটি deterministic simulator-কে সেগুলো খুঁজতে হয়। বাজারঘরের “২০০ কিলোমিটারের মধ্যে সব ঠিকানা ঘুরে আসার কোনো রুট আছে কি?” প্রশ্নও একই ছাঁচে: রুট অনুমান, তারপর দৈর্ঘ্য যোগ করে যাচাই।
# NTM idea for COMPOSITES = {n : n > 1 has a factor 1 < p < n}, n in binary.
# Each branch: guess the k bits of p (k = bits of n), then verify n % p == 0.
def branch(n, p): # one lucky branch: deterministic check
return 1 < p < n and n % p == 0
def bfs_simulation(n): # deterministic simulation of the tree
k, level, visited = n.bit_length(), [0], 1
for depth in range(k): # guessing stage: 2 children per node
level = [2 * p + bit for p in level for bit in (0, 1)]
visited += len(level)
for p in level: # leaves in shortlex order = 0, 1, 2, ...
if branch(n, p): return "composite", k, p, visited
return "prime", k, None, visited
def dfs_simulation(n): # the tree is finite, so DFS is safe
k, visited, todo = n.bit_length(), 0, [(0, 0)]
while todo:
p, d = todo.pop(); visited += 1
if d == k:
if branch(n, p): return visited
else: todo += [(2 * p + 1, d + 1), (2 * p, d + 1)]
return visited
print(" n bits verdict witness p BFS nodes DFS nodes")
for n in [91, 97, 221, 251, 4087, 4093, 65535, 65521]:
verdict, k, p, v = bfs_simulation(n)
print(f" {n:<6} {k:4} {verdict:9} {str(p):9} {v:9} {dfs_simulation(n):9}")আসল আউটপুট (ব্রাউজারের Python):
n bits verdict witness p BFS nodes DFS nodes
91 7 composite 7 255 19
97 7 prime None 255 255
221 8 composite 13 511 32
251 8 prime None 511 511
4087 12 composite 61 8191 130
4093 12 prime None 8191 8191
65535 16 composite 3 131071 21
65521 16 prime None 131071 131071
প্রতিটি শাখা মাত্র k-টি অনুমান আর একটি ভাগ, যেমন 4087-এ ১২টি bit অনুমান করে p = 61, আর 4087 = 61 × 67. কিন্তু simulator-এর কাজ গাছের আকারের সমান: k bit-এ BFS সবসময় 2k+1 − 1টি node তৈরি করে (এই সরল রূপে আগে পুরো স্তর বানানো হয়), আর ৭ থেকে ১৬ bit-এ সংখ্যাটি ২৫৫ থেকে ১,৩১,০৭১. এই NTM decider, তাই গাছ সসীম আর DFS-ও নিরাপদ (অংশ ৬)। Composite সংখ্যায় DFS সবচেয়ে ছোট গুণনীয়কে দ্রুত পৌঁছায় (65535-এ মাত্র ২১টি node), কিন্তু মৌলিক সংখ্যায় দুই পদ্ধতিকেই পুরো গাছ দেখতে হয়, কারণ “কোনো গুণনীয়ক নেই” বলতে প্রতিটি পাতা বর্জিত হওয়া লাগে। এটি অংশ ২-এর অসমতারই ছবি।
একটি সৎ সতর্কতা: এই উদাহরণ শুধু গঠন দেখায়, COMPOSITES-এর সেরা algorithm নয়। Agrawal, Kayal আর Saxena ২০০২ সালে দেখান যে কোনো সংখ্যা মৌলিক কি না, তা polynomial সময়ে নির্ণয় করা যায় (AKS primality test), তাই COMPOSITES ∈ P. কিন্তু গুণনীয়কটি খুঁজে বের করা (factoring) polynomial সময়ে করা যায় কি না, তা জানা নেই। আর অনেক সমস্যায়, যেমন বাজারঘরের রুটের প্রশ্ন, কোনো polynomial algorithm জানা নেই; সেগুলোর কথা পর্ব ৫৮–৬৩-এ।
NP = polynomial সময়ের NTM decider যেসব language decide করে, তাদের শ্রেণি। সমতুল্যভাবে, যেসব language-এর প্রতিটি সদস্যের একটি ছোট certificate (যেমন একটি গুণনীয়ক বা একটি রুট) polynomial সময়ে যাচাই করা যায়। দুই সংজ্ঞার সমতা guess and verify-এরই রূপ: অনুমান করা bit-গুলোই certificate, আর যাচাইয়ের অংশটিই verifier. NP নামের “N” এসেছে nondeterministic থেকে; এটি “non-polynomial” নয়।
| যন্ত্র | Nondeterminism ক্ষমতা বাড়ায়? | Deterministic রূপের দাম |
|---|---|---|
| Finite automaton | না (পর্ব ১০) | state বড়জোর 2n, সময় রৈখিকই থাকে |
| PDA | হ্যাঁ: wwR কোনো DPDA চেনে না (পর্ব ৩৫) | সাধারণভাবে রূপান্তর সম্ভব নয় |
| LBA (রৈখিক tape) | অজানা, ১৯৬০-এর দশক থেকে খোলা | — |
| Turing machine | না (উপপাদ্য ৫.১, ৬.২) | জানা পদ্ধতিতে সময় 2O(t); ভালো করা যায় কি না, খোলা |
আরও গভীরে: সময়ের ক্ষেত্রে সবচেয়ে বিখ্যাত আংশিক ফল Paul, Pippenger, Szemerédi আর Trotter-এর (১৯৮৩): multi-tape যন্ত্রে রৈখিক সময়ে nondeterminism সত্যিই বেশি পারে, DTIME(n) ≠ NTIME(n); কিন্তু বড় সময়-সীমায় এমন কিছু প্রমাণিত নয়। জায়গার (space) ক্ষেত্রে ছবি অনেক ভালো: Savitch ১৯৭০ সালে দেখান, s(n) ≥ log n হলে s(n) জায়গার NTM-কে deterministic ভাবে s(n)2 জায়গায় অনুকরণ করা যায় (পর্ব ৬৪)। অনেক গবেষক আরও শক্ত অনুমান করেন যে 3SAT-এর জন্য 2o(n) সময়ের কোনো algorithm নেই (Exponential Time Hypothesis, Impagliazzo আর Paturi, প্রায় ২০০১); এটি অনুমান, প্রমাণ নয় (পর্ব ৭২)।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- NTM-এর formal definition দিন; DTM থেকে পার্থক্য কোথায়? δ: Q′ × Γ → P(Q × Γ × {L, R}); একটি শাখা গ্রহণ করলেই গ্রহণ।
- প্রমাণ করুন NTM আর DTM সমতুল্য। তিন-tape D, address tape-এ shortlex ক্রমে BFS; তারপর multi-tape থেকে single-tape.
- Simulation-এ DFS কেন চলে না? একটি অসীম শাখায় ঢুকলে DFS আর ফেরে না, গ্রহণকারী শাখা অদেখা থাকে।
- t(n) সময়ের NTM-এর deterministic simulation কত সময় নেয়? 2O(t(n)); polynomial-এ সম্ভব কি না, তা P বনাম NP-এর প্রশ্ন।
- NTM decider কখন? যখন প্রতিটি input-এ প্রতিটি শাখা থামে; তখন König-এর lemma-য় গাছ সসীম।
৮ · AI-এর যুগে NTM আর simulation
AI assistant-কে NTM নিয়ে প্রশ্ন করলে সাবলীল উত্তর আসে, কিন্তু কয়েকটি ভুল প্রায় নিয়মিত দেখা যায়: “NTM সব শাখা সমান্তরালে চালায়, তাই দ্রুত” (সংজ্ঞায় কোনো হার্ডওয়্যার নেই), “NP মানে non-polynomial”, আর “quantum computer হলো NTM” (BQP আর NP-এর সম্পর্ক অজানা, পর্ব ৭৫)। নিচের সারণিতে আরও কয়েকটি।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “NTM DTM-এর চেয়ে শক্তিশালী; কিছু language শুধু NTM চেনে” | উপপাদ্য ৫.১: ক্ষমতা সমান; পার্থক্য শুধু দক্ষতায়, আর তা-ও অপ্রমাণিত |
| Simulation-এ DFS বা “প্রথম পছন্দ আগে” recursion | একটি qloop-ধরনের অসীম শাখা দিয়ে simulator চালিয়ে দেখুন, ধাপের সীমাসহ |
| “কোনো শাখা reject করলে বর্জন”, বা accept/reject অদলবদলে complement | সংজ্ঞা ২.২ মিলিয়ে নিন: বর্জন মানে সব শাখা থামা আর হারা |
| “NTM-কে polynomial সময়ে simulate করা যায়” বা “P ≠ NP প্রমাণিত” | দুটিই খোলা প্রশ্ন; জানা ঊর্ধ্বসীমা 2O(t). দাবির উৎস চান |
| Address পদ্ধতিতে অবৈধ address-কে “reject” ধরে থেমে যাওয়া | অবৈধ মানে শুধু “এটি node নয়, পরের address”; ছোট NTM-এ address-তালিকা ছাপিয়ে মেলান |
| বানানো সাল বা রেফারেন্স (যেমন ভুল বছরে König, Savitch) | Sipser, HMU বা Arora–Barak-এ নিজে খুঁজে দেখুন |
AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণের প্রতিটি ধাপের কারণ, একটি ছোট NTM-এর পুরো computation tree আর একটি simulator চাওয়া, যা আপনি নিজে ধাপের সীমা দিয়ে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Nondeterministic যন্ত্র কি বাস্তবে বানানো যায়? “অনুমান” কথাটির সঠিক অর্থ কী, আর parallel, random বা quantum ব্যাখ্যাগুলো কতটা ঠিক?
সরাসরি উত্তর: না, NTM কোনো যন্ত্রের নকশা নয়। এটি একটি প্রশ্নের গাণিতিক রূপ: “এমন কোনো পছন্দের ক্রম কি আছে, যা গ্রহণে পৌঁছায়?” এখানে “আছে” একটি অস্তিত্বের দাবি (∃), যেমন গণিতে “এমন কোনো x আছে যাতে …”। পছন্দ কে করে, তা সংজ্ঞায় নেই। মজার ব্যাপার হলো, Turing নিজে ১৯৩৬ সালের প্রবন্ধে “automatic machine” (a-machine)-এর পাশাপাশি “choice machine” (c-machine)-এর কথা লেখেন বলে পরিচিত, যেখানে কিছু ধাপে বাইরের একজন অপারেটর পছন্দ ঠিক করে দেন। আজকের NTM সেই অপারেটরকে একটি সর্বদা-সঠিক অনুমানে বদলে দিয়েছে।
তিনটি জনপ্রিয় ব্যাখ্যা আংশিক সত্য। “Parallel” ব্যাখ্যা (প্রতিটি ভাগে যন্ত্র নিজের কপি বানায়) গ্রহণের সংজ্ঞা বোঝাতে কাজের, কিন্তু কপির সংখ্যা সূচকীয় হারে বাড়ে; polynomial সংখ্যক processor কাজকে বড়জোর polynomial গুণ দ্রুত করে। “Random” ব্যাখ্যা ভুল: একটি randomized যন্ত্র এলোমেলো পছন্দ করে আর গ্রহণের সম্ভাবনা মাপে; একটি NTM-এ একটি মাত্র গ্রহণকারী শাখা থাকলেও (২১০০-এর মধ্যে একটি) উত্তর “হ্যাঁ”, যা এলোমেলো চেষ্টায় কার্যত কখনো পাওয়া যাবে না। Randomized যন্ত্রের শ্রেণি আলাদা (BPP, পর্ব ৬৯)। “Quantum” ব্যাখ্যাও ভুল: quantum কম্পিউটার সব শাখা চালিয়ে ভালোটি বেছে নিতে পারে না; interference-এর কৌশল শুধু কিছু বিশেষ গঠনের সমস্যায় কাজে লাগে। BQP-তে NP-complete সমস্যা আছে কি না, তা অজানা, আর অধিকাংশ গবেষক তা মনে করেন না।
NTM-এর গুরুত্ব এখানেই: এটি “খোঁজা” আর “যাচাই করা”-র ফারাক মাপার ভাষা।
মূল উপলব্ধি: NTM একটি “∃ সফল পথ” প্রশ্নের ভাষা, বাস্তব হার্ডওয়্যার নয়; parallel, random বা quantum ছবি দিয়ে একে বোঝাতে গেলে দামের হিসাবটাই হারিয়ে যায়।
প্র ০২Nondeterminism finite automaton-এ ক্ষমতা বাড়ায় না, PDA-তে বাড়ায়, Turing machine-এ আবার বাড়ায় না, আর LBA-তে কেউ জানে না। এই বিচিত্র ছবির পেছনের নিয়মটি কী?
প্রশ্নটি আসলে এই: একটি deterministic যন্ত্র কি nondeterministic যন্ত্রের “সব শাখার অবস্থা” নিজের স্মৃতিতে ধরে রাখতে পারে? Finite automaton-এ সব শাখার অবস্থা মানে Q-এর একটি subset, আর subset সসীম; তাই একটি DFA প্রতিটি subset-কে একটি state বানিয়ে সব শাখা একসঙ্গে চালায় (Rabin আর Scott, ১৯৫৯)। দাম state-সংখ্যায়, সময়ে নয়।
PDA-তে প্রতিটি শাখার নিজস্ব stack, আর একটি stack-এ অনেকগুলো stack একসঙ্গে রাখা যায় না, কারণ প্রতিটি শাখা নিজের stack-এর ওপরটা দেখতে চায়। সীমিত-প্রবেশের এই স্মৃতিই সমস্যা, আর ফলটি সত্যিকারের পার্থক্য: deterministic CFL একটি কঠোর উপশ্রেণি (পর্ব ৩৫)। Turing machine-এ স্মৃতি সীমাহীন আর যেকোনো জায়গায় পড়া-লেখা যায়। তাই deterministic যন্ত্র একটি tape-এ address বা পুরো configuration-এর queue রেখে সব শাখা পালা করে চালাতে পারে। স্মৃতির নমনীয়তা ক্ষমতার ফারাক মুছে দেয়, শুধু সময়ের দাম থেকে যায়।
LBA (linear bounded automaton) এক কৌতূহলী মাঝামাঝি: tape-এর দৈর্ঘ্য input-এর সমান। Nondeterministic LBA ঠিক context-sensitive language চেনে (Kuroda ১৯৬৪ সালে দেখান বলে পরিচিত)। কিন্তু deterministic LBA একই শ্রেণি চেনে কি না, এই “প্রথম LBA সমস্যা” আজও খোলা। এর একটি সমতুল্য রূপ NSPACE(n) = DSPACE(n)? Savitch-এর simulation-এ জায়গা বর্গ হয়ে যায়, n থেকে n2, তাই রৈখিক tape-এ তা চলে না। “দ্বিতীয় LBA সমস্যা”, অর্থাৎ context-sensitive language complement-এ বদ্ধ কি না, ১৯৮৭–৮৮ সালে Immerman আর Szelepcsényi আলাদাভাবে সমাধান করেন: হ্যাঁ, বদ্ধ (পর্ব ৬৬)।
সাধারণ নিয়মটি তাই: যদি deterministic যন্ত্রের সম্পদ (state, stack, tape, সময়, জায়গা) দিয়ে সব শাখার হিসাব রাখা যায়, তবে ক্ষমতা সমান; সম্পদ যত সীমিত বা যত অনমনীয়, প্রশ্ন তত কঠিন। P বনাম NP ঠিক এই প্রশ্ন, যেখানে সম্পদ হলো polynomial সময়।
মূল উপলব্ধি: Nondeterminism ক্ষমতা বাড়ায় কি না, তা নির্ভর করে deterministic যন্ত্র সব শাখার হিসাব নিজের স্মৃতিতে ধরতে পারে কি না, তার ওপর; সীমাহীন tape পারে, একটি stack পারে না, আর সীমিত সময় বা জায়গায় উত্তর প্রায়ই অজানা।
প্র ০৩NTM-এর deterministic simulation-এ সূচকীয় সময় কি অনিবার্য? কী প্রমাণিত, কী অনুমান, আর কী একেবারে খোলা?
প্রমাণিত অংশ দিয়ে শুরু করা যাক। উপপাদ্য ৭.১ একটি ঊর্ধ্বসীমা দেয়: t(n) সময়ের NTM-কে 2O(t(n)) সময়ে অনুকরণ করা যায়। নিম্নসীমার দিকে খুব সামান্য জানা। ১৯৮৩ সালে Paul, Pippenger, Szemerédi আর Trotter প্রমাণ করেন যে multi-tape Turing machine-এ রৈখিক সময়ের ক্ষেত্রে DTIME(n) ⊊ NTIME(n), অর্থাৎ অন্তত এই সরু জায়গায় nondeterminism সত্যিই বেশি পারে। প্রমাণটি সূক্ষ্ম আর মডেলের ওপর নির্ভরশীল; বড় সময়-সীমায় এর বিস্তার জানা নেই।
খোলা অংশ সবচেয়ে বড়। Polynomial সময়ের সব NTM-কে polynomial সময়ে অনুকরণ করা যায় কি না, এটিই P = NP প্রশ্ন। Clay Mathematics Institute ২০০০ সালে এটিকে Millennium Prize সমস্যার তালিকায় রাখে। অধিকাংশ গবেষক মনে করেন P ≠ NP, কিন্তু এটি বিশ্বাস, প্রমাণ নয়। পর্ব ৬৮-এ দেখবেন, কেন কিছু সহজ প্রমাণ-কৌশল (relativization) এই প্রশ্নের মীমাংসা করতে পারে না বলে প্রমাণিত, যা প্রশ্নটির কাঠিন্যের একটি কারণ।
অনুমানের স্তরও আছে। Exponential Time Hypothesis (ETH) বলে, 3SAT-এর কোনো 2o(n) সময়ের algorithm নেই, যেখানে n চলকের সংখ্যা। এটি P ≠ NP-এর চেয়েও শক্ত দাবি, আর অপ্রমাণিত। তবু fine-grained complexity-তে (পর্ব ৭২) একে ভিত্তি ধরে অনেক “শর্তসাপেক্ষ” নিম্নসীমা প্রমাণ করা হয়: “ETH সত্য হলে এই সমস্যার এর চেয়ে দ্রুত algorithm নেই।”
সূচকীয় দাম মানে সবসময় অসাধ্য নয়: বাস্তবে SAT solver বিশাল সমস্যাও প্রায়ই সমাধান করে (পর্ব ৭৩), যদিও সবচেয়ে খারাপ ক্ষেত্রে কোনো জানা algorithm সূচকীয়ের নিচে নামে না। জায়গার ক্ষেত্রে অবশ্য ছবি ভিন্ন: Savitch-এর উপপাদ্যে (১৯৭০) nondeterministic জায়গা s-কে deterministic জায়গা s2-এ অনুকরণ করা যায়, তাই PSPACE = NPSPACE প্রমাণিত (পর্ব ৬৪)।
মূল উপলব্ধি: সময়ের জন্য শুধু ঊর্ধ্বসীমা 2O(t) প্রমাণিত, নিম্নসীমা প্রায় অজানা; P ≠ NP আর ETH বিশ্বাস, প্রমাণ নয়, আর জায়গার ক্ষেত্রে simulation-এর দাম মাত্র বর্গ।
প্র ০৪Sipser-এর address পদ্ধতি আসলে কোন ধরনের search? বাস্তব সফটওয়্যারে, যেমন Prolog, model checker বা puzzle solver-এ, অসীম শাখার একই সমস্যা কীভাবে ফিরে আসে?
Address পদ্ধতি প্রতিটি address-এর জন্য root থেকে নতুন করে একটি সীমিত-গভীরতার পথ চালায়, আর গভীরতার সীমা ০, ১, ২, … করে বাড়ায়। এটি আসলে iterative deepening-এর একটি রূপ: DFS-এর মতো অল্প স্মৃতি (একটি address আর একটি tape), অথচ BFS-এর মতো সম্পূর্ণ, কারণ কোনো গভীরতায় আটকে থাকে না। বারবার root থেকে শুরু করা অপচয় মনে হয়, কিন্তু b ≥ 2 হলে মোট কাজ শেষ স্তরের কাজের একটি ধ্রুবক গুণের বেশি নয়, কারণ শেষ স্তরেই অধিকাংশ node. AI-এর search algorithm-এ (Korf ১৯৮৫ সালের প্রবন্ধে জনপ্রিয় করেন বলে পরিচিত) ঠিক এই যুক্তিই ব্যবহার হয়; DSA কোর্সের পর্ব ৪১-এ DFS নিজেই বিস্তারিত।
বাস্তব উদাহরণ অনেক। Prolog ভাষা একটি প্রশ্নের উত্তর খোঁজে DFS দিয়ে, rule-গুলো লেখার ক্রমে। একটি left-recursive rule, যেমন ancestor(X, Y) :- ancestor(X, Z), parent(Z, Y)., প্রথমে রাখলে Prolog নিজের ভেতরে অসীম গভীরে নামে আর উত্তর থাকা সত্ত্বেও কখনো দেয় না। এটি ঠিক অংশ ৪-এর qloop ফাঁদ। Prolog প্রোগ্রামাররা তাই rule-এর ক্রম সাবধানে ঠিক করেন, আর কিছু ব্যবস্থা tabling যোগ করে এই সমস্যা কমায়।
Model checker (পর্ব ৭৭) একটি software-এর সব সম্ভাব্য অবস্থা খোঁজে; অনেকে DFS ব্যবহার করে, কিন্তু আগে দেখা অবস্থা মনে রাখে বলে সসীম graph-এ আটকায় না, আর অবস্থা অসীম হলে গভীরতার সীমা লাগে। Sudoku-র মতো puzzle-এ গাছ সসীম, তাই DFS নিরাপদ, ঠিক composite_ntm.py-র মতো।
নিয়মটি তাই সরল: গাছ সসীম হলে (decider, বা দেখা অবস্থা মনে রাখা সসীম graph) DFS চলে আর প্রায়ই দ্রুত। গাছ অসীম হতে পারলে সম্পূর্ণতার জন্য BFS, iterative deepening বা একটি স্পষ্ট সীমা লাগে।
মূল উপলব্ধি: Address পদ্ধতি হলো iterative deepening, যা অল্প স্মৃতিতে BFS-এর সম্পূর্ণতা দেয়; Prolog-এর left recursion থেকে model checking পর্যন্ত, অসীম শাখার ফাঁদ বাস্তব সফটওয়্যারে প্রতিদিন দেখা যায়।
প্র ০৫“অনুমান করুন, তারপর যাচাই করুন” ছকটি কীভাবে complexity তত্ত্বের কেন্দ্রে এল, আর মৌলিক সংখ্যার গল্প এই ছকের কোন সূক্ষ্মতা দেখায়?
১৯৬০-এর দশকে গবেষকেরা লক্ষ করেন, অনেক কঠিন সমস্যার একটি সাধারণ বৈশিষ্ট্য আছে: উত্তর “হ্যাঁ” হলে একটি ছোট প্রমাণ দেখানো যায়, যা সহজে যাচাই হয়। Jack Edmonds ১৯৬৫ সালের matching-এর প্রবন্ধে polynomial সময়কে “ভালো algorithm”-এর মাপকাঠি হিসেবে প্রস্তাব করেন, আর সহজে যাচাইযোগ্য প্রমাণের ধারণা নিয়েও আলোচনা করেন বলে পরিচিত। Stephen Cook ১৯৭১ সালে এই শ্রেণিকে polynomial সময়ের nondeterministic Turing machine দিয়ে সংজ্ঞায়িত করে দেখান, SAT এই শ্রেণির “সবচেয়ে কঠিন” সমস্যা; Leonid Levin প্রায় একই সময়ে সোভিয়েত ইউনিয়নে স্বাধীনভাবে একই ধরনের ফল পান (প্রকাশ ১৯৭৩)। Richard Karp ১৯৭২ সালে ২১টি পরিচিত সমস্যাকে একই শ্রেণির সবচেয়ে কঠিন বলে দেখান। NTM-এর ভাষা এই সবকিছুকে এক সুতোয় বাঁধে: অনুমানের অংশ certificate, যাচাইয়ের অংশ verifier (পর্ব ৫৮–৬০)।
মৌলিক সংখ্যার গল্প একটি সূক্ষ্মতা দেখায়। COMPOSITES-এর certificate স্বাভাবিক: একটি গুণনীয়ক। কিন্তু PRIMES, অর্থাৎ “n মৌলিক”, তার certificate কী? “কোনো গুণনীয়ক নেই” দেখাতে সব সম্ভাবনা বাদ দিতে হয়, যা guess and verify-এর ছাঁচে বসে না। Vaughan Pratt ১৯৭৫ সালে দেখান যে মৌলিকতারও ছোট certificate আছে (একটি primitive root আর n − 1-এর গুণনীয়কগুলোর পুনরাবৃত্ত প্রমাণ), তাই PRIMES ∈ NP. শেষে ২০০২ সালে Agrawal, Kayal আর Saxena দেখান PRIMES ∈ P. অর্থাৎ যে সমস্যার “না” উত্তর প্রথমে যাচাইয়ের অযোগ্য মনে হয়েছিল, তারও ছোট প্রমাণ মিলেছে, আর শেষে সরাসরি দ্রুত algorithm-ও।
শিক্ষাটি দুই দিকে। এক, NTM দিয়ে সহজে লেখা যায় বলেই কোনো সমস্যা কঠিন নয়; COMPOSITES এখন P-তে। দুই, “না” উত্তরের ছোট প্রমাণ আছে কি না, সাধারণভাবে তা NP বনাম coNP প্রশ্ন (পর্ব ৬২), যা খোলা।
মূল উপলব্ধি: Guess and verify থেকে certificate আর verifier-এর ধারণা এসে NP-এর সংজ্ঞা দিয়েছে; মৌলিক সংখ্যার ইতিহাস মনে করিয়ে দেয় যে কোনো সমস্যার ছোট প্রমাণ বা দ্রুত algorithm আছে কি না, তা প্রায়ই দশকের গবেষণার পরে জানা যায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। ntm_tree.py-তে নিজের NTM লিখে bfs দিয়ে, আর address_sim.py-র address_sim দিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা: Σ = {0, 1}-এর ওপর L = {w : |w| ≥ 3 আর w-এর শেষ থেকে তৃতীয় চিহ্ন 1} চেনার জন্য একটি NTM দিন, যা শুধু ডানে চলে। এটি কি decider? Input 100-এ Sipser-এর address পদ্ধতি কোন address-এ গ্রহণ করে?
অনুমান: “এই 1-টিই শেষ থেকে তৃতীয়”। q0-তে 0 পড়ে (q0, 0, R); 1 পড়ে দুটি পছন্দ, (q0, 1, R) আর (q1, 1, R). তারপর গুনে দুটি চিহ্ন: q1-এ 0 বা 1 পড়ে q2, q2-তে 0 বা 1 পড়ে q3, সবই R. q3-তে ␣ পড়ে qaccept. বাকি সব (q, a)-তে δ = ∅, অর্থাৎ সেই শাখা বর্জন (q0-তে ␣ পড়লেও)।
এটি decider: প্রতিটি move ডানে, আর blank-এ পৌঁছালে প্রতিটি শাখা থামে (গ্রহণ বা কোনো move নেই), তাই কোনো শাখা |w| + 1 ধাপের বেশি চলে না। Input 100-এ গ্রহণকারী শাখা: প্রথম 1-এ অনুমান (পছন্দ ২), তারপর তিনটি একক move: address 2111. Shortlex ক্রমে এর আগে দৈর্ঘ্য ০–৩-এর ১৫টি আর দৈর্ঘ্য ৪-এর ৮টি address, তাই ২৪তম address-এ গ্রহণ। Scratch-এ address simulator-এ ঠিক এই ফল (২৪টি address, মোট ৪০টি অনুকৃত ধাপ), আর দৈর্ঘ্য ১০ পর্যন্ত ২০৪৭টি string-এ যন্ত্র আর সংজ্ঞা হুবহু মিলেছে।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: যেকোনো NTM N-কে একটি DTM D DFS দিয়ে অনুকরণ করতে পারে। প্রমাণ: D গাছটিতে DFS চালায়, প্রতিটি node-এ পছন্দ ১, ২, … ক্রমে। গাছে প্রতিটি node-এর সন্তান সসীম, তাই DFS একসময় প্রতিটি node দেখবে। N কোনো শাখায় গ্রহণ করলে D সেই node দেখে গ্রহণ করবে। ∎” ভুলটি কোথায়, আর কোন ক্ষেত্রে দাবিটি সত্য?
ভুল বাক্যটি “DFS একসময় প্রতিটি node দেখবে”। সন্তান সসীম হলেও একটি শাখা অসীম হতে পারে; DFS সেই শাখায় ঢুকলে কখনো পিছিয়ে আসে না, তাই তার ডান দিকের কোনো node কখনো দেখা হয় না। N1-এ input 011: DFS পছন্দ ১ ধরে 011[q0]␣ থেকে qloop-এ ঢোকে, আর address 121-এর গ্রহণকারী node অদেখা থাকে (address_sim.py-র শেষ লাইন, ১০০০টি configuration-এর পরেও qloop). “Finitely branching” শুধু প্রতিটি স্তরকে সসীম রাখে, গভীরতাকে নয়।
দাবিটি সত্য হয় যখন N decider: তখন প্রতিটি শাখা সসীম, König-এর lemma-য় পুরো গাছ সসীম, আর DFS সব node দেখে থামে (composite_ntm.py-র DFS ঠিক এই ক্ষেত্র)। সাধারণ NTM-এর জন্য সংশোধন: BFS, বা address পদ্ধতির মতো iterative deepening.
-
Trace: N1-এর transition: q0-তে 0 পড়ে (q0, 0, R); 1 পড়ে পছন্দ ১ (q0, 1, R), পছন্দ ২ (q1, 1, R); ␣ পড়ে পছন্দ ১ (qloop, ␣, R), পছন্দ ২ (qreject, ␣, R); q1-এ 1 পড়ে (qaccept, 1, R), 0 বা ␣ পড়ে qreject; qloop-এ ␣ পড়ে (qloop, ␣, R). Input 11-এ address পদ্ধতি কোন কোন address চেষ্টা করে, প্রতিটির ফল কী, আর মোট কয়টি অনুকৃত ধাপ লাগে?
ε: running, [q0]11 (০ ধাপ)। 1: running, 1[q0]1 (১)। 2: running, 1[q1]1 (১); এখানে প্রথম 1-এই দুটি পছন্দ, তাই 011-এর মতো অবৈধ নয়। 11: running, 11[q0]␣ (২)। 12: running, 11[q1]␣ (২)। 21: ACCEPT, 11[qacc]␣ (২)।
মোট ছয়টি address আর 0 + 1 + 1 + 2 + 2 + 2 = ৮টি অনুকৃত ধাপ। address_sim.py-র আউটপুটের “11 ('ACCEPT at 21', 6, 8)” লাইন ঠিক এটিই। গ্রহণকারী শাখা দুই ধাপের, তাই BFS স্তর ২-এ পায়।
-
হিসাব: একটি decider NTM-এর branching factor b = 3, আর দৈর্ঘ্য n-এর একটি input-এ প্রতিটি শাখা বড়জোর t = 10 ধাপে থামে। Address পদ্ধতি দৈর্ঘ্য ≤ 10-এর কতগুলো address চেষ্টা করতে পারে, আর অনুকৃত ধাপের একটি ঊর্ধ্বসীমা কত? t = 20 হলে?
দৈর্ঘ্য i-এর address 3i-টি, তাই মোট Σi=0..10 3i = (311 − 1)/2 = 88,573. দৈর্ঘ্য i-এর একটি address বড়জোর i ধাপ চালায়, তাই অনুকৃত ধাপ ≤ Σ i · 3i = 841,449 (একটি সরল ঊর্ধ্বসীমা 10 × 88,573 = 885,730). t = 20-এ address (321 − 1)/2 = 5,230,176,601 আর ধাপ ≤ 101,988,443,730. t দ্বিগুণ হলে কাজ প্রায় 310 ≈ ৫৯,০০০ গুণ: এটিই 2O(t)-এর অর্থ। সংখ্যাগুলো scratch-এ Python দিয়ে গোনা।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমSipser-এর তিন-tape deterministic simulation D-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- tape ১-এ input w রাখা আর tape ৩-এ address ε বসানো
- tape ২ মুছে tape ১ থেকে w কপি করা
- tape ৩-এর চিহ্ন অনুযায়ী পছন্দ নিয়ে tape ২-এ N-এর একটি শাখা চালানো
- accepting configuration এলে গ্রহণ করে থামা
- নইলে tape ৩-এ shortlex ক্রমের পরের address বসিয়ে কপির ধাপে ফেরা
একটি nondeterministic Turing machine N একটি input w গ্রহণ করে কখন?
- যখন computation tree-র সব শাখা qaccept-এ পৌঁছায়
- যখন অন্তত একটি শাখা qaccept-এ পৌঁছায়
- যখন অর্ধেকের বেশি শাখা qaccept-এ পৌঁছায়
- যখন সব শাখা থামে আর অন্তত একটি গ্রহণ করে
একটি NTM-কে deterministic ভাবে অনুকরণ করতে computation tree-তে DFS (প্রথম পছন্দ আগে, যতদূর সম্ভব গভীরে) ব্যবহার করলে প্রধান সমস্যা কী?
- DFS-এর জন্য BFS-এর চেয়ে অনেক বেশি স্মৃতি লাগে
- একটি node-এর সন্তানদের কোনো নির্দিষ্ট ক্রম নেই
- একটি অসীম শাখায় আটকে গিয়ে গ্রহণকারী শাখা কখনো না-ও দেখতে পারে
- DFS নিজেই nondeterministic, তাই DTM-এ লেখা যায় না
একটি NTM decider-এর প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ বড়জোর t(n) ধাপে থামে, যেখানে t(n) ≥ n. এর সমতুল্য single-tape deterministic decider-এর জানা সময়-ঊর্ধ্বসীমা কোনটি?
- 2O(t(n))
- O(t(n)2)
- O(t(n))
- সময় অসীম হতে পারে, কারণ গাছ অসীম
NTM N-এর transition: q0-তে 0 পড়ে (q0, 0, R); 1 পড়ে দুটি পছন্দ, (q0, 1, R) আর (q1, 1, R); q1-এ 1 পড়ে (qaccept, 1, R); অন্য সব ক্ষেত্রে কোনো move নেই। Input 11-এ address পদ্ধতি shortlex ক্রমে ε থেকে শুরু করে কততম address-এ গ্রহণ করে?
- তৃতীয় (address 2)
- পঞ্চম (address 12)
- ষষ্ঠ (address 21)
- সপ্তম (address 22)
Nondeterministic আর deterministic Turing machine সম্পর্কে নিচের কোন বক্তব্যটি প্রমাণিত সত্য?
- প্রতিটি polynomial-সময়ের NTM-কে polynomial সময়ের DTM দিয়ে অনুকরণ করা যায়
- একটি language Turing-recognizable হয় ঠিক যখন কোনো NTM তাকে চেনে, আর decidable হয় ঠিক যখন কোনো NTM decider তাকে decide করে
- কিছু language শুধু NTM চেনে, কোনো DTM চেনে না
- NTM-এর কোনো একটি শাখা বর্জন করলে NTM input-টি বর্জন করে
একটি nondeterministic Turing machine N-কে কখন decider বলা হয়?
- যখন প্রতিটি input-এ অন্তত একটি শাখা থামে
- যখন প্রতিটি গৃহীত input-এ অন্তত একটি শাখা qaccept-এ পৌঁছায়
- যখন প্রতিটি configuration-এর সন্তান সংখ্যা সসীম
- যখন প্রতিটি input-এ প্রতিটি শাখা থামে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- NTM: δ: Q′ × Γ → P(Q × Γ × {L, R}). গ্রহণ = অন্তত একটি শাখা qaccept-এ; বর্জন = সব শাখা থামে আর কোনোটি গ্রহণ করে না; decider = প্রতিটি input-এ প্রতিটি শাখা থামে।
- Computation tree-র node configuration, root q0w, প্রতি node-এ বড়জোর b সন্তান; root থেকে পছন্দের ক্রম হলো address.
- DFS অসীম শাখায় আটকে যেতে পারে; BFS বা Sipser-এর address পদ্ধতি (tape ১ input, tape ২ simulation, tape ৩ shortlex address) সবসময় গ্রহণকারী শাখা খুঁজে পায়।
- NTM = DTM ক্ষমতায়: recognizable আর decidable দুই অর্থেই; decider-এর ক্ষেত্রে König-এর lemma গাছকে সসীম করে।
- দাম: t(n) সময়ের NTM ⇒ 2O(t(n)) সময়ের DTM; polynomial-এ সম্ভব কি না, তা P বনাম NP. Guess and verify-এর অনুমানই NP-এর certificate.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৯ · NFA — nondeterminism, একসঙ্গে অনেক পথ আর গ্রহণের নিয়মফিরে দেখুন“অন্তত একটি পথ”, computation tree আর guess and verify-এর প্রথম রূপ।
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণতুলনাসসীম স্মৃতিতে nondeterminism মোছার পদ্ধতি, যার দাম state-সংখ্যায়।
- পর্ব ৩২ · Pushdown automaton — stack-সহ automatonতুলনাযেখানে nondeterminism সত্যিই ক্ষমতা বাড়ায়: wwR-এর মাঝখান অনুমান।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪৭ Church–Turing thesis, আর পর্ব ৫৮-এ NP.
- DSA · পর্ব ৬৪ — P বনাম NPপাশের ট্র্যাকAlgorithm-এর দিক থেকে NP-complete সমস্যা আর reduction.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৫ — Turing machine-এর পরিচয়পাশের ট্র্যাকTuring machine আর halting problem-এর প্রথম পরিচয়, গণিতের দিক থেকে।