এই পর্বে যা শিখবেন
- Decision, function, search আর optimization problem-এর নিখুঁত সংজ্ঞা আর পার্থক্য
- Encoding ⟨·⟩-এর তিন শর্ত, আর graph ও DFA-কে string-এ লেখা ও ফিরিয়ে পড়া
- “সমস্যা সমাধান ⇔ language decide” প্রস্তাবের দুই দিকের প্রমাণ, আর ADFA decidable হওয়ার প্রমাণ
- Unary বনাম binary: কেন input-এর দৈর্ঘ্য দিয়ে সময় মাপতে হয়, আর pseudo-polynomial কী
- বাজারঘরের ডেলিভারি রুটে optimization থেকে decision, আবার decision থেকে আসল রুট
১ · একটি প্রশ্ন, একটি string — কেন সমস্যাকে language বলি
বাজারঘর আমাদের কাল্পনিক অনলাইন দোকান। গ্রাহক অর্ডার ট্র্যাক করতে একটি order code লেখেন, যার নিয়ম “BG-” তারপর ঠিক চারটি অঙ্ক, যেমন BG-0042. ওয়েবসাইটের প্রথম কাজ একটি প্রশ্নের উত্তর দেওয়া: “এই লেখাটি কি বৈধ order code?” উত্তর শুধু হ্যাঁ অথবা না।
খেয়াল করুন, যে program এই প্রশ্নের উত্তর দেয়, সে “অর্ডার”, “গ্রাহক” বা “দোকান” কিছুই বোঝে না। সে পায় কয়েকটি অক্ষরের একটি সারি, অর্থাৎ একটি string, আর ফেরত দেয় হ্যাঁ বা না। পর্ব ০৩-এর ভাষায়, সব বৈধ code মিলে একটি সেট:
এটি একটি formal language: একটি alphabet Σ-এর ওপর string-এর একটি সেট, L ⊆ Σ∗. “code বৈধ কি না” প্রশ্নের উত্তর দেওয়া আর “string-টি LORDER-এর সদস্য কি না” বলা হুবহু একই কাজ। এই পর্বের পুরো কথাটি এই এক লাইনে: প্রতিটি হ্যাঁ/না প্রশ্নকে একটি language হিসেবে লেখা যায়, আর প্রশ্নের উত্তর দেওয়া মানে সেই language-এর সদস্যতা যাচাই করা।
রেলের টিকিট কাউন্টারের কথা ভাবুন। কাউন্টারের কর্মী যাত্রীকে চেনেন না, তাঁর গন্তব্যের কারণও জানেন না। তিনি শুধু একটি ছাপা ফর্ম দেখেন: নির্দিষ্ট ঘরে নির্দিষ্ট ধরনের লেখা আছে কি না। ফর্মটি হলো encoding, যাত্রীর আসল চাহিদা হলো instance, আর কর্মীর “হ্যাঁ, টিকিট হবে” বা “না” হলো যন্ত্রের accept বা reject. ফর্ম ভুলভাবে ভরলে (তারিখের ঘরে নাম) কর্মী সোজা ফেরত দেন; যন্ত্রও ভুল-গঠনের string reject করে।
কেন এত কষ্ট করে প্রশ্নকে language বানানো? কারণ এই কোর্সের সব যন্ত্র, finite automaton থেকে Turing machine পর্যন্ত, string-এর ওপর কাজ করে। প্রশ্নকে language বানালে একটিমাত্র মাপকাঠিতে সব প্রশ্ন তুলনা করা যায়: কোন language কোন যন্ত্র চিনতে পারে, কত সময়ে, কত memory-তে। নিচের ছবিটি এই সেতুর পুরো পথ দেখায়।
বাস্তব প্রশ্ন থেকে accept/reject পর্যন্ত
Instance x আগে encoding-এ string ⟨x⟩ হয়; decider শুধু সেই string পড়ে সিদ্ধান্ত দেয়।
নিচের stepper বাজারঘরের প্রশ্নটিকে ধাপে ধাপে language-এ রূপ দেয়। প্রতিটি ধাপে একটি করে সিদ্ধান্ত নিতে হয়; কোনোটি বাদ দিলে language অস্পষ্ট থেকে যায়।
| ধাপ | |
| বিষয় |
- প্রশ্ন। “গ্রাহক যে order code লিখলেন, সেটি কি বৈধ?” প্রশ্নটি হ্যাঁ/না আকারে, তাই এটি একটি decision problem.
- Instance কী? প্রশ্নের প্রতিটি নির্দিষ্ট ইনপুট একটি instance. এখানে গ্রাহক যা খুশি লিখতে পারেন:
BG-0042,bg-42, এমনকি ফাঁকা লেখা। তাই সব string-ই instance. - Alphabet ঠিক করা। Σ = বড় হাতের A–Z, ছোট হাতের a–z, অঙ্ক 0–9 আর হাইফেন। মোট 26 + 26 + 10 + 1 = 63টি চিহ্ন; Σ সসীম আর অশূন্য, যেমন পর্ব ০৩-এর শর্ত।
- হ্যাঁ-শর্ত। String-টি ঠিক 7 অক্ষরের, প্রথম তিনটি হুবহু “BG-”, বাকি চারটি অঙ্ক। শর্তটি শুধু অক্ষর দেখেই যাচাই করা যায়, ডেটাবেস লাগে না।
- Language লেখা। LORDER = {BG-d1d2d3d4}; প্রতিটি অঙ্কের 10টি বিকল্প, তাই |LORDER| = 104 = 10000. Language সসীম, অথচ instance অসীম।
- সদস্যতা।
BG-0042∈ LORDER;BG-042∉ LORDER (তিন অঙ্ক);bg-0042∉ LORDER (ছোট হাতের অক্ষর)। প্রশ্নের উত্তর দেওয়া আর এই সদস্যতা বলা একই কাজ।
এই language এতই সরল যে একটি ছোট finite automaton-ই একে চেনে; সেই যন্ত্রের নকশা অনুশীলন ১-এ, আর DFA-র পূর্ণ সংজ্ঞা পর্ব ০৭-এ। কিন্তু সব প্রশ্ন এত সরল নয়। “এই program কি কখনো থামবে?” প্রশ্নটিও একটি language, অথচ কোনো যন্ত্রই সেটি সবসময় ঠিকভাবে decide করতে পারে না। এই দুই প্রান্তের মাঝখানের পুরো মানচিত্রই এই কোর্স।
২ · সমস্যার চার রূপ — decision, function, search আর optimization
“সমস্যা” শব্দটি দৈনন্দিন কথায় ঢিলেঢালা। গণনার তত্ত্বে এর নিখুঁত অর্থ দরকার। একটি computational problem মানে অসীম সংখ্যক প্রশ্নের একটি পরিবার, যাদের প্রত্যেকটি একটি instance; “1000003 কি মৌলিক?” একটি instance, আর “একটি স্বাভাবিক সংখ্যা মৌলিক কি না” হলো সমস্যা। উত্তরের ধরন অনুযায়ী সমস্যা চার রকম।
ধরা যাক I হলো instance-এর সেট।
- Decision problem: একটি উপসেট Y ⊆ I দেওয়া; প্রতিটি x ∈ I-এর জন্য বলতে হবে x ∈ Y (হ্যাঁ) না x ∉ Y (না)। Y-এর সদস্যরা yes-instance.
- Function problem: একটি ফাংশন f: I → S দেওয়া; প্রতিটি x-এর জন্য f(x) বের করতে হবে, যেমন দুটি সংখ্যার gcd.
- Search problem: একটি সম্পর্ক R ⊆ I × S দেওয়া; x দিলে এমন একটি y দিতে হবে যাতে (x, y) ∈ R, অথবা বলতে হবে এমন y নেই। একাধিক সঠিক উত্তর থাকতে পারে।
- Optimization problem: প্রতিটি x-এর বৈধ সমাধানের সেট আর একটি খরচ-ফাংশন দেওয়া; সবচেয়ে কম (বা বেশি) খরচের সমাধান, অথবা শুধু সেই খরচ বের করতে হবে।
একই বিষয় নিয়ে চার রকম প্রশ্ন করা যায়। বাজারঘরের ডেলিভারি ভ্যান গুদাম থেকে বেরিয়ে কয়েকটি ঠিকানা ঘুরে ফেরে; প্রতিটি রাস্তার খরচ টাকায় জানা।
| ধরন | মৌলিক সংখ্যা নিয়ে | ডেলিভারি রুট নিয়ে | উত্তরের রূপ |
|---|---|---|---|
| Decision | n কি মৌলিক? | খরচ ≤ k টাকার কোনো রুট আছে? | হ্যাঁ / না |
| Function | n-এর ক্ষুদ্রতম মৌলিক উৎপাদক কত? | সবচেয়ে সস্তা রুটের খরচ কত? | একটি নির্দিষ্ট মান |
| Search | n-এর একটি অতুচ্ছ উৎপাদক দিন (না থাকলে বলুন) | খরচ ≤ k-এর একটি রুট দেখান | যেকোনো একটি সাক্ষী |
| Optimization | — | সবচেয়ে সস্তা রুটটি দিন | সেরা সমাধান |
এই কোর্সের বেশিরভাগ তত্ত্ব decision problem নিয়ে। কারণ তিনটি। প্রথমত, হ্যাঁ/না উত্তর মানেই একটি language, আর language-এর ওপর যন্ত্রের তত্ত্ব খুব পরিষ্কার। দ্বিতীয়ত, কোনো কিছু অসম্ভব বা কঠিন প্রমাণ করতে decision রূপই যথেষ্ট: হ্যাঁ/না-ও যদি বলা না যায়, পুরো সমাধান তো আরও অসম্ভব। তৃতীয়ত, অনুচ্ছেদ ৭-এ দেখবেন, অনেক ক্ষেত্রে decision রূপের উত্তর জানা থাকলে optimization আর search রূপও বের করা যায়।
Decision রূপ বানাতে গিয়ে একটি সাধারণ ভুল: প্রশ্নে একটি সীমা k না রাখা। “সবচেয়ে সস্তা রুট কোনটি?” হ্যাঁ/না প্রশ্ন নয়। সঠিক decision রূপ: “খরচ ≤ k-এর রুট আছে কি?”, যেখানে k instance-এর অংশ, অর্থাৎ ইনপুটের সঙ্গেই দেওয়া হয়।
৩ · Encoding ⟨·⟩ — বস্তুকে string-এ লেখা
Instance সবসময় string হয় না। একটি graph হলো বিন্দু আর রেখার সেট, একটি DFA হলো পাঁচটি অংশের tuple, একটি সংখ্যা হলো বিমূর্ত মান। যন্ত্রকে দিতে হলে এদের প্রত্যেককে একটি নির্দিষ্ট নিয়মে string-এ লিখতে হয়। মোবাইল ব্যাংকিংয়ের PIN মেনুতে আপনি “টাকা পাঠান” বেছে নিলে ফোন আসলে সার্ভারে কয়েকটি অঙ্ক আর চিহ্নের একটি string পাঠায়; সার্ভার সেটি পড়ে আবার “কাকে, কত” বুঝে নেয়। এই লেখা আর পড়ার নিয়মটিই encoding.
একটি instance-সেট I-এর encoding হলো একটি ফাংশন ⟨·⟩: I → Σ∗, যা প্রতিটি বস্তু O-কে একটি string ⟨O⟩-এ পাঠায়। কয়েকটি বস্তু একসঙ্গে লিখলে ⟨O1, O2, …, Ok⟩, যেমন একটি DFA B আর একটি string w মিলে ⟨B, w⟩. Encoding-কে reasonable বলা হয় যদি তিনটি শর্ত মানে:
- Injective: আলাদা বস্তুর string আলাদা। নইলে decode করে বস্তু ফেরত পাওয়া যায় না।
- লেখা ও পড়া যায়: x থেকে ⟨x⟩ বানানো, আর কোনো string s দিলে “s কি কোনো ⟨x⟩?” যাচাই করে x ফেরত আনা, দুটিই algorithm দিয়ে করা যায়। Complexity-র প্রশ্নে এ দুটি polynomial সময়ে হতে হয়।
- অপচয়হীন: ⟨x⟩-এর দৈর্ঘ্য x-এর স্বাভাবিক আকারের polynomial; বিশেষত সংখ্যা binary (বা দশমিক)-এ, unary-তে নয় (অনুচ্ছেদ ৬)।
এই কোর্সের স্থির নিয়ম। (ক) ⟨O⟩ সবসময় O-এর একটি নির্দিষ্ট reasonable encoding; সাধারণত format-এর খুঁটিনাটি গুরুত্বহীন, তাই লেখা হয় শুধু ⟨G⟩, ⟨M⟩, ⟨M, w⟩. (খ) সংখ্যা ডিফল্টভাবে binary-তে। (গ) যে string কোনো বস্তুর বৈধ encoding নয়, তাকে না-instance ধরা হয়: language-এ নেই, decider সেটি reject করে। (ঘ) সমস্যার নাম বড় হাতের অক্ষরে: PRIME, CONNECTED, SAT, আর “accept করে কি না” প্রশ্নের জন্য ADFA, ATM; “থামে কি না” প্রশ্নের জন্য HALTTM. এই চিহ্নগুলো Sipser-এর বইয়ের ধারা মেনে, পরের সব পর্বে একই অর্থে।
নিয়ম (গ) খুব কাজের। এর ফলে প্রতিটি decider-এর প্রথম কাজ একই: string-টি ঠিক গঠনের কি না দেখা। Reasonable encoding-এ এই যাচাই সহজ আর সবসময় শেষ হয়, তাই “ভুল গঠনের string-এ কী করব” প্রশ্নটি তত্ত্বকে জটিল করে না।
একটি graph-কে string-এ লেখা
পরের অংশে ব্যবহারের জন্য একটি নির্দিষ্ট format ঠিক করি। Vertex 1, 2, …, n নিয়ে একটি undirected graph G-কে লেখা হবে n: তারপর কমা দিয়ে আলাদা করা edge-এর তালিকা, প্রতিটি edge u-v আকারে, যেখানে u < v আর তালিকা ছোট থেকে বড় ক্রমে। এই “একমাত্র রূপ” (canonical form) শর্তের ফলে প্রতিটি graph-এর ঠিক একটি string; ফলে encoding injective, আর decode করার পর আবার encode করলে হুবহু একই string ফিরে আসে।
একটি graph আর তার encoding
চারটি vertex, চারটি edge. নিচের string-টিই ⟨G⟩.
| string | |
| দৈর্ঘ্য | |
| বাকি edge |
- Vertex-সংখ্যা। প্রথমে n = 4 আর একটি কোলন:
4:. Vertex-এর নাম 1 থেকে n, তাই আলাদা করে নাম লিখতে হয় না। - প্রথম edge. Edge-গুলো (ছোট প্রান্ত, বড় প্রান্ত) জোড়া হিসেবে সাজালে প্রথমটি {1,2}; লেখা হলো
1-2. String এখন 5 অক্ষরের। - দ্বিতীয় edge. কমা দিয়ে আলাদা করে {1,3}:
4:1-2,1-3, দৈর্ঘ্য 9. - তৃতীয় edge. ক্রম অনুযায়ী এবার {1,4}, কারণ (1, 4) জোড়াটি (2, 3)-এর আগে আসে। দৈর্ঘ্য 13.
- শেষ edge. {2,3} যোগ করে ⟨G⟩ =
4:1-2,1-3,1-4,2-3, মোট 17 অক্ষর। Alphabet শুধু অঙ্ক, কোলন, কমা আর হাইফেন। - ফিরিয়ে পড়া। Decoder কোলনে ভাগ করে n = 4 পায়, কমায় ভাগ করে চারটি edge পায়, প্রতিটিতে 1 ≤ u < v ≤ 4 যাচাই করে, তারপর আবার encode করে মিলিয়ে দেখে। একই string ফিরে এল, তাই এটি বৈধ ⟨G⟩.
4:2-1,1-3এই শেষ পরীক্ষায় আটকে যায়।
এখন এই format-টি সত্যিই চালিয়ে দেখি। নিচের ব্লকে encode_graph আর decode_graph উপরের নিয়ম মানে, আর CONNECTED হলো connected graph-এর language-এর একটি decider: যেকোনো string নেয়, ভুল গঠন হলে reject করে, নইলে vertex 1 থেকে BFS চালিয়ে দেখে সব vertex-এ পৌঁছানো যায় কি না। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।
from collections import deque
# <G> of an undirected graph on vertices 1..n: "n:u-v,u-v,..." (u < v, edges sorted)
def encode_graph(n, edges):
es = sorted({(min(u, v), max(u, v)) for u, v in edges})
return f"{n}:" + ",".join(f"{u}-{v}" for u, v in es)
def decode_graph(s): # (n, edges) if s is some <G>, else None
head, sep, body = s.partition(":")
if not sep or not head.isdecimal() or int(head) < 1: return None
n, edges = int(head), []
for part in (body.split(",") if body else []):
u, dash, v = part.partition("-")
if not (dash and u.isdecimal() and v.isdecimal()):
return None
u, v = int(u), int(v)
if not (1 <= u < v <= n): return None
edges.append((u, v))
return (n, edges) if encode_graph(n, edges) == s else None # canonical form only
def CONNECTED(s): # a decider: it halts on every string s
g = decode_graph(s)
if g is None:
return False # not a well-formed <G>: reject
n, edges = g
adj = {v: [] for v in range(1, n + 1)}
for u, v in edges:
adj[u].append(v); adj[v].append(u)
seen, todo = {1}, deque([1])
while todo: # breadth-first search from vertex 1
for y in adj[todo.popleft()]:
if y not in seen:
seen.add(y); todo.append(y)
return len(seen) == n
G = encode_graph(4, [(1, 2), (2, 3), (3, 1), (1, 4)])
print("<G> =", G, " length", len(G), " decoded:", decode_graph(G))
for s in [G, "4:1-2,1-3,2-3", "1:", "4:2-1,1-3", "4:1-2,2-5", "BG-0042"]:
print(f"{s:18} valid={decode_graph(s) is not None!s:5} in CONNECTED={CONNECTED(s)}")আসল আউটপুট (ব্রাউজারের Python):
<G> = 4:1-2,1-3,1-4,2-3 length 17 decoded: (4, [(1, 2), (1, 3), (1, 4), (2, 3)])
4:1-2,1-3,1-4,2-3 valid=True in CONNECTED=True
4:1-2,1-3,2-3 valid=True in CONNECTED=False
1: valid=True in CONNECTED=True
4:2-1,1-3 valid=False in CONNECTED=False
4:1-2,2-5 valid=False in CONNECTED=False
BG-0042 valid=False in CONNECTED=False
Edge-গুলো এলোমেলো ক্রমে দিলেও ((3, 1) সহ) encoder একই canonical string বানায়, দৈর্ঘ্য 17, ঠিক stepper-এর মতো। দ্বিতীয় graph বৈধ কিন্তু vertex 4 বিচ্ছিন্ন, তাই CONNECTED-এ নেই। 1: হলো একটি vertex, কোনো edge নেই: সংজ্ঞা অনুযায়ী connected. শেষ তিনটি string ভুল গঠনের: 2-1 canonical নয়, 5 vertex-সীমার বাইরে, আর BG-0042-এ কোলনই নেই। নিয়ম (গ) মেনে তিনটিই reject. খেয়াল করুন, decider কখনো আটকে থাকে না: প্রতিটি loop সসীম তালিকার ওপর।
Graph লেখার এটিই একমাত্র উপায় নয়। Adjacency matrix হিসেবে n2টি বিট পরপর লেখা যায়, বা adjacency list হিসেবে। Matrix-এর দৈর্ঘ্য n2, edge-তালিকার দৈর্ঘ্য মোটামুটি m · log n (m = edge-সংখ্যা, প্রতিটি vertex-নাম লিখতে প্রায় log n অঙ্ক)। দুটির যেকোনো একটি থেকে অন্যটি polynomial সময়ে বানানো যায়, আর দৈর্ঘ্যও পরস্পরের polynomial-এর মধ্যে। তাই “কোন graph সমস্যা polynomial সময়ে হয়” প্রশ্নের উত্তর এই বাছাইয়ে বদলায় না।
৪ · সমস্যা = language — PRIME, CONNECTED, ADFA, SAT, ATM, HALTTM
Encoding ঠিক হলে decision problem আর language-এর সেতু একটি সংজ্ঞাতেই বাঁধা যায়।
Instance-সেট I, yes-instance-এর সেট Y ⊆ I আর encoding ⟨·⟩ দেওয়া থাকলে সমস্যা P-এর language হলো
LP = { ⟨x⟩ : x ∈ Y } ⊆ Σ∗.
অর্থাৎ শুধু হ্যাঁ-উত্তরের instance-গুলোর string. না-instance-এর string আর ভুল গঠনের string, দুটিই LP-এর বাইরে।
এই কোর্সে যেসব language বারবার ফিরে আসবে, সেগুলোর নাম এখনই চিনে রাখুন। প্রতিটির পাশে লেখা আছে কোন পর্বে তার ভাগ্য নির্ধারণ হবে।
| নাম | Language | প্রশ্নটি সহজ ভাষায় | যা জানা |
|---|---|---|---|
| PRIME | {⟨n⟩ : n মৌলিক} | সংখ্যাটি কি মৌলিক? | Decidable; polynomial সময়েও (AKS, ২০০২) |
| CONNECTED | {⟨G⟩ : G connected undirected graph} | সব vertex কি এক টুকরো? | Polynomial সময়ে (BFS) |
| ADFA | {⟨B, w⟩ : B একটি DFA, B w-কে accept করে} | এই DFA কি এই string নেয়? | Decidable (নিচে প্রমাণ); পর্ব ২০-এ বাকি regular প্রশ্ন |
| SAT | {⟨φ⟩ : φ একটি satisfiable Boolean সূত্র} | সূত্রটি কি কোনোভাবে সত্য করা যায়? | Decidable; NP-complete (পর্ব ৬০) |
| ATM | {⟨M, w⟩ : M একটি TM, M w-কে accept করে} | এই program কি এই ইনপুটে “হ্যাঁ” বলবে? | Recognizable, কিন্তু undecidable (পর্ব ৫১) |
| HALTTM | {⟨M, w⟩ : M একটি TM, M w-এ থামে} | এই program কি এই ইনপুটে কখনো থামবে? | Recognizable, undecidable (পর্ব ৫১–৫২) |
SAT হলো Boolean satisfiability: যেমন φ = (x ∨ y) ∧ (¬x ∨ y) সূত্রটি satisfiable, কারণ y = সত্য দিলেই দুটি অংশ সত্য। ATM-এ M একটি Turing machine, যার পূর্ণ সংজ্ঞা পর্ব ৪৩-এ; আপাতত একে “যেকোনো program” ভাবতে পারেন। লক্ষ করুন, ATM আর HALTTM-এর instance-এ একটি যন্ত্রের বর্ণনা ⟨M⟩ ইনপুট হিসেবে ঢুকছে। Program-কেও data হিসেবে string-এ লেখা যায়, আর এই ধারণাই পর্ব ৪৮-এর universal Turing machine আর পর্ব ৫১-এর halting problem-এর ভিত্তি।
এবার মূল প্রস্তাব। এখানে “algorithm” মানে এমন একটি ধাপে ধাপে পদ্ধতি যা প্রতিটি ইনপুটে সসীম ধাপে থেমে উত্তর দেয়; পর্ব ৪৭-এর Church–Turing thesis একে Turing machine-এর সঙ্গে এক করে দেয়। আর একটি language-কে decidable বলা হয় যদি এমন একটি যন্ত্র থাকে যা প্রতিটি string-এ থামে আর ঠিক L-এর string-গুলো accept করে।
ধরুন ⟨·⟩ একটি reasonable encoding. তাহলে decision problem P-এর জন্য একটি algorithm আছে ⇔ LP decidable.
প্রমাণ (⇒). ধরা যাক ALG একটি algorithm, যা প্রতিটি instance x-এ থেমে সঠিক হ্যাঁ/না দেয়। String s-এর ওপর যন্ত্র D বানাই:
- s কোনো ⟨x⟩ কি না যাচাই; না হলে reject. — শর্ত ২: এই যাচাই algorithm-এ হয় আর থামে
- হলে x decode করে ALG(x) চালাই; হ্যাঁ হলে accept, না হলে reject. — শর্ত ২-এ decode সম্ভব; ALG সবসময় থামে
- D প্রতিটি s-এ থামে, কারণ দুই ধাপই থামে। — উপরের দুই যুক্তি
- D accept করে ⇔ s = ⟨x⟩ আর x ∈ Y ⇔ s ∈ LP. — সংজ্ঞা ৫.৩; ভুল-গঠন বাইরে, নিয়ম (গ)
প্রমাণ (⇐). ধরা যাক D একটি যন্ত্র যা LP decide করে। Instance x-এর জন্য algorithm:
- ⟨x⟩ বানাই, D চালাই; accept হলে “হ্যাঁ”, reject হলে “না”। — শর্ত ২: encode করা যায়; D সবসময় থামে
- x ∈ Y হলে ⟨x⟩ ∈ LP, তাই উত্তর হ্যাঁ। — সংজ্ঞা ৫.৩
- x ∉ Y হলে ⟨x⟩ ∈ LP হতে পারে শুধু যদি কোনো y ∈ Y-এর জন্য ⟨x⟩ = ⟨y⟩, অর্থাৎ x = y ∈ Y, যা বিরোধ; তাই উত্তর না। ∎ — শর্ত ১: injective
দুই দিকেই encoding-এর শর্তগুলো ঠিক কোথায় লাগল, খেয়াল করুন। Injective না হলে দ্বিতীয় দিকের শেষ ধাপ ভাঙে; decode করা না গেলে প্রথম দিকের ধাপ ১। পর্ব ০৪-এর “if and only if” প্রমাণের দুই দিক লেখার নিয়ম এখানেই প্রথম পূর্ণ প্রয়োগ।
৫ · Decider আর recognizer — “সবসময় থামে” কেন জরুরি
লিফটের বোতামের কথা ভাবুন। ভালো লিফট প্রতিটি বোতাম চাপার পর কিছু একটা করে: দরজা খোলে, বা “ভুল তলা” দেখায়। খারাপ লিফট কখনো কখনো চুপচাপ দাঁড়িয়ে থাকে; আপনি জানেন না সে চলবে, নাকি চিরকাল দাঁড়িয়েই থাকবে। যন্ত্রের ক্ষেত্রেও এই পার্থক্য মৌলিক।
একটি যন্ত্র M, language L-এর decider যদি M প্রতিটি string-এ থামে, আর ঠিক L-এর string-গুলো accept করে। M, L-এর recognizer যদি M ঠিক L-এর string-গুলো accept করে; L-এর বাইরের string-এ M reject করতে পারে, অথবা কখনো না থেমে চলতে পারে। যে language-এর recognizer আছে, তাকে Turing-recognizable বলে।
প্রতিটি decider একটি recognizer, কিন্তু উল্টোটা সত্য নয়। Recognizer-কে জিজ্ঞেস করলে “হ্যাঁ” উত্তর একসময় আসবেই; কিন্তু “না”-এর অপেক্ষায় আপনি অনন্তকাল বসে থাকতে পারেন, আর কোনো মুহূর্তে বলতে পারবেন না অপেক্ষা থামানো উচিত কি না। এবার এমন একটি language দেখি যার decider সত্যিই আছে।
ADFA = {⟨B, w⟩ : B একটি DFA এবং B, w-কে accept করে} একটি decidable language.
প্রমাণ. ইনপুট string x-এর ওপর যন্ত্র D:
- x কোনো ⟨B, w⟩ কি না যাচাই: B-এর পাঁচ অংশ (Q, Σ, δ, q0, F) আছে, δ প্রতিটি (state, চিহ্ন) জোড়ায় ঠিক একটি state দেয়, আর w-এর প্রতিটি চিহ্ন Σ-তে। না মিললে reject. — সসীম string-এর ওপর সসীম যাচাই, তাই থামে
- q ← q0; w-এর চিহ্নগুলো বাঁ থেকে ডানে পড়ে প্রতিটিতে q ← δ(q, a). — ঠিক |w|টি ধাপ, প্রতিটি একটি সসীম table দেখা
- শেষে q ∈ F হলে accept, নইলে reject. — এখানে D থামে
- D accept করে ⇔ x = ⟨B, w⟩ আর δ̂(q0, w) ∈ F ⇔ B, w-কে accept করে ⇔ x ∈ ADFA. — DFA-র গ্রহণের সংজ্ঞা (পর্ব ০৭)
- ধাপ ১–৩ প্রতিটি সসীম, তাই D প্রতিটি x-এ থামে; D একটি decider. ∎
নিচের stepper এই decider-কে একটি নির্দিষ্ট string-এ চালায়। B হলো বাজারঘরের সেন্সর-লাইনের parity-যন্ত্র EVEN: state E (এ পর্যন্ত জোড় সংখ্যক 1) আর O (বিজোড়), শুরু E, accept E. এর encoding ছোট একটি format-এ: states;alphabet;moves;start;accepting, যেখানে move E1O মানে δ(E, 1) = O. তারপর # আর w.
1split x at "#": enc, w2B = decode(enc); bad: reject3w uses only Σ? no: reject4q = q05for a in w: q = δ(q, a)6q ∈ F ? accept : reject
| পড়া অংশ | |
| q | |
| পথ |
- ভাগ করা। x =
E,O;0,1;E0E,E1O,O0O,O1E;E;E#1001.#-এর বাঁয়ে ⟨B⟩, ডানে w = 1001. - ⟨B⟩ যাচাই। পাঁচটি অংশ আছে; Q = {E, O}, Σ = {0, 1}; চারটি move, প্রতিটি (state, চিহ্ন) জোড়ায় ঠিক একটি; q0 = E ∈ Q; F = {E} ⊆ Q. বৈধ DFA.
- w যাচাই। 1001-এর প্রতিটি চিহ্ন Σ = {0, 1}-এ আছে।
10a1হলে এখানেই reject হতো। - শুরু। q = E. এখনো কিছু পড়া হয়নি; ε-তে জোড় সংখ্যক (শূন্যটি) 1.
- পড়া 1. δ(E, 1) = O: এ পর্যন্ত একটি 1, বিজোড়।
- পড়া 0. δ(O, 0) = O: 0 parity বদলায় না।
- পড়া 0. আবার δ(O, 0) = O.
- পড়া 1. δ(O, 1) = E: মোট দুটি 1, জোড়। Loop ঠিক |w| = 4 বার চলল।
- সিদ্ধান্ত। q = E ∈ F, তাই accept: ⟨EVEN, 1001⟩ ∈ ADFA. যন্ত্র থামল, আর থামতে বাধ্য ছিল।
এবার একই decider Python-এ। এটি পাঁচটি অংশে ভাগ করে ⟨B⟩ যাচাই করে, δ সম্পূর্ণ কি না দেখে, তারপর DFA চালায়। শেষের দুটি পরীক্ষায় ইচ্ছা করে ভুল-গঠনের string দেওয়া হয়েছে।
# <B, w> = <B> + "#" + w, <B> = "states;alphabet;moves;start;accepting"
# every state and symbol is one character; a move "pas" means delta(p, a) = s
def decode_dfa(s):
parts = s.split(";")
if len(parts) != 5:
return None
Q, S, T = parts[0].split(","), parts[1].split(","), parts[2].split(",")
q0, F = parts[3], (parts[4].split(",") if parts[4] else [])
delta = {}
for t in T:
if len(t) != 3 or t[0] not in Q or t[1] not in S or t[2] not in Q:
return None
delta[t[0], t[1]] = t[2]
if len(T) != len(delta) or len(delta) != len(set(Q)) * len(set(S)):
return None # exactly one move for each (state, symbol)
if q0 not in Q or not set(F) <= set(Q):
return None
return delta, q0, set(F), set(S)
def A_DFA(x): # a decider: every path ends in a return
enc, sep, w = x.partition("#")
B = decode_dfa(enc) if sep else None
if B is None or not set(w) <= B[3]:
return "reject (not a valid <B, w>)"
delta, q, F, _ = B
path = q
for a in w: # exactly |w| moves, then stop
q = delta[q, a]
path += q
return ("accept" if q in F else "reject") + " path " + path
EVEN = "E,O;0,1;E0E,E1O,O0O,O1E;E;E"
tests = [("EVEN, 1001", EVEN + "#1001"), ("EVEN, 1011", EVEN + "#1011"),
("EVEN, empty", EVEN + "#"), ("EVEN, 10a1", EVEN + "#10a1"),
("missing moves", "E,O;0,1;E0E,E1O;E;E#1"), ("BG-0042", "BG-0042")]
for name, x in tests:
print(f"{name:14} -> {A_DFA(x)}")আসল আউটপুট (ব্রাউজারের Python):
EVEN, 1001 -> accept path EOOOE
EVEN, 1011 -> reject path EOOEO
EVEN, empty -> accept path E
EVEN, 10a1 -> reject (not a valid <B, w>)
missing moves -> reject (not a valid <B, w>)
BG-0042 -> reject (not a valid <B, w>)
প্রথম লাইনের পথ EOOOE হুবহু stepper-এর। 1011-এ তিনটি 1, তাই শেষ state O, reject; এটি বৈধ instance-এর না-উত্তর। ফাঁকা w-তে পথ শুধু E, accept: শূন্যটি 1 জোড় সংখ্যা। শেষ তিনটি reject-এর কারণ ভিন্ন: w-তে Σ-এর বাইরের চিহ্ন, δ অসম্পূর্ণ (O-এর কোনো move নেই), আর order code-টি কোনো ⟨B, w⟩-ই নয়। তিনটিই নিয়ম (গ)-এর প্রয়োগ। প্রতিটি ক্ষেত্রে loop ঠিক |w| বার ঘোরে, তাই এই ফাংশন কোনো ইনপুটে আটকে থাকতে পারে না।
একই কৌশল ATM-এ কেন চলে না? “M-কে w-এর ওপর চালাও; accept করলে accept, reject করলে reject” — এই যন্ত্র ATM-এর একটি recognizer, decider নয়। DFA ঠিক |w| ধাপ পরে থামে, কিন্তু Turing machine অনন্তকাল চলতে পারে, আর তখন এই simulator-ও চলতে থাকে। কোনো চালাক decider-ও নেই: পর্ব ৫১-এ diagonalization দিয়ে প্রমাণ হবে ATM undecidable. “Simulate করে দেখি” বললেই decider হয় না; প্রতিটি ইনপুটে থামার যুক্তি আলাদা করে দিতে হয়।
৬ · Encoding-এর আকার — unary বনাম binary
Computability-র প্রশ্নে (“algorithm আছে কি না”) reasonable encoding-এর বাছাই গুরুত্বহীন। কিন্তু complexity-র প্রশ্নে (“কত দ্রুত”) একটি বিষয় খুব গুরুত্বপূর্ণ: সময় মাপা হয় ইনপুট string-এর দৈর্ঘ্যের ফাংশন হিসেবে, ইনপুটের সংখ্যার মান দিয়ে নয়। আর দৈর্ঘ্য নির্ভর করে encoding-এর ওপর।
সংখ্যা n লেখার তিনটি উপায় ভাবুন। Unary: n-টি 1, যেমন পরীক্ষার খাতায় দাগ টেনে গোনা; দৈর্ঘ্য n. Binary: দৈর্ঘ্য len2(n) = ⌊log2 n⌋ + 1. দশমিক: len10(n) = ⌊log10 n⌋ + 1. Binary আর দশমিকের পার্থক্য সামান্য, unary-র পার্থক্য বিশাল।
প্রতিটি n ≥ 1-এর জন্য len10(n) ≤ len2(n) ≤ 4 · len10(n), কিন্তু unary দৈর্ঘ্য n ≥ 2len2(n) − 1.
- log10 n ≤ log2 n, আর ⌊·⌋ ক্রম রাখে, তাই len10(n) ≤ len2(n). — n ≥ 1-এ log10 n = log2 n / log2 10
- d = len10(n) হলে n < 10d, তাই log2 n < d · log2 10 < 3.33d. — log2 10 ≈ 3.3219
- ফলে len2(n) < 3.33d + 1 ≤ 4d, যখন d ≥ 2. — 3.33d + 1 ≤ 4d ⇔ d ≥ 1.5
- d = 1 হলে n ≤ 9 < 16, তাই len2(n) ≤ 4 = 4d. — সরাসরি
- b = len2(n) বিটের সংখ্যার সবচেয়ে বড় বিটটি 1, তাই n ≥ 2b − 1. ∎ — binary-র সংজ্ঞা
অর্থাৎ binary আর দশমিক পরস্পরের ধ্রুবক গুণের মধ্যে (Big-O-র ভাষায় একই; DSA কোর্সের পর্ব ০৪ দেখুন), কিন্তু unary binary-র তুলনায় exponential লম্বা। এবার এর ফল দেখুন। PRIME-এর সবচেয়ে সরল decider হলো trial division: 2, 3, 4, … করে √n পর্যন্ত ভাগ করে দেখা। Prime n-এ প্রায় √n বার ভাগ লাগে।
import math
def PRIME(n): # trial division; also counts the divisions
if n < 2:
return False, 0
d, steps = 2, 0
while d * d <= n:
steps += 1
if n % d == 0:
return False, steps
d += 1
return True, steps
print(f"{'n':>13} {'unary':>13} {'binary':>6} {'decimal':>7} {'prime':>5} {'divisions':>9}")
for n in [101, 65537, 1000003, 1000000007, 1099511627689]:
p, steps = PRIME(n)
print(f"{n:>13} {n:>13} {n.bit_length():>6} {len(str(n)):>7} {p!s:>5} {steps:>9}")
print("\nbits b -> about 2^(b/2) divisions for a b-bit prime")
for b in [20, 40, 64, 128, 2048]:
print(f"b = {b:4}: 2^{b // 2} = about 10^{b // 2 * math.log10(2):.1f}")আসল আউটপুট (ব্রাউজারের Python; শেষ সংখ্যাটির জন্য প্রায় দশ লাখ ভাগ লাগে, তাই এক সেকেন্ডের মতো সময় নিতে পারে):
n unary binary decimal prime divisions
101 101 7 3 True 9
65537 65537 17 5 True 255
1000003 1000003 20 7 True 999
1000000007 1000000007 30 10 True 31621
1099511627689 1099511627689 40 13 True 1048574
bits b -> about 2^(b/2) divisions for a b-bit prime
b = 20: 2^10 = about 10^3.0
b = 40: 2^20 = about 10^6.0
b = 64: 2^32 = about 10^9.6
b = 128: 2^64 = about 10^19.3
b = 2048: 2^1024 = about 10^308.3
পাঁচটি সংখ্যাই মৌলিক (শেষটি 240 − 87). ভাগের সংখ্যা প্রায় √n: 1000003-এ 999, 40-বিটের সংখ্যায় 1048574 ≈ 220. Binary দৈর্ঘ্য b-এর হিসাবে এটি প্রায় 2b/2, অর্থাৎ exponential. Unary দৈর্ঘ্য n-এর হিসাবে একই সংখ্যা √n, অর্থাৎ দৈর্ঘ্যের চেয়েও কম। একই algorithm, একই ধাপ, অথচ এক encoding-এ “দ্রুত”, অন্যটিতে “ধীর”। 2048-বিটের সংখ্যায় 10308-এর মতো ভাগ কোনো কম্পিউটারে কোনোদিন শেষ হবে না।
তাহলে কি PRIME কঠিন? না। ২০০২ সালে Manindra Agrawal, Neeraj Kayal আর Nitin Saxena (AKS) দেখান PRIME ∈ P, অর্থাৎ binary দৈর্ঘ্যের polynomial সময়ে decide করা যায়। Trial division শুধু একটি ধীর algorithm, সমস্যাটির সীমা নয়। বাস্তবে Miller–Rabin-এর মতো randomized পরীক্ষা আরও দ্রুত; বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২৫-এ।
এই উদাহরণ থেকেই pseudo-polynomial ধারণা আসে। যে algorithm-এর সময় ইনপুটের সংখ্যাগুলোর মানের polynomial, কিন্তু তাদের binary দৈর্ঘ্যের polynomial নয়, তাকে pseudo-polynomial বলে। বিখ্যাত উদাহরণ subset sum-এর dynamic programming, সময় O(n · T), যেখানে T লক্ষ্য-যোগফল (DSA কোর্সের পর্ব ৫৩)। T-কে unary-তে দিলে এটি polynomial, binary-তে দিলে নয়; আর subset sum NP-complete (পর্ব ৬১)। Unary encoding তাই “অযৌক্তিক” বলে ধরা হয়: সে ইনপুটকে কৃত্রিমভাবে লম্বা করে কঠিন সমস্যাকে সহজ দেখায়।
সংক্ষেপে নিয়ম: সংখ্যা binary বা দশমিকে, graph matrix বা edge-তালিকায়, সূত্র সাধারণ লেখায়, যন্ত্র তার transition-তালিকায়। এগুলোর যেকোনো দুটি reasonable encoding-এর মধ্যে polynomial সময়ে রূপান্তর চলে, তাই P, NP-র মতো শ্রেণি encoding-এর বাছাইয়ে বদলায় না। শুধু unary-র মতো “ফোলানো” encoding এই নিশ্চয়তা ভাঙে।
৭ · Optimization থেকে decision — বাজারঘরের ডেলিভারি রুট
বাজারঘরের ভ্যান গুদাম W থেকে বেরিয়ে তিনটি ঠিকানা A, B, C-তে মাল দিয়ে W-তে ফেরে। প্রতিটি রাস্তার খরচ (টাকা, কাল্পনিক উদাহরণ) নিচের মানচিত্রে। ম্যানেজার জানতে চান সবচেয়ে সস্তা ঘোরা (tour) কোনটি; এটি একটি optimization problem. Decision রূপ:
বাজারঘরের ডেলিভারি মানচিত্র
ছয়টি রাস্তা, প্রতিটির গায়ে খরচ। সবুজ মোটা রেখা সবচেয়ে সস্তা ঘোরা W → A → B → C → W, খরচ 4 + 3 + 2 + 5 = 14.
ধরুন আপনার কাছে শুধু একটি “জাদুর বাক্স” আছে, যা TOUR decide করে: ⟨G, k⟩ দিলে হ্যাঁ/না বলে। এটি দিয়ে সবচেয়ে কম খরচ বের করা যায়, আর খুব কম প্রশ্নে।
খরচ পূর্ণসংখ্যা, আর সবচেয়ে কম খরচ OPT জানা একটি পরিসরে 0 ≤ OPT ≤ U. তাহলে TOUR-এর decider-কে বড়জোর ⌈log2(U + 1)⌉ বার প্রশ্ন করে OPT বের করা যায়।
প্রমাণ. [lo, hi] = [0, U] থেকে শুরু; invariant: OPT ∈ [lo, hi]. প্রতিবার mid = ⌊(lo + hi)/2⌋ নিয়ে TOUR(mid) জিজ্ঞেস করি। হ্যাঁ হলে OPT ≤ mid, তাই hi ← mid; না হলে OPT > mid, তাই lo ← mid + 1. দুই ক্ষেত্রেই invariant থাকে, আর পরিসরের আকার s থেকে কমে বড়জোর ⌈s/2⌉ হয়। আকার U + 1 থেকে 1-এ নামতে বড়জোর ⌈log2(U + 1)⌉ বার অর্ধেক করতে হয়; তখন lo = hi = OPT. ∎
U হিসেবে সব রাস্তার খরচের যোগফল নেওয়া যায়, কারণ যেকোনো ঘোরা প্রতিটি রাস্তা বড়জোর একবার ব্যবহার করে। এখানে U = 4 + 6 + 5 + 3 + 7 + 2 = 27, তাই বড়জোর ⌈log2 28⌉ = 5টি প্রশ্ন। U-এর binary দৈর্ঘ্য ইনপুটের দৈর্ঘ্যের polynomial, তাই প্রশ্নের সংখ্যাও polynomial: decision রূপ polynomial সময়ে হলে optimization রূপের খরচটিও polynomial সময়ে মেলে।
| প্রশ্ন k | |
| উত্তর | |
| [lo, hi] | |
| প্রশ্ন গোনা |
- শুরু। lo = 0, hi = 27 (সব রাস্তার যোগফল)। OPT এই পরিসরেই আছে; বাক্সকে এখনো কিছু জিজ্ঞেস করা হয়নি।
- প্রশ্ন k = 13. mid = ⌊(0 + 27)/2⌋ = 13. তিনটি ঘোরার খরচ 14, 19, 21; কোনোটিই ≤ 13 নয়, উত্তর না। তাই lo = 14.
- প্রশ্ন k = 20. mid = ⌊(14 + 27)/2⌋ = 20. 14 আর 19 খরচের ঘোরা ≤ 20, উত্তর হ্যাঁ। hi = 20.
- প্রশ্ন k = 17. mid = ⌊(14 + 20)/2⌋ = 17. 14 ≤ 17, হ্যাঁ। hi = 17.
- প্রশ্ন k = 15. mid = ⌊(14 + 17)/2⌋ = 15. হ্যাঁ। hi = 15.
- প্রশ্ন k = 14. mid = ⌊(14 + 15)/2⌋ = 14. হ্যাঁ, hi = 14 = lo. থামা: OPT = 14, ঠিক ⌈log2 28⌉ = 5টি প্রশ্নে।
খরচ জানা গেল, কিন্তু রুটটি কোনটি? এখানেও decider যথেষ্ট। একটি একটি করে রাস্তা মুছে জিজ্ঞেস করুন “এখনো খরচ ≤ 14-এর ঘোরা আছে?” হ্যাঁ হলে রাস্তাটি বাদ, না হলে ফিরিয়ে রাখুন। শেষে যা থাকে, সেটিই একটি সেরা ঘোরা; কেন, তার প্রমাণ অনুশীলন ৪-এ। ছোট উত্তর থেকে বড় উত্তর গড়ার এই কৌশলের নাম self-reducibility. নিচের ব্লকে “জাদুর বাক্স” হলো সব ঘোরা গুনে দেখা একটি ধীর decider, কিন্তু খোঁজার অংশটি বাক্সকে শুধু হ্যাঁ/না প্রশ্নই করে।
from itertools import permutations
ROADS = {("W", "A"): 4, ("W", "B"): 6, ("W", "C"): 5,
("A", "B"): 3, ("A", "C"): 7, ("B", "C"): 2}
calls = 0
def cost(tour, w): # a missing road costs "infinity"
legs = zip(tour, tour[1:] + tour[:1])
return sum(w.get((a, b), w.get((b, a), 10**6)) for a, b in legs)
def TOUR(w, k): # decision: a tour W -> A, B, C -> W of cost <= k?
global calls
calls += 1
return any(cost(("W",) + p, w) <= k for p in permutations("ABC"))
lo, hi = 0, sum(ROADS.values()) # some tour costs at most the sum of all roads
while lo < hi: # binary search on the budget k
mid = (lo + hi) // 2
yes = TOUR(ROADS, mid)
print(f"TOUR(k = {mid:2}) -> {'yes' if yes else 'no'}")
if yes:
hi = mid
else:
lo = mid + 1
print("cheapest tour costs", lo, "| decision calls:", calls)
w = dict(ROADS) # search from decision: drop roads we do not need
for road in list(w):
saved = w.pop(road)
if not TOUR(w, lo):
w[road] = saved # without this road no tour of cost <= lo exists
print("roads kept:", sorted(w), "| total calls:", calls)আসল আউটপুট (ব্রাউজারের Python):
TOUR(k = 13) -> no
TOUR(k = 20) -> yes
TOUR(k = 17) -> yes
TOUR(k = 15) -> yes
TOUR(k = 14) -> yes
cheapest tour costs 14 | decision calls: 5
roads kept: [('A', 'B'), ('B', 'C'), ('W', 'A'), ('W', 'C')] | total calls: 11
প্রশ্নের ক্রম 13, 20, 17, 15, 14 হুবহু stepper-এর, আর 5টি প্রশ্নেই OPT = 14. তারপর ছয়টি রাস্তার প্রতিটির জন্য একটি করে প্রশ্ন, মোট 11. টিকে থাকা চারটি রাস্তা W–A, A–B, B–C, C–W: ঠিক মানচিত্রের সবুজ ঘোরা। A–C (7) আর W–B (6) বাদ পড়েছে, কারণ এদের ছাড়াও 14 খরচের ঘোরা থাকে।
এখানে decider-টি সব ঘোরা গুনছে; তিনটি ঠিকানায় তা সহজ, কিন্তু n ঠিকানায় (n − 1)!/2টি ঘোরা। TOUR আসলে বিখ্যাত travelling salesman problem-এর decision রূপ, আর এটি NP-complete বলে প্রমাণিত (Hamiltonian cycle থেকে reduction, পর্ব ৫৯–৬১)। তাই polynomial সময়ের decider জানা নেই, আর P বনাম NP প্রশ্ন (পর্ব ৬৩) মীমাংসিত না হওয়া পর্যন্ত কেউ জানে না এমন decider আদৌ আছে কি না। কিন্তু উপরের যুক্তি দেখায়: decision রূপ যত কঠিন, optimization রূপ তার চেয়ে polynomial গুণের বেশি কঠিন নয়। Search আর decision-এর এই সম্পর্কের পূর্ণ আলোচনা পর্ব ৬২-এ।
৮ · বাজারঘরের প্রশ্নের মানচিত্র আর গণনার সীমা
এই কোর্সে বাজারঘরের যত প্রশ্ন আসবে, সবগুলো এখন একই ভাষায় লেখা যায়। নিচের সারণি প্রতিটি প্রশ্নকে language বানিয়ে দেখায় কোন যন্ত্র তাকে decide করে, আর কোন পর্বে সেটি প্রমাণ হবে।
| বাজারঘরের প্রশ্ন | Language | যথেষ্ট যন্ত্র | কোথায় |
|---|---|---|---|
| Order code বৈধ? | LORDER = {BG-dddd}, 104টি string | Finite automaton | অনুশীলন ১, পর্ব ০৭ |
| Coupon code বৈধ? | {A–Z, 0–9}-এর ওপর দৈর্ঘ্য 6-এর সব string, 366 = 2176782336টি | Finite automaton | পর্ব ০৭–০৮ |
| সেন্সর-লাইনে জোড় সংখ্যক 1? | {w ∈ {0,1}∗ : w-এ জোড় সংখ্যক 1} | দুই state-এর DFA | উপরের EVEN, পর্ব ০৭ |
| Order query-র বন্ধনী সুষম? | সুষম বন্ধনীর string | Pushdown automaton; কোনো DFA নয় | পর্ব ১৭ (regular নয়), ২৫, ৩২ |
| খরচ ≤ k-এর ডেলিভারি ঘোরা? | TOUR | Decider আছে; দ্রুত decider অজানা | পর্ব ৫৯–৬৩ |
| এই validator program কি সবসময় থামবে? | HALTTM-এর রূপ | কোনো decider নেই | পর্ব ৫১–৫৩ |
শেষ সারিটি এই কোর্সের সবচেয়ে বড় চমক, আর তার একটি সহজ পূর্বাভাস এখনই দেওয়া যায়। প্রতিটি decider-কে একটি সসীম string ⟨M⟩ হিসেবে লেখা যায়; তাই সব decider-কে shortlex ক্রমে একটি তালিকায় সাজানো যায়, অর্থাৎ decider-এর সেট countable. অথচ পর্ব ০২-এ দেখেছেন, Σ∗-এর সব উপসেটের সেট P(Σ∗) uncountable (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮-এর Cantor-এর diagonal). Language অসংখ্য বেশি, decider কম। তাই এমন language থাকতেই হবে যার কোনো decider নেই, অর্থাৎ এমন হ্যাঁ/না প্রশ্ন যার কোনো algorithm নেই। এই গণনা-যুক্তি শুধু অস্তিত্ব দেখায়; একটি নির্দিষ্ট, স্বাভাবিক প্রশ্ন (HALTTM) undecidable, তার প্রমাণ পর্ব ৫১-এর কাজ।
“বস্তুকে প্রতীকে লেখা” ধারণার দুটি বড় মুহূর্ত। ১৯৩১ সালে Kurt Gödel প্রতিটি গাণিতিক সূত্র আর প্রমাণকে একটি স্বাভাবিক সংখ্যায় লেখার কৌশল (Gödel numbering) দিয়ে দেখান, গণিত নিজের সম্পর্কে কথা বলতে পারে। ১৯৩৬ সালে Alan Turing তাঁর যন্ত্রের পুরো নিয়ম-তালিকাকে একটি সংখ্যায় (description number) লিখে universal machine-এর ধারণা দেন, আর প্রমাণ করেন কিছু প্রশ্ন কোনো যন্ত্রই সাধারণভাবে decide করতে পারে না। “Halting problem” নামটি পরে চালু হয়; অনেক উৎস ১৯৫০-এর দশকে Martin Davis-এর লেখাকে এর কৃতিত্ব দেয়। Complexity-তে encoding-এর আকার নিয়ে সতর্কতা Garey ও Johnson-এর ১৯৭৯ সালের বই Computers and Intractability-তে বিস্তারিত আলোচিত।
আরও গভীরে: Encoding আরও “ঘন” হলে complexity লাফ দিতে পারে। একটি graph-কে তার edge-তালিকার বদলে একটি ছোট Boolean circuit দিয়ে দেওয়া যায় (succinct representation); Galperin ও Wigderson (১৯৮৩) আর Papadimitriou ও Yannakakis (১৯৮৬)-এর কাজে দেখা যায়, অনেক সহজ graph-প্রশ্ন এই রূপে exponential-time-এর শ্রেণিতে কঠিন হয়ে ওঠে বলে পরিচিত। আবার কিছু প্রশ্নে সব string-ই instance নয়, শুধু “প্রতিশ্রুতি” মানা string-গুলো; এদের promise problem বলে (Even, Selman ও Yacobi, ১৯৮৪), আর approximation (পর্ব ৭১) ও cryptography-তে এগুলো স্বাভাবিকভাবে আসে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Decision problem আর language-এর সম্পর্ক? LP = {⟨x⟩ : x yes-instance}; সমস্যার algorithm ⇔ LP decidable.
- ADFA decidable কেন? DFA ঠিক |w| ধাপে থামে, তাই simulation সবসময় শেষ হয়।
- Trial division কি polynomial? √n ধাপ = 2b/2, b = বিটের সংখ্যা; তাই না, exponential. তবু PRIME ∈ P (AKS).
- Decider আর recognizer-এর পার্থক্য? Decider সব ইনপুটে থামে; recognizer L-এর বাইরে চিরকাল চলতে পারে।
- Optimization থেকে decision রূপ? একটি সীমা k যোগ করে “খরচ ≤ k?”; উল্টো দিকে binary search.
৯ · AI-এর যুগে — encoding আর decision-এর দাবি যাচাই
AI সহকারীকে “এই সমস্যাটি language হিসেবে লেখো” বা “এর complexity কত” জিজ্ঞেস করলে উত্তর সাধারণত আত্মবিশ্বাসী আর সুন্দর করে সাজানো আসে। কিন্তু এই বিষয়ে কয়েকটি ভুল AI প্রায়ই করে, আর ভুলগুলো সূক্ষ্ম বলে চোখ এড়িয়ে যায়।
| AI-এর ভুল | কেন ভুল | যাচাইয়ের উপায় |
|---|---|---|
| “√n ধাপ, তাই polynomial” | সময় মাপতে হয় দৈর্ঘ্য b ≈ log2 n-এ | ধাপকে b দিয়ে লিখুন: 2b/2 |
| Decision রূপে সীমা k নেই | “সেরা রুট কোনটি” হ্যাঁ/না প্রশ্ন নয় | উত্তর কি শুধু হ্যাঁ/না? k কি ইনপুটে? |
| ভুল-গঠনের string-এর কথা নেই | Language অস্পষ্ট থেকে যায় | Decoder-এ আবর্জনা string দিয়ে চালান |
| “Simulate করি, তাই decidable” | Simulation না থামলে শুধু recognizer | প্রতিটি ইনপুটে থামার যুক্তি চান |
| “PRIME কঠিন, factoring-এর মতো” | PRIME ∈ P (২০০২); factoring-এর দ্রুত classical algorithm অজানা | Decision বনাম search আলাদা করুন |
| বানানো রেফারেন্স বা theorem নম্বর | উৎস হয়তো নেই | Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে দেখুন |
নিচের prompt-টি AI-কে যাচাইযোগ্য আকারে উত্তর দিতে বাধ্য করে: encoding, ভুল-গঠনের নিয়ম আর থামার যুক্তি আলাদা করে চায়, আর শেষে একটি পরীক্ষা-কোড চায় যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১তত্ত্ব শুধু হ্যাঁ/না প্রশ্ন নিয়ে কাজ করে। তাহলে “সেরা রুট দিন” বা “উৎপাদক দিন” ধরনের আসল কাজের প্রশ্নগুলো কি হারিয়ে যায় না?
হারায় না, কারণ বেশিরভাগ স্বাভাবিক সমস্যায় decision রূপ থেকে বাকি রূপগুলো অল্প কয়েকটি প্রশ্নেই বের করা যায়। দুটি কৌশল প্রায় সবখানে কাজ করে।
- Binary search: খরচ পূর্ণসংখ্যা আর 0 থেকে U-এর মধ্যে হলে “খরচ ≤ k?” প্রশ্ন ⌈log2(U + 1)⌉ বার করলেই সেরা খরচ মেলে। U লিখতে log2 U বিট লাগে, তাই প্রশ্নের সংখ্যা ইনপুটের দৈর্ঘ্যের মধ্যেই থাকে। ডেলিভারি রুটের উদাহরণে 27 পর্যন্ত পরিসরে 5টি প্রশ্নই যথেষ্ট ছিল।
- Self-reducibility: উত্তর জানার পর আসল সমাধান টুকরো টুকরো গড়া। SAT-এ n টি variable থাকলে x1 = সত্য বসিয়ে জিজ্ঞেস করুন “এখনো satisfiable?” হ্যাঁ হলে রাখুন, না হলে x1 = মিথ্যা নিশ্চিত। এভাবে প্রতিটি variable-এর জন্য একটি করে প্রশ্নে, মোট n + 1টি প্রশ্নে একটি সত্য-করা মান-বসানো পাওয়া যায়। রুটের ক্ষেত্রে আমরা রাস্তা মুছে মুছে একই কাজ করেছি।
এই কারণেই NP-completeness-এর তত্ত্ব (পর্ব ৫৯–৬১) decision রূপে লেখা হলেও বাস্তবের optimization প্রশ্নের ওপর সরাসরি প্রযোজ্য: decision রূপ polynomial সময়ে হলে optimization রূপও হয়, আর decision রূপ কঠিন হলে optimization রূপ আরও সহজ হতে পারে না। তবে সাবধান: সব সমস্যায় এই সেতু এত সহজ নয়। যে সমস্যায় খরচ বাস্তব সংখ্যা, বা যেখানে “খরচ ≤ k?” প্রশ্নের decider আছে কিন্তু সমস্যাটি self-reducible নয়, সেখানে আলাদা যুক্তি লাগে। আবার decision রূপের উত্তর সবসময় “হ্যাঁ” হলেও সমাধান খোঁজা কঠিন হতে পারে, যা প্রশ্ন ০৫-এর বিষয়। Search আর decision-এর এই সূক্ষ্ম সম্পর্ক পর্ব ৬২-এ বিস্তারিত।
মূল উপলব্ধি: হ্যাঁ/না প্রশ্ন সংকীর্ণ শোনায়, কিন্তু ভালো করে বেছে নেওয়া decision রূপ পুরো সমস্যার কঠিনতা ধরে রাখে। তাই তত্ত্ব সরল থাকে, আর বাস্তবের সঙ্গে সংযোগ হারায় না।
প্র ০২Unary encoding-কে “অযৌক্তিক” বলা হয় কেন? সংখ্যা তো unary-তেও নির্ভুলভাবে লেখা যায়।
Unary-তে লেখা নির্ভুল, injective, decode-ও সহজ; computability-র প্রশ্নে এটি পুরোপুরি চলে। সমস্যা complexity-তে। Complexity মাপে সময়কে ইনপুটের দৈর্ঘ্যের ফাংশন হিসেবে। 240-এর কাছাকাছি একটি সংখ্যা binary-তে 40 অক্ষর, unary-তে এক লাখ কোটির বেশি অক্ষর। যে algorithm প্রায় দশ লাখ ধাপ নেয়, সে 40-অক্ষরের ইনপুটে খুব ধীর, কিন্তু লাখ কোটি অক্ষরের ইনপুটে অবিশ্বাস্য দ্রুত দেখায়। Algorithm একই, শুধু মাপার ফিতে বদলেছে।
এর সবচেয়ে বিখ্যাত ফল pseudo-polynomial algorithm. Subset sum-এ n টি সংখ্যা আর লক্ষ্য T দেওয়া; dynamic programming O(n · T) সময়ে উত্তর দেয়। T unary-তে দিলে এটি ইনপুট-দৈর্ঘ্যের polynomial, অর্থাৎ “unary subset sum” P-তে আছে। T binary-তে দিলে T ≈ 2b, আর algorithm exponential; সাধারণ subset sum NP-complete. Michael Garey আর David Johnson তাঁদের ১৯৭৯ সালের বইতে এই পার্থক্য থেকে “strong NP-completeness” ধারণা দাঁড় করান: যে সমস্যা সংখ্যাগুলো unary-তে দিলেও NP-complete থাকে (যেমন 3-partition বা বেশিরভাগ graph সমস্যা), তার pseudo-polynomial algorithm থাকার আশা নেই, যদি না P = NP.
বাস্তবেও এর অর্থ আছে। বাজারঘরের ভ্যানে মালের ওজন যদি কয়েক কেজির পূর্ণসংখ্যা হয়, O(n · T)-এর DP চমৎকার চলে। কিন্তু একই সমস্যায় ওজন গ্রামে, দশমিকসহ দিলে T লাখ-কোটিতে পৌঁছায়, আর একই কোড অচল। তাই “এই algorithm দ্রুত” বলার আগে জিজ্ঞেস করতে হয়: কিসের হিসাবে দ্রুত? সংখ্যার মানের, নাকি সংখ্যা লিখতে যত অক্ষর লাগে তার?
মূল উপলব্ধি: Encoding-কে “অযৌক্তিক” বলার কারণ ভুল নয়, অপচয়। ফোলানো ইনপুট কঠিন সমস্যাকে সহজ দেখায়, তাই complexity-র তুলনা ন্যায্য রাখতে সংখ্যা binary-তে লেখার নিয়ম।
প্র ০৩ATM আর HALTTM-এ একটি যন্ত্রের বর্ণনা ⟨M⟩ ইনপুট হিসেবে যায়। “Program-ই data” ধারণাটি কোথা থেকে এল, আর কেন এটি এত শক্তিশালী?
ধারণাটির শিকড় যুক্তিবিদ্যায়। ১৯৩১ সালে Kurt Gödel তাঁর incompleteness theorem প্রমাণ করতে প্রতিটি চিহ্ন, সূত্র আর প্রমাণকে একটি স্বাভাবিক সংখ্যায় লেখার কৌশল বানান। এর ফলে “এই সূত্রটি প্রমাণযোগ্য” কথাটিও সংখ্যা নিয়ে একটি গাণিতিক বক্তব্য হয়ে গেল, আর গণিত নিজের সম্পর্কে কথা বলতে পারল। সেখান থেকেই আত্ম-উল্লেখের (self-reference) সেই বিখ্যাত সূত্র আসে।
১৯৩৬ সালে Alan Turing একই কাজ যন্ত্রের সঙ্গে করেন। প্রতিটি Turing machine-এর নিয়ম-তালিকা একটি সসীম তালিকা, তাই একটি সংখ্যায় (তাঁর ভাষায় description number) লেখা যায়। তারপর তিনি দেখান একটি universal যন্ত্র আছে, যা অন্য যেকোনো যন্ত্রের বর্ণনা ইনপুট হিসেবে নিয়ে তাকে অনুকরণ করে (পর্ব ৪৮)। আজকের কম্পিউটারের stored-program নকশা, যেখানে program আর data একই memory-তে থাকে, এই ধারণার প্রকৌশল-রূপ বলে প্রায়ই বর্ণিত হয়। Compiler, interpreter, virus scanner, এমনকি আপনার IDE-র “unused variable” সতর্কবার্তাও program-কে data হিসেবে পড়ে।
শক্তির অন্য দিকটি সীমা। ⟨M⟩ যখন string, তখন যন্ত্রকে তার নিজের বর্ণনাও ইনপুট দেওয়া যায়: M-কে ⟨M⟩-এর ওপর চালানো। পর্ব ৫১-এর diagonalization ঠিক এখানেই কামড় দেয়: ধরে নিন HALTTM-এর একটি decider H আছে; H ব্যবহার করে এমন একটি যন্ত্র বানানো যায় যা নিজের বর্ণনা পেলে H-এর ভবিষ্যদ্বাণীর উল্টো কাজ করে, আর বিরোধ আসে। Encoding ছাড়া এই যুক্তি লেখাই যেত না, কারণ “একটি যন্ত্র আরেকটি যন্ত্রকে ইনপুট নেয়” কথাটির অর্থই encoding থেকে আসে।
মূল উপলব্ধি: ⟨M⟩ চিহ্নটি দেখতে নিরীহ, কিন্তু এটিই universal computer-এর সম্ভাবনা আর undecidability-র অনিবার্যতা, দুটিকেই একসঙ্গে খুলে দেয়।
প্র ০৪Encoding বদলে কি কোনো কঠিন সমস্যাকে সহজ বানানো যায়? যেমন ইনপুটের সঙ্গে উত্তরটিও লিখে দিলে?
চমৎকার প্রশ্ন, আর এর উত্তরই দেখায় কেন reasonable encoding-এর শর্তগুলো দরকার। ধরুন কেউ বলল, “আমি প্রতিটি ⟨M, w⟩-এর শেষে একটি বিট জুড়ে দেব: 1 যদি M, w-এ থামে, 0 যদি না থামে। তাহলে HALTTM-এর decider শুধু শেষ বিট পড়বে!” Language-টি সত্যিই তুচ্ছ হয়ে গেল। কিন্তু চালাকিটা লুকিয়ে আছে encoding ফাংশনে: x থেকে ⟨x⟩ বানাতে হলে আগে জানতে হবে M থামে কি না, অর্থাৎ encoding নিজেই একটি undecidable কাজ। Reasonable encoding-এর শর্ত ২ ঠিক এটি নিষেধ করে: encoding algorithm দিয়ে বানানো যেতে হবে।
Complexity-তে একই প্রতারণা সূক্ষ্ম রূপে আসে। SAT-এর প্রতিটি সূত্রের সঙ্গে একটি সত্য-করা মান-বসানো (থাকলে) জুড়ে দিলে satisfiability যাচাই সহজ হয়ে যায়, কিন্তু সেই মান-বসানো খুঁজে বের করতে হয়তো exponential সময় লাগে। তাই complexity-র জন্য শর্তটি আরও কড়া: encode আর decode polynomial সময়ে হতে হবে। এই শর্তে দুটি reasonable encoding-এর মধ্যে রূপান্তর polynomial সময়ে চলে, ফলে P, NP, PSPACE-এর মতো শ্রেণি encoding বাছাইয়ে বদলায় না।
উল্টো দিকেও সতর্কতা আছে। Encoding খুব “ঘন” হলে সমস্যা কঠিন হয়ে উঠতে পারে: একটি বিশাল graph-কে ছোট একটি circuit দিয়ে বর্ণনা করলে (succinct representation) অনেক সহজ প্রশ্ন exponential সময়ের শ্রেণিতে চলে যায়, কারণ ইনপুট ছোট হলেও আসল বস্তুটি exponential বড়। তাই “এই সমস্যা কত কঠিন” প্রশ্নের সঙ্গে সবসময় একটি অদৃশ্য অংশ থাকে: “কোন encoding-এ?”
মূল উপলব্ধি: Encoding বস্তুর নিরপেক্ষ বর্ণনা হতে হবে, উত্তরের ইঙ্গিত নয়। শর্তগুলো (injective, দক্ষভাবে লেখা-পড়া যায়, অপচয়হীন) মানলে computability আর complexity দুটিই encoding-এর বাছাই থেকে স্বাধীন হয়।
প্র ০৫এমন কি হয় যে হ্যাঁ/না উত্তর সহজ, অথচ আসল সমাধান খোঁজা কঠিন বলে মনে করা হয়?
হয়, আর দুটি বিখ্যাত উদাহরণ আছে। প্রথমটি সংখ্যা নিয়ে। “n কি যৌগিক (composite)?” একটি decision problem, আর AKS (২০০২)-এর ফলে এটি P-তে, কারণ PRIME P-তে হলে তার complement-ও P-তে। কিন্তু search রূপ, “n-এর একটি অতুচ্ছ উৎপাদক দিন”, অর্থাৎ factoring, এর কোনো polynomial সময়ের classical algorithm জানা নেই। RSA-র মতো পদ্ধতির নিরাপত্তা এই অনুমানের ওপর দাঁড়িয়ে। মজার ব্যাপার, AKS জানায় উৎপাদক আছে, কিন্তু কোনটি, তা বলে না। ১৯৯৪ সালে Peter Shor দেখান quantum কম্পিউটারে factoring polynomial সময়ে হয় (পর্ব ৭৫), কিন্তু classical জগতে প্রশ্নটি খোলা।
দ্বিতীয় উদাহরণ খেলার তত্ত্বে। John Nash ১৯৫০ সালে প্রমাণ করেন প্রতিটি সসীম খেলায় অন্তত একটি (mixed) Nash equilibrium থাকে। তাই decision রূপ “equilibrium আছে কি?” এর উত্তর সবসময় হ্যাঁ, তুচ্ছ। কিন্তু একটি equilibrium খুঁজে বের করা PPAD নামের শ্রেণিতে complete বলে প্রমাণিত (২০০৬ সালের দিকে Daskalakis, Goldberg ও Papadimitriou, আর Chen ও Deng-এর কাজ), আর এর দ্রুত algorithm আছে বলে কেউ জানে না।
এই দুই উদাহরণের সাধারণ সূত্র: উত্তর “হ্যাঁ” জানা থাকলেও সেই হ্যাঁ-এর সাক্ষী খোঁজা আলাদা কাজ। যে search problem-এ সাক্ষী সবসময় থাকে, তাদের শ্রেণির নাম TFNP. সেখানে decision রূপ কিছুই বলে না, তাই প্রশ্ন ০১-এর binary search বা self-reducibility কাজে আসে না। SAT-এর মতো NP-complete সমস্যায় self-reducibility খাটে বলেই সেখানে decision আর search সমান কঠিন।
মূল উপলব্ধি: “সমাধান আছে কি না জানা” আর “সমাধানটি হাতে পাওয়া” এক নয়। Decision রূপ বাছাইয়ের সময় খেয়াল রাখুন, এটি আসল প্রশ্নের কঠিনতা ধরে রাখছে কি না।
অনুশীলন
একটি নকশা, একটি হিসাব, একটি ভুল-খোঁজা আর একটি প্রমাণ। আগে নিজে চেষ্টা করুন, তারপর উত্তর খুলুন।
-
DFA নকশা (LORDER): Σ = {A–Z, a–z, 0–9, -}-এর ওপর LORDER = {BG-dddd} decide করে এমন একটি DFA-র নকশা করুন। কয়টি state লাগে? Transition table চিহ্নের দল (B, G, -, অঙ্ক, বাকি সব) ধরে লিখুন।
৯টি state: q0, …, q7 আর একটি dead state D. qi মানে “প্রথম i টি অক্ষর ঠিকঠাক মিলেছে”। M = (Q, Σ, δ, q0, F), Q = {q0, …, q7, D}, F = {q7}.
state B G - 0–9 বাকি → q0 q1 D D D D q1 D q2 D D D q2 D D q3 D D q3, q4, q5, q6 D D D পরের q D ∗ q7 D D D D D D D D D D D এর চেয়ে কম state সম্ভব নয়: qi থেকে accept করতে ঠিক 7 − i টি নির্দিষ্ট অক্ষর লাগে, তাই আটটি qi পরস্পর আলাদা আচরণ করে, আর D থেকে কিছুই accept হয় না (নিয়মমাফিক প্রমাণ পর্ব ১৮–১৯-এর পদ্ধতিতে)। যাচাই: একটি scratch script এই DFA-কে {B, G, -, 0, 1, 5, 9, X} চিহ্নের ওপর দৈর্ঘ্য 0 থেকে 8-এর সব 19173961টি string-এ regex
BG-\d{4}-এর সঙ্গে মিলিয়েছে; অমিল 0. -
Encode আর decode (হিসাব): এই পর্বের graph-format (
n:তারপর ক্রম-মানাu-v, u < v) ধরে (ক) vertex 1–5 আর edge {4,5}, {2,1}, {3,2}-এর ⟨G⟩ লিখুন; (খ)5:1-2,2-3,4-5কি CONNECTED-এ আছে? (গ)3:1-3,1-2কি বৈধ ⟨G⟩?(ক) Edge-গুলো (ছোট, বড়) আকারে: (4,5), (1,2), (2,3); ক্রমে সাজালে (1,2), (2,3), (4,5). ⟨G⟩ =
5:1-2,2-3,4-5, দৈর্ঘ্য 13.(খ) এটি (ক)-এর graph-ই। Vertex 1 থেকে BFS পৌঁছায় {1, 2, 3}; 4 আর 5 আলাদা টুকরো। তাই বৈধ instance, কিন্তু না-instance: ∉ CONNECTED.
(গ) না। Edge দুটি নিজেরা ঠিক (1 ≤ u < v ≤ 3), কিন্তু ক্রম উল্টো: canonical রূপ
3:1-2,1-3. Decode করে আবার encode করলে ভিন্ন string আসে, তাই এটি বৈধ ⟨G⟩ নয়, আর নিয়ম (গ) মেনে decider reject করে। তিনটি উত্তরই উপরেরgraph_encoding.py-এর ফাংশন দিয়ে যাচাই করা। -
ভুল খুঁজুন (প্রমাণ): “দাবি: PRIME ∈ P. প্রমাণ: n দেওয়া থাকলে 2 থেকে √n পর্যন্ত প্রতিটি d দিয়ে ভাগ করে দেখি। এতে বড়জোর √n ≤ n টি ভাগ লাগে, প্রতিটি ভাগ polynomial সময়ের, তাই মোট সময় polynomial. ∎” প্রমাণের ভুলটি কোথায়? দাবিটি কি তাহলে মিথ্যা?
ভুল “√n ≤ n, তাই polynomial” ধাপে। P-এর সংজ্ঞায় সময় মাপতে হয় ইনপুটের দৈর্ঘ্যে। ⟨n⟩ binary-তে, দৈর্ঘ্য b = ⌊log2 n⌋ + 1, আর n ≥ 2b − 1. ফলে prime n-এ ভাগের সংখ্যা প্রায় √n ≥ 2(b − 1)/2, যা b-এর exponential. “n-এর polynomial” মানে দৈর্ঘ্যের polynomial নয়; প্রমাণটি আসলে দেখিয়েছে trial division একটি pseudo-polynomial algorithm.
তবু দাবিটি সত্য: AKS (২০০২) একটি সম্পূর্ণ ভিন্ন, b-এর polynomial algorithm দিয়ে PRIME ∈ P প্রমাণ করে। শিক্ষা: সঠিক উপসংহারের ভুল প্রমাণও ভুল প্রমাণ। পরীক্ষায় এমন যুক্তি লিখলে নম্বর কাটা যায়, আর AI প্রায়ই ঠিক এই যুক্তি দেয়।
-
প্রমাণ করুন (decision থেকে search): ধরুন TOUR-এর একটি decider আছে আর OPT জানা। Edge-গুলো যেকোনো ক্রমে একে একে নিন; প্রতিটি e-র জন্য e মুছে জিজ্ঞেস করুন “খরচ ≤ OPT-এর ঘোরা এখনো আছে?” হ্যাঁ হলে e বাদ, না হলে ফিরিয়ে রাখুন। প্রমাণ করুন, শেষে যে edge-গুলো থাকে সেগুলো ঠিক একটি খরচ-OPT ঘোরা গঠন করে।
- Invariant: প্রতিটি ধাপের পর বর্তমান graph-এ খরচ ≤ OPT-এর অন্তত একটি ঘোরা আছে। শুরুতে সত্য (OPT-এর সংজ্ঞা); e বাদ যায় কেবল উত্তর হ্যাঁ হলে, আর ফিরিয়ে রাখলে graph আগের মতো। — induction, ধাপের সংখ্যার ওপর
- তাই শেষ graph Gf-এ খরচ ≤ OPT-এর একটি ঘোরা T আছে; OPT সর্বনিম্ন বলে খরচ(T) = OPT, আর T-এর সব edge Gf-এ। — ধাপ ১, OPT-এর সংজ্ঞা
- ধরুন Gf-এর কোনো edge e, T-তে নেই। e-কে যখন দেখা হয়েছিল, তখনকার graph H; e রাখা হয়েছিল, অর্থাৎ H − e-তে খরচ ≤ OPT-এর ঘোরা ছিল না। — পদ্ধতির নিয়ম
- কিন্তু পরে শুধু edge মোছা হয়, তাই Gf ⊆ H, আর e ∉ T বলে T ⊆ Gf − e ⊆ H − e. তাহলে H − e-তে T একটি খরচ-OPT ঘোরা: বিরোধ। — ধাপ ২–৩
- অতএব Gf-এর প্রতিটি edge T-তে, আর T-এর প্রতিটি edge Gf-এ: Gf-এর edge-সেট ঠিক T. ∎
প্রশ্ন লাগে m টি (m = edge-সংখ্যা), আর OPT খুঁজতে আরও ⌈log2(U + 1)⌉টি। বাজারঘরের উদাহরণে 5 + 6 = 11, ঠিক
tour_from_decision.py-এর আউটপুট।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি বাস্তব প্রশ্নকে language বানিয়ে decide করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- প্রশ্নটিকে হ্যাঁ/না আকারে লেখা (প্রয়োজনে সীমা k যোগ করে)
- Instance-এর সেট আর alphabet Σ ঠিক করা
- Injective, decode-যোগ্য encoding ⟨·⟩ বেছে নেওয়া
- L = {⟨x⟩ : x একটি yes-instance} লেখা
- সব string-এ থামে এমন decider বানানো, যা ভুল-গঠনের string reject করে
নিচের কোনটি decision problem?
- একটি graph-এ দুটি vertex-এর সবচেয়ে কম দূরত্ব কত?
- একটি undirected graph কি connected?
- একটি সংখ্যার সব মৌলিক উৎপাদক কী কী?
- সবচেয়ে সস্তা ডেলিভারি রুটটি কোনটি?
ADFA = {⟨B, w⟩ : B একটি DFA, B w-কে accept করে}-এর একটি decider-কে string BG-0042 দেওয়া হলো, যা কোনো ⟨B, w⟩-এর বৈধ encoding নয়। প্রচলিত নিয়মে কী হওয়া উচিত?
- Decider চিরকাল চলতে থাকবে
- Accept করবে, কারণ string-টি কোনো DFA-র বিরোধিতা করে না
- থেমে reject করবে
- “অনির্ধারিত” নামে তৃতীয় একটি উত্তর দেবে
b বিটের একটি মৌলিক সংখ্যা n-এ trial division (2 থেকে √n পর্যন্ত ভাগ) প্রায় কতটি ভাগ করে, আর input-এর দৈর্ঘ্যের হিসাবে সেটি কেমন?
- প্রায় b টি; linear
- প্রায় b2 টি; polynomial
- প্রায় √n টি; √n ≤ n বলে polynomial
- প্রায় 2b/2 টি; exponential
যন্ত্র S ইনপুট ⟨M, w⟩ পেলে Turing machine M-কে w-এর ওপর চালায়; M accept করলে S accept করে, M reject করলে S reject করে। S সম্পর্কে কোনটি সঠিক?
- S হলো ATM-এর recognizer, কিন্তু decider নয়
- S হলো ATM-এর decider
- S হলো HALTTM-এর decider
- S কোনো language-এর recognizer নয়
একটি সমস্যার খরচ পূর্ণসংখ্যা, আর সবচেয়ে কম খরচ 0 থেকে 1000-এর মধ্যে। “খরচ ≤ k?” প্রশ্নের একটি decider দিয়ে binary search-এ সবচেয়ে কম খরচ বের করতে সবচেয়ে খারাপ ক্ষেত্রে কয়টি প্রশ্ন লাগে?
- 1001টি
- 32টি
- 10টি
- 9টি
Complexity-র প্রশ্নে সংখ্যা লেখার কোন encoding “reasonable” বলে ধরা হয় না?
- Binary
- Unary (n টি 1)
- দশমিক
- Hexadecimal (base 16)
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- সমস্যা চার রকম: decision, function, search, optimization; তত্ত্ব মূলত decision রূপে, কারণ হ্যাঁ/না মানেই language.
- ⟨x⟩ = instance x-এর একটি reasonable encoding: injective, লেখা-পড়া যায়, অপচয়হীন; ভুল-গঠনের string সবসময় reject.
- LP = {⟨x⟩ : x yes-instance}; algorithm আছে ⇔ LP decidable. নাম: PRIME, CONNECTED, ADFA, SAT, ATM, HALTTM.
- Decider সব ইনপুটে থামে, recognizer না-ও থামতে পারে। ADFA decidable; ATM শুধু recognizable.
- সময় মাপা হয় দৈর্ঘ্যে: √n = 2b/2; unary ফোলানো। “খরচ ≤ k?” থেকে binary search আর self-reducibility-তে সেরা সমাধান।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineপরবর্তী পর্বGrammar-এর চার ধরন, প্রতিটির যন্ত্র আর কোথায় decidable language বসে।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর তিনটি শেখার পথ।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৫ · Turing machine-এর পরিচয়পটভূমিComputability আর halting problem-এর প্রথম ঝলক।
- DSA · পর্ব ৬৪ · P বনাম NPপাশের ট্র্যাকNP-complete আর reduction, algorithm-এর দিক থেকে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ১৮ · CardinalityগণিতCountable, uncountable আর Cantor-এর diagonal: কেন বেশিরভাগ language-এর decider নেই।