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

লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — গণনার তত্ত্ব

Theory of Computation Written and Viva Questions — Model Answers, Comparisons and Follow-ups

Taught in Bangla, this practice page gives a five-part template for compare and explain answers, then 17 written questions in five groups, from automata and grammars to computability, complexity and applications, each with marks, difficulty, what examiners look for and where marks are lost. Ten in-page Python (Pyodide) checks verify claims such as the 2^n subset bound, CANYIELD and BPP amplification. It adds five three-minute explanations, a sample viva with 24 short questions, a trap table and honest answers.

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

  • “পার্থক্য লিখুন” প্রশ্নে একই মাপকাঠির ছক বানিয়ে “কখন কোনটি” দিয়ে শেষ করা
  • প্রতিটি উপপাদ্যের শর্ত আগে লেখা: |xy| ≤ p, f(n) ≥ log n, Rice-এর “অতুচ্ছ”
  • প্রমাণিত আর খোলা প্রশ্ন আলাদা রাখা: NL = coNL প্রমাণিত, L বনাম NL আর P বনাম NP খোলা
  • Reduction-এর দিক কখনো উল্টে না ফেলা, আর উত্তরের প্রতিটি সংখ্যা ছোট brute force দিয়ে মিলিয়ে নেওয়া
  • ভাইভায় ছোট করে, শর্তসহ, আর না জানলে সৎভাবে বলা

১ · লিখিত উত্তরের কাঠামো — সংজ্ঞা, ছক, উদাহরণ, কখন কোনটি, সীমা

গণনার তত্ত্বের লিখিত প্রশ্নের বড় অংশ তুলনার: DFA বনাম NFA, pumping lemma বনাম Myhill–Nerode, LL বনাম LR, NP-hard বনাম NP-complete. দুটি ট্রেনের তুলনায় একই প্রশ্ন দুটিকেই করতে হয়: কোথা থেকে কোথায়, কত সময়; একটির ভাড়া আর অন্যটির গতি বললে তুলনা হয় না। উত্তরেও তা-ই: একই সারির ছক, তারপর এমন উদাহরণ, যেখানে একটি খাটে আর অন্যটি খাটে না।

পাঁচ অংশের কাঠামো
সংজ্ঞা (tuple বা প্রতীকসহ) → তুলনার ছক → উদাহরণ ও প্রতিউদাহরণ → কখন কোনটি → সীমা ও সাধারণ ভুল
  1. সংজ্ঞা: দুটি ধারণাই আনুষ্ঠানিকভাবে, শর্তসহ। যেমন “DFA-তে δ: Q × Σ → Q, আর তা total”.
  2. তুলনার ছক: তিন থেকে ছয়টি সারি, প্রতিটি সারিতে একই প্রশ্ন দুই ধারণার জন্য।
  3. উদাহরণ ও প্রতিউদাহরণ: ছোট ও নির্দিষ্ট: চার state-এর যন্ত্র, তিন নিয়মের grammar, চার অক্ষরের string.
  4. কখন কোনটি: পরীক্ষক এখানেই বোঝেন আপনি শুধু মুখস্থ করেননি।
  5. সীমা: কোন শর্ত বাদ দিলে দাবি ভাঙে, কোনটি এখনো খোলা প্রশ্ন, আর সাধারণত কোথায় ভুল হয়।
প্রশ্নের ধরনসংজ্ঞাছক বা নির্মাণউদাহরণকখন কোনটি ও সীমা
৫ নম্বর (ছোট তুলনা)১২১১
১০ নম্বর (পূর্ণ তুলনা বা ব্যাখ্যা)২৩৩২

এই ভাগ কোনো নির্দিষ্ট পরীক্ষার নিয়ম নয়; আপনার পরীক্ষার নির্দেশনা আলাদা হলে সেটিই মানুন। ১৮০ মিনিটে ৯০ নম্বর হলে ১০ নম্বরের প্রশ্নে কুড়ি মিনিট। আটকে গেলে সংজ্ঞা আর ছক লিখে এগিয়ে যান; কাঠামোতেই অর্ধেক নম্বর। নিচের stepper-এ ক-০১ প্রশ্নের উত্তর ধাপে ধাপে গড়া হয়েছে।

প্রতিটি অংশ যোগ করার পর
যোগ হলো
খাতায় যা লিখলেন
জমা নম্বর
খরচ হওয়া সময়
  1. সংজ্ঞা — ২ নম্বর। তিনটি transition function পাশাপাশি; পার্থক্য শুধু δ-এর ধরনে।
  2. সমতা — আরও ১। “কোনটি বেশি শক্তিশালী” প্রশ্নের উত্তর: কোনোটিই নয়, নির্মাণের নামসহ।
  3. ছক — আরও ২। একই পাঁচ প্রশ্ন তিন যন্ত্রের জন্য। মোট ৫ নম্বর, দশ মিনিট।
  4. উদাহরণ — আরও ৩। একটি language, যেখানে আকারের পার্থক্য সূচকীয়, আর তা এড়ানো যায় না।
  5. ভুলের জায়গা — আরও ১। Complement-এর ফাঁদটি পরীক্ষকের প্রিয় পরের প্রশ্ন।
  6. কখন কোনটি — শেষ ১। কুড়ি মিনিটে দশ নম্বর।
বিষয়পর্বলিখিতভাইভা
Automaton, regex আর regular language০১–২৪অংশ ২ (ক-০১–ক-০৩)ভ-০১–ভ-০৪
Grammar, PDA আর parsing২৫–৪২অংশ ৩ (খ-০১–খ-০৪)ভ-০৫–ভ-০৮
Turing machine আর computability৪৩–৫৬অংশ ৪ (গ-০১–গ-০৪)ভ-০৯–ভ-১২
P, NP আর উন্নত complexity৫৭–৭০অংশ ৫ (ঘ-০১–ঘ-০৪)ভ-১৩–ভ-২০
কঠিন সমস্যা, নতুন দিগন্ত আর প্রয়োগ৭১–৮০অংশ ৬ (ঙ-০১–ঙ-০২)ভ-২১–ভ-২৪

এই পাতার কোনো প্রশ্ন কোনো নির্দিষ্ট পরীক্ষা, বিশ্ববিদ্যালয়, প্রতিষ্ঠান বা কোম্পানির ইন্টারভিউ থেকে নেওয়া নয়; এ ধরনের প্রশ্ন বিশ্ববিদ্যালয়ের Theory of Computation বা Automata কোর্সে, চাকরির লিখিত পরীক্ষায় আর ইন্টারভিউতে প্রায়ই আসে। দশটি ব্লক পাতাতেই চলে (ব্রাউজারের Python, শুধু standard library); প্রথমবার Python নামাতে কয়েক সেকেন্ড লাগে। এখানে প্রমাণগুলো “ধারণা” বা রূপরেখা স্তরের; পূর্ণ প্রমাণ আর marking rubric পর্ব ৮৪-তে। নকশার হাতে-কলমে অনুশীলন পর্ব ৮১ (Automaton আর grammar নকশার অনুশীলন)-এ, MCQ পর্ব ৮২ (MCQ প্রশ্নব্যাংক)-এ, আর regex, parsing ও complexity-র ইন্টারভিউ-প্রশ্ন পর্ব ৮৫-তে।

২ · অংশ ক — Finite automaton আর regular language (মডিউল ২–৪)

রিভিশন: পর্ব ০৭ (DFA), পর্ব ০৯ আর পর্ব ১০ (NFA ও subset construction), পর্ব ১১ (ε-NFA), পর্ব ১৭ (pumping lemma), পর্ব ১৮ (Myhill–Nerode), পর্ব ২১ (বাস্তব regex engine).

ক-০১DFA, NFA আর ε-NFA-র আনুষ্ঠানিক সংজ্ঞা দিয়ে তুলনা করুন। তিনটির ক্ষমতা কি সমান? সমান হলে “state-সংখ্যা”-য় পার্থক্য কতটা হতে পারে, একটি উদাহরণে দেখান। NFA-র complement নিতে কী সাবধানতা লাগে? — ১০ নম্বর (সহজ–মাঝারি)

সংজ্ঞা: DFA M = (Q, Σ, δ, q0, F), যেখানে δ: Q × Σ → Q একটি total function: প্রতিটি state আর চিহ্নে ঠিক একটি পরের state. NFA-তে δ: Q × Σ → P(Q), অর্থাৎ শূন্য, এক বা একাধিক পরের state; ε-NFA-তে δ: Q × Σε → P(Q), চিহ্ন না পড়েও state বদলানো যায়। NFA একটি string গ্রহণ করে, যদি কোনো একটি পথ F-এ শেষ হয়।

মাপকাঠিDFANFAε-NFA
একটি input-এ পথঠিক একটিঅনেক, কিছু মাঝপথে আটকায়অনেক, ε-move-সহ
আকারসবচেয়ে বড় হতে পারেঅনেক ছোট হতে পারেনির্মাণে সবচেয়ে সহজ
চালানোর খরচ (|w| = n)O(n)state-সেট ধরে O(n · |Q|2)তার সঙ্গে প্রতি ধাপে ε-closure
Complementaccept state উল্টালেই (DFA complete হলে)আগে DFA বানাতে হয়আগে DFA বানাতে হয়

সমতা: তিনটির ক্ষমতা সমান। ε-NFA থেকে ε-closure দিয়ে NFA (পর্ব ১১), আর NFA থেকে subset construction দিয়ে DFA (Rabin–Scott, ১৯৫৯): DFA-র প্রতিটি state হলো NFA-র state-এর একটি সেট, শুরু {q0}, আর ∅ হলো dead state.

উদাহরণ: Ln = {w ∈ {0, 1}∗ : শেষ থেকে n-তম চিহ্ন 1}। NFA “অনুমান করে” কোন 1-টি শেষ থেকে n-তম, তাই n + 1টি state যথেষ্ট; DFA-কে শেষ n চিহ্ন মনে রাখতে হয়। নিচের ব্লক reachable state গোনে আর n = 3-এর DFA দৈর্ঘ্য ১০ পর্যন্ত সংজ্ঞার সঙ্গে মেলায়।

from itertools import product

def nfa(n):                     # L_n: the n-th symbol from the end is 1
    d = {(0, "0"): {0}, (0, "1"): {0, 1}}
    for i in range(1, n):
        d[(i, "0")] = d[(i, "1")] = {i + 1}
    return d, {n}
def subset_dfa(n):              # only reachable subsets, start {0}
    d, F = nfa(n)
    start = frozenset({0}); seen = {start}; todo = [start]; delta = {}
    while todo:
        S = todo.pop()
        for a in "01":
            T = frozenset(q for s in S for q in d.get((s, a), ()))
            delta[(S, a)] = T
            if T not in seen:
                seen.add(T); todo.append(T)
    return start, delta, {S for S in seen if S & F}, len(seen)

for n in range(1, 9):
    print(f"n={n}: NFA states {n + 1:2}  DFA states {subset_dfa(n)[3]:3}")

start, delta, acc, _ = subset_dfa(3)
ok = True
for k in range(11):
    for w in map("".join, product("01", repeat=k)):
        S = start
        for a in w: S = delta[(S, a)]
        ok &= (S in acc) == (len(w) >= 3 and w[-3] == "1")
print("n=3 DFA == definition on all strings up to length 10:", ok)

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

n=1: NFA states  2  DFA states   2
n=2: NFA states  3  DFA states   4
n=3: NFA states  4  DFA states   8
n=4: NFA states  5  DFA states  16
n=5: NFA states  6  DFA states  32
n=6: NFA states  7  DFA states  64
n=7: NFA states  8  DFA states 128
n=8: NFA states  9  DFA states 256
n=3 DFA == definition on all strings up to length 10: True

NFA বাড়ে এক এক করে, DFA দ্বিগুণ হারে: n = 8-এ ৯ বনাম ২৫৬। এটি নির্মাণের দোষ নয়: শেষ n চিহ্নের যেকোনো দুটি ক্রম কোনো suffix দিয়ে আলাদা হয়, তাই Myhill–Nerode অনুযায়ী minimal DFA-তেও 2nটি state লাগে (পর্ব ১০, ১৮)।

সীমা: Nondeterminism মানে এলোমেলোভাবে বাছাই নয়; সব পথ একসঙ্গে দেখা। NFA-র accept আর non-accept state উল্টালে complement হয় না: যে string-এ একটি পথ গ্রহণ আর অন্যটি বর্জনে শেষ হয়, তা দুই যন্ত্রেই গৃহীত হবে। Partial DFA-তেও আগে dead state যোগ করতে হয় (পর্ব ০৮)।

পরীক্ষক যা খোঁজেন: তিন δ-এর ধরন (২); সমতা আর নির্মাণের নাম (১); ছক (২); Ln বা অনুরূপ উদাহরণ ও অনিবার্যতা (৩); complement-এর ফাঁদ (১); কখন কোনটি (১)। পর্ব ১০ · পর্ব ১১

যেখানে নম্বর কাটে: “NFA বেশি শক্তিশালী” লেখা; subset construction-এ ε-closure বা ∅ বাদ দেওয়া; “2n শুধু খারাপ নির্মাণের দোষ” বলা।

ক-০২Regular language-এর pumping lemma আর Myhill–Nerode theorem শর্তসহ লিখুন। কোনটি কী প্রমাণ করতে পারে আর কী পারে না, তুলনা করুন। {anbn : n ≥ 0} দুই পদ্ধতিতেই non-regular দেখান, আর এমন একটি non-regular language দিন যা pumping lemma-র শর্ত পূরণ করে। — ১০ নম্বর (মাঝারি–কঠিন)

Pumping lemma: L regular হলে এমন p ≥ 1 আছে যে L-এর প্রতিটি s, |s| ≥ p, কে s = xyz লেখা যায়, যেখানে |y| ≥ 1, |xy| ≤ p, আর প্রতিটি i ≥ 0-তে xyiz ∈ L. এটি আবশ্যিক শর্ত মাত্র। ব্যবহারে প্রতিপক্ষ p আর ভাগ (x, y, z) বাছেন; আপনি s আর i.

Myhill–Nerode (Myhill ১৯৫৭, Nerode ১৯৫৮): x ≡L y যদি প্রতিটি z-এ xz ∈ L ⇔ yz ∈ L. L regular ⇔ ≡L-এর equivalence class সসীম সংখ্যক; আর class-এর সংখ্যা ঠিক minimal DFA-র state-সংখ্যা।

মাপকাঠিPumping lemmaMyhill–Nerode
যুক্তির ধরনআবশ্যিক শর্ত (একমুখী)যদি-এবং-কেবল-যদি
Regular প্রমাণ করতে পারে?নাহ্যাঁ (class সসীম দেখালে)
Non-regular প্রমাণের কৌশলপ্রতিপক্ষের খেলা: প্রতিটি ভাগে একটি iঅসীম সংখ্যক জোড়ায় জোড়ায় আলাদা string
বাড়তি ফলনেইMinimal DFA-র আকার আর গঠন

anbn, দুই পথে: (১) s = apbp; |xy| ≤ p বলে y শুধু a, তাই i = 0-তে a কমে, b একই থাকে: s ∉ L. (২) ai আর aj (i ≠ j) suffix bi দিয়ে আলাদা: aibi ∈ L কিন্তু ajbi ∉ L. অসীম সংখ্যক class, তাই non-regular. নিচের ব্লক দুটিই যাচাই করে, সঙ্গে একটি “pump হয় কিন্তু regular নয়” language.

import re
from itertools import product

def anbn(w):
    m = re.fullmatch(r"(a*)(b*)", w)
    return bool(m) and len(m[1]) == len(m[2])

def splits(s, p):               # every x, y, z with |xy| <= p, |y| >= 1
    return [(s[:i], s[i:j], s[j:]) for j in range(1, p + 1) for i in range(j)]

p = 4; s = "a" * p + "b" * p
surv = [all(anbn(x + y * i + z) for i in range(4)) for x, y, z in splits(s, p)]
print(f"a^n b^n, p={p}: {len(surv)} splits, splits that survive pumping: {sum(surv)}")

pref = ["a" * i for i in range(6)]          # Myhill-Nerode: a^i vs a^j
dist = [(u, v) for u in pref for v in pref if u < v
        and anbn(u + "b" * len(u)) != anbn(v + "b" * len(u))]
print("pairs a^i, a^j (i<j<6) separated by suffix b^i:", len(dist), "of 15")

def L2(w):                      # a^i b^j c^k with i = 0 or j = k
    m = re.fullmatch(r"(a*)(b*)(c*)", w)
    return bool(m) and (len(m[1]) == 0 or len(m[2]) == len(m[3]))

bad = [w for k in range(1, 9) for w in map("".join, product("abc", repeat=k))
       if L2(w) and not all(L2(w[0] * i + w[1:]) for i in range(5))]
print("L2 with p=1, y = first symbol: strings that fail to pump:", len(bad))
hit = [(j, k) for j in range(9) for k in range(9) if L2("a" + "b" * j + "c" * k)]
print("L2 meets a b^j c^k (j, k < 9) only when j == k:", all(j == k for j, k in hit))

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

a^n b^n, p=4: 10 splits, splits that survive pumping: 0
pairs a^i, a^j (i<j<6) separated by suffix b^i: 15 of 15
L2 with p=1, y = first symbol: strings that fail to pump: 0
L2 meets a b^j c^k (j, k < 9) only when j == k: True

p = 4-এ বৈধ ভাগ দশটি, আর একটিও pumping-এ টেকে না। a0 থেকে a5-এর ১৫টি জোড়াই আলাদা। কিন্তু L2 = {aibjck : i = 0 বা j = k}-এ p = 1 নিয়ে y = প্রথম চিহ্ন বাছলে প্রতিটি string pump হয়: a-কে বাদ দিলে i = 0 হয়ে ভাষাতেই থাকে। তবু L2 ∩ ab∗c∗ = {abncn}, যা non-regular; regular language intersection-এ বদ্ধ বলে L2-ও non-regular (পর্ব ১৬)।

কখন কোনটি: সরল “গুনে মেলানো” language-এ pumping দ্রুত; pumping আটকে গেলে Myhill–Nerode বা closure. Minimal DFA-র আকার জানতে কেবল Myhill–Nerode.

পরীক্ষক যা খোঁজেন: দুই বক্তব্য সব quantifier-সহ (৩); ছক (২); anbn দুই পথে (৩); pump-হওয়া non-regular উদাহরণ (২)। পর্ব ১৭ · পর্ব ১৮

যেখানে নম্বর কাটে: “pumping lemma মানলে regular” লেখা; ভাগ নিজে বাছা; |xy| ≤ p শর্ত বাদ দেওয়া।

ক-০৩Formal regular expression আর বাস্তব regex engine-এর regex কি একই জিনিস? Backreference কেন regular-এর বাইরে যায়, আর backtracking engine কেন কিছু pattern-এ সূচকীয় সময় নেয়? — ৫ নম্বর (মাঝারি)

সংজ্ঞা: Formal regular expression গড়া হয় ∅, ε, একক চিহ্ন, ∪, concatenation আর ∗ দিয়ে, আর তা ঠিক regular language বর্ণনা করে (Kleene, ১৯৫৬)। বাস্তব engine-এ বাড়তি আছে: backreference, lookaround, anchor.

Backreference: (a*)b\1 মেলে ঠিক {anban}-এর সঙ্গে, যা pumping-এ non-regular. তাই “practical regex” আর regular language এক শ্রেণি নয়।

দুই engine: Backtracking engine (Python re, JavaScript RegExp) একটি করে বিকল্প চেষ্টা করে, ব্যর্থ হলে পেছায়; (a+)+$-এ “aaa…ab” ভাগের সব উপায় ঘোরে, সময় সূচকীয়: ReDoS. Automaton-ভিত্তিক engine (Thompson-এর ধারার NFA simulation বা lazy DFA) state-সেট ধরে এগোয়, সময় linear, কিন্তু backreference নেই।

পরীক্ষক যা খোঁজেন: formal সংজ্ঞা (১); একটি non-regular backreference উদাহরণ (২); দুই engine আর সময়ের পার্থক্য (২)। পর্ব ১৩ · পর্ব ২১

যেখানে নম্বর কাটে: “সব regex DFA-তে বদলানো যায়” লেখা; ReDoS-কে engine-এর bug বলা (এটি backtracking-এর স্বভাব)।

৩ · অংশ খ — Grammar, pushdown automaton আর parsing (মডিউল ৫–৭)

রিভিশন: পর্ব ২৯ (CNF), পর্ব ৩০ (GNF), পর্ব ৩৩ (PDA-র গ্রহণ), পর্ব ৩৫ (DPDA), পর্ব ৩৭ (closure ও decision), পর্ব ৩৮ আর পর্ব ৩৯ (LL ও LR).

খ-০১Chomsky normal form আর Greibach normal form-এর সংজ্ঞা দিয়ে তুলনা করুন: নিয়মের আকার, দৈর্ঘ্য n-এর string-এর derivation-এর ধাপ, কোন algorithm বা প্রমাণে কোনটি কাজে লাগে, আর রূপান্তরের খরচ। {anbn : n ≥ 1}-এর দুই রূপের grammar দিন। — ১০ নম্বর (মাঝারি)

সংজ্ঞা: CNF-এ প্রতিটি নিয়ম A → BC বা A → a (B, C শুরুর variable নয়), সঙ্গে ε ∈ L হলে শুধু S0 → ε। GNF-এ প্রতিটি নিয়ম A → aα, যেখানে a terminal আর α ∈ V∗; ε থাকলে L − {ε} নিয়ে কাজ (Greibach, ১৯৬৫)।

মাপকাঠিCNFGNF
দৈর্ঘ্য n ≥ 1-এর derivationঠিক 2n − 1 ধাপঠিক n ধাপ
Parse treeপ্রায় full binary treeপ্রতিটি ধাপে একটি করে terminal বাঁ থেকে
কাজে লাগেCYK (O(n3 · |G|)), CFL-এর pumping lemma-র প্রমাণপ্রতি move-এ একটি চিহ্ন পড়া PDA, left recursion-হীন top-down
রূপান্তরSTART, DEL, UNIT, TERM, BIN; আগে DEL করলে আকার সূচকীয় হতে পারে, আগে BIN করলে polynomial থাকেআগে left recursion দূর করতে হয়; grammar অনেক বড় হতে পারে

উদাহরণ: CNF: S → AX ∣ AB, X → SB, A → a, B → b. GNF: S → aSB ∣ aB, B → b. নিচের ব্লক দৈর্ঘ্য ১০ পর্যন্ত দুটির language মেলায় আর derivation-এর ধাপ গোনে।

CNF = {"S": ["AX", "AB"], "X": ["SB"], "A": ["a"], "B": ["b"]}
GNF = {"S": ["aSB", "aB"], "B": ["b"]}

def words(G, maxlen):           # leftmost derivations; {word: steps}
    found, frontier = {}, [("S", 0)]
    while frontier:
        nxt = []
        for form, k in frontier:
            i = next((j for j, c in enumerate(form) if c.isupper()), None)
            if i is None:
                found[form] = k; continue
            for rhs in G[form[i]]:
                new = form[:i] + rhs + form[i + 1:]
                if len(new) <= maxlen:          # no rule shrinks a form
                    nxt.append((new, k + 1))
        frontier = nxt
    return found

c, g = words(CNF, 10), words(GNF, 10)
want = {"a" * n + "b" * n for n in range(1, 6)}
print("CNF language == a^n b^n (n>=1, len<=10):", set(c) == want)
print("GNF language == a^n b^n (n>=1, len<=10):", set(g) == want)
for w in sorted(want, key=len):
    print(f"|w|={len(w):2}  CNF steps {c[w]:2} (2|w|-1 = {2*len(w)-1:2})"
          f"  GNF steps {g[w]:2}")

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

CNF language == a^n b^n (n>=1, len<=10): True
GNF language == a^n b^n (n>=1, len<=10): True
|w|= 2  CNF steps  3 (2|w|-1 =  3)  GNF steps  2
|w|= 4  CNF steps  7 (2|w|-1 =  7)  GNF steps  4
|w|= 6  CNF steps 11 (2|w|-1 = 11)  GNF steps  6
|w|= 8  CNF steps 15 (2|w|-1 = 15)  GNF steps  8
|w|=10  CNF steps 19 (2|w|-1 = 19)  GNF steps 10

Language একই, ধাপ আলাদা: |w| = 10-এ CNF ১৯, GNF ১০। CNF-এ n − 1টি A → BC ধাপ গাছ ভাগ করে আর n টি A → a ধাপ পাতা বসায়; GNF-এর প্রতিটি ধাপ ঠিক একটি terminal লেখে।

সীমা: একটি language-এর অনেক CNF grammar হয়; “অনন্য” বলা ভুল। GNF-এ নিয়ম বহুগুণ বাড়তে পারে (পর্ব ৩০-এর একটি উদাহরণে ৪টি থেকে ১৩টি)।

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা ε-সহ (২); ছক (৩); দুই grammar (২); ধাপের হিসাব ও কারণ (২); প্রয়োগ (১)। পর্ব ২৯ · পর্ব ৩০ · পর্ব ৩১

যেখানে নম্বর কাটে: CNF-এ A → aB লেখা; DEL-এর আগে UNIT করে নতুন unit নিয়ম রেখে দেওয়া; GNF-এ left recursion থেকে যাওয়া।

খ-০২PDA-র দুই গ্রহণ-রীতি (final state আর empty stack) তুলনা করুন। Nondeterministic আর deterministic PDA-তে এই দুই রীতির ক্ষমতা কী? DPDA কেন NPDA-র চেয়ে দুর্বল, একটি language দিয়ে দেখান; অথচ DFA আর NFA সমান কেন? — ১০ নম্বর (মাঝারি–কঠিন)

সংজ্ঞা: PDA P = (Q, Σ, Γ, δ, q0, F), δ: Q × Σε × Γε → P(Q × Γε)। Final state-এ গ্রহণ: L(P) = যেসব w পড়া শেষে কোনো পথ F-এ থাকে। Empty stack-এ গ্রহণ: N(P) = যেসব w পড়া শেষে কোনো পথে stack ফাঁকা।

যন্ত্রFinal stateEmpty stackউদাহরণ
NPDAঠিক CFLঠিক CFL (দুই দিকে রূপান্তর)wwR, BAL, anbn
DPDAঠিক DCFLশুধু prefix-free DCFLwcwR, anbn

কেন DPDA দুর্বল: wwR CFL, কিন্তু DCFL নয়: মাঝখান অনুমান ছাড়া চেনা যায় না; মাঝে c দিলে (wcwR) DPDA যথেষ্ট। আরেক যুক্তি: DCFL complement-এ বদ্ধ, CFL নয়।

DFA = NFA কেন: সব সম্ভাব্য state-এর সেট একটি সসীম তথ্য, যা একটি DFA state-এ ধরে। PDA-তে প্রতিটি পথের নিজস্ব stack, আর সব stack-এর সেট সসীম নয়; subset construction খাটে না। Turing machine-এ আবার DTM = NTM ক্ষমতায় (পর্ব ৪৬)।

সীমা: Empty-stack DPDA-র সমস্যা মেটে শেষে endmarker $ জুড়লে। DCFL ⇔ LR(k) grammar আছে (Knuth, ১৯৬৫)।

পরীক্ষক যা খোঁজেন: দুই রীতির সংজ্ঞা (২); ছক (৩); wwR বনাম wcwR (২); DFA = NFA কিন্তু DPDA ≠ NPDA-র কারণ (২); endmarker বা LR-এর যোগ (১)। পর্ব ৩৩ · পর্ব ৩৫

যেখানে নম্বর কাটে: “DPDA-তে দুই রীতি সমান” লেখা; “subset construction PDA-তেও চলে” বলা।

খ-০৩LL(1) আর LR parsing-এর তুলনা করুন: derivation-এর দিক, সিদ্ধান্তের সময়, কোন grammar নেয়, conflict, আর বাস্তবে কোনটি কখন। একটি left-recursive expression grammar-এ LL(1) কেন ব্যর্থ, FIRST/FOLLOW দিয়ে দেখান। — ১০ নম্বর (মাঝারি)
মাপকাঠিLL(1)LR (SLR, LALR, LR(1))
দিকTop-down, leftmost derivationBottom-up, rightmost derivation উল্টো ক্রমে
নিয়ম বাছাইনিয়মের শুরুতেই, এক token দেখেপুরো ডান দিক পড়ার পর (handle), এক token দেখে
যন্ত্রFIRST/FOLLOW থেকে table, বা recursive descentItem-এর DFA আর stack
Grammar-এর শর্তleft recursion ও একই শুরুর বিকল্প চলে নাleft recursion চলে; LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1)
Conflicttable-এর একই ঘরে দুই নিয়মshift/reduce, reduce/reduce
বাস্তবেহাতে লেখা parser, ভালো error বার্তাparser generator

সম্পর্ক: প্রতিটি LL(1) grammar LR(1), উল্টোটি নয়; language-এ LL(k) ⊊ DCFL = LR(1) grammar-এর language. LR বেশি নেয় কারণ সিদ্ধান্ত দেরিতে, পুরো ডান দিক দেখে।

উদাহরণ: E → E + T ∣ T-এ দুই বিকল্পের FIRST একই ({(, id}), তাই M[E, id]-তে দুই নিয়ম। Left recursion সরিয়ে E → T E′, E′ → + T E′ ∣ ε (T-এর জন্যও একইভাবে) লিখলে conflict থাকে না। নিচের ব্লক FIRST, FOLLOW আর table-এর conflict নিজে হিসাব করে।

def ll1(G, S):                   # G: {A: [rhs tuples]}, () is ε
    FI = {A: set() for A in G}; FO = {A: set() for A in G}; FO[S].add("$")
    def first(seq):
        out = set()
        for X in seq:
            f = FI[X] if X in G else {X}
            out |= f - {"ε"}
            if "ε" not in f: return out
        return out | {"ε"}
    def predict(A, r):
        f = first(r)
        return (f - {"ε"}) | (FO[A] if "ε" in f else set())
    for _ in range(len(G) * 4):            # iterate to a fixed point
        for A, rhss in G.items():
            for r in rhss:
                FI[A] |= first(r)
                for i, X in enumerate(r):
                    if X in G: FO[X] |= predict(A, r[i + 1:]) - {"ε"}
    seen, clash = set(), set()
    for A, rhss in G.items():
        for r in rhss:
            for a in predict(A, r):
                if (A, a) in seen: clash.add((A, a))
                seen.add((A, a))
    return FI, FO, sorted(clash)
E1 = {"E": [("E", "+", "T"), ("T",)], "T": [("T", "*", "F"), ("F",)], "F": [("(", "E", ")"), ("id",)]}
E2 = {"E": [("T", "E'")], "E'": [("+", "T", "E'"), ()], "T": [("F", "T'")], "T'": [("*", "F", "T'"), ()], "F": [("(", "E", ")"), ("id",)]}
print("left-recursive E1, LL(1) conflicts:", ll1(E1, "E")[2])
FI, FO, clash = ll1(E2, "E"); print("E2 conflicts:", clash)
for A in E2: print(f"{A:2}  FIRST {sorted(FI[A])}  FOLLOW {sorted(FO[A])}")

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

left-recursive E1, LL(1) conflicts: [('E', '('), ('E', 'id'), ('T', '('), ('T', 'id')]
E2 conflicts: []
E   FIRST ['(', 'id']  FOLLOW ['$', ')']
E'  FIRST ['+', 'ε']  FOLLOW ['$', ')']
T   FIRST ['(', 'id']  FOLLOW ['$', ')', '+']
T'  FIRST ['*', 'ε']  FOLLOW ['$', ')', '+']
F   FIRST ['(', 'id']  FOLLOW ['$', ')', '*', '+']

Left-recursive grammar-এ E আর T-এর ঘরে ( আর id-তে দুটি করে নিয়ম; রূপান্তরের পর conflict শূন্য। FOLLOW(E′) = {$, )} বলেই E′ → ε নেওয়া হয় ) বা $ দেখলে।

পরীক্ষক যা খোঁজেন: ছক (৪); grammar-শ্রেণির সম্পর্ক (২); FIRST/FOLLOW-সহ উদাহরণ (৩); কখন কোনটি (১)। পর্ব ৩৮ · পর্ব ৩৯ · পর্ব ৪০

যেখানে নম্বর কাটে: FOLLOW(S)-এ $ ভোলা; ε-নিয়মের ঘর FIRST দিয়ে ভরা; “LR(1) language LL(1)-এর চেয়ে বেশি, তাই প্রতিটি CFL LR-এ চলে” লেখা (wwR DCFL নয়)।

খ-০৪Regular আর context-free language-এর closure আর decision property একটি ছকে তুলনা করুন। CFL intersection-এ কেন বদ্ধ নয়, উদাহরণসহ দেখান। — ৫ নম্বর (সহজ–মাঝারি)
ধর্মRegularCFL
∪, concatenation, ∗বদ্ধবদ্ধ
∩, complementবদ্ধবদ্ধ নয়
Regular language-এর সঙ্গে ∩বদ্ধবদ্ধ (PDA × DFA)
Membership, emptiness, finitenessdecidabledecidable (CYK, generating symbol)
Equivalence, universalitydecidableundecidable

উদাহরণ: {anbncm} আর {ambncn} দুটিই CFL, কিন্তু intersection {anbncn}, যা CFL-এর pumping lemma-য় CFL নয় (পর্ব ৩৬)। De Morgan থেকে: complement-এ বদ্ধ হলে ∪ দিয়ে ∩-ও আসত, তাই complement-এও নয়।

পরীক্ষক যা খোঁজেন: ছক (৩); উদাহরণ ও complement-এর যুক্তি (২)। পর্ব ১৬ · পর্ব ৩৭

যেখানে নম্বর কাটে: “regular-এর subset regular” বা “CFL-এর subset CFL” লেখা (anbn ⊆ a∗b∗)।

৪ · অংশ গ — Turing machine আর computability (মডিউল ৮–৯)

রিভিশন: পর্ব ৪৫ (রূপভেদ), পর্ব ৪৬ (NTM), পর্ব ৪৭ (Church–Turing thesis), পর্ব ৫০ (decidable ও recognizable), পর্ব ৫১ (halting), পর্ব ৫২ (reduction), পর্ব ৫৩ (Rice).

গ-০১Turing machine-এর রূপভেদ (multi-tape, nondeterministic, দুই দিকে অসীম tape, enumerator) কেন একই শ্রেণির language চেনে? Simulation-এর খরচ কত? এই robustness থেকে Church–Turing thesis-এ কীভাবে পৌঁছাই, আর thesis-টি theorem নয় কেন? — ১০ নম্বর (মাঝারি)

সংজ্ঞা: মূল মডেল TM M = (Q, Σ, Γ, δ, q0, qaccept, qreject), এক দিকে অসীম এক tape. প্রতিটি রূপভেদের প্রতিটি ধাপ মূল যন্ত্রে কয়েক ধাপে নকল করা যায়।

রূপভেদনকলের কৌশলখরচ
Multi-tape (k tape)এক tape-এ k অংশ, # দিয়ে আলাদা, head-এর ঘর দাগানোt(n) ধাপ → O(t(n)2), t(n) ≥ n
Nondeterministiccomputation tree-তে BFS (DFS নয়)2O(t(n))
দুই দিকে অসীম tapetape ভাঁজ করে দুই trackধ্রুবক গুণ
Enumeratorসব string আর ধাপ dovetail করেrecognizable ⇔ enumerable

উদাহরণ: পর্ব ৪৫-এ {w#w}-এ মাপা: 2-tape-এ 3m + 4 ধাপ, এক tape-এ 2(m + 1)2.

Church–Turing thesis: “কার্যকর পদ্ধতিতে গণনাযোগ্য” = “Turing machine-এ গণনাযোগ্য”। বাঁ পাশ অনানুষ্ঠানিক ধারণা, তাই গাণিতিক প্রমাণ সম্ভব নয়; পক্ষে সাক্ষ্য হলো ভিন্ন মডেলের (lambda calculus, μ-recursive function, register machine) সমতুল্যতা। Extended thesis (polynomial বাড়তি সময়ে নকল) আলাদা দাবি; quantum computer factoring-এ এটিকে চ্যালেঞ্জ করতে পারে বলে মনে করা হয়, মূল thesis-কে নয়।

পরীক্ষক যা খোঁজেন: মূল মডেল (১); ছক ও খরচ (৪); robustness-এর অর্থ (১); thesis-এর বক্তব্য, কেন প্রমাণ নয়, পক্ষে প্রমাণ (৩); extended রূপ (১)। পর্ব ৪৫ · পর্ব ৪৬ · পর্ব ৪৭

যেখানে নম্বর কাটে: NTM-কে DFS-এ নকল করা (অসীম শাখায় আটকায়); thesis-কে প্রমাণিত theorem বলা; “quantum computer halting সমাধান করে” লেখা।

গ-০২Decidable, Turing-recognizable আর co-recognizable language-এর সংজ্ঞা দিন। L decidable ⇔ L আর L̄ দুটিই recognizable — প্রমাণের ধারণা দিন। প্রতিটি শ্রেণির একটি উদাহরণ আর এমন একটি language দিন যা কোনোটিতেই নেই। — ১০ নম্বর (মাঝারি–কঠিন)

সংজ্ঞা: L recognizable, যদি এমন TM M থাকে যে w ∈ L হলে গ্রহণ করে, আর w ∉ L হলে বর্জন করে বা চিরকাল চলে। L decidable, যদি এমন M (decider) থাকে যা প্রতিটি input-এ থামে আর ঠিক L গ্রহণ করে। L co-recognizable, যদি L̄ recognizable.

প্রমাণের রূপরেখা: (⇒) decider-এর accept/reject উল্টালে L̄-এর decider. (⇐) M1 L-কে, M2 L̄-কে চেনে; নতুন যন্ত্র দুটিকে পালাক্রমে এক এক ধাপ চালায়। প্রতিটি w L বা L̄-এ, তাই একটি গ্রহণ করে থামবেই; M1 গ্রহণ করলে গ্রহণ, M2 করলে বর্জন। একটিকে আগে পুরো চালানো চলে না, সেটি চিরকাল চলতে পারে। ∎

ছবি ৮৩.১ — recognizable আর co-recognizable-এর মিলনস্থলেই decidable

বাঁ বৃত্ত recognizable, ডান বৃত্ত co-recognizable; মাঝের অংশ decidable; বাইরে দুটির কোনোটিই নয়

Recognizable and co-recognizable languages overlap exactly in the decidable languages সব language যেমন EQTM recognizable ATM HALTTM co-recognizable ĀTM ETM decidable ADFA ACFG aⁿbⁿcⁿ

উদাহরণ: ATM recognizable (universal TM দিয়ে চালাই) কিন্তু decidable নয় (diagonalization, Turing ১৯৩৬); তাই ĀTM recognizable নয়। “L(M) অশূন্য” সব input-এ dovetailing করে recognizable, তাই ETM co-recognizable. EQTM কোনোটিই নয় (পর্ব ৫২)। নিচের ব্লকে recognizer: থামলে নিশ্চিত “হ্যাঁ”, না থামলে কখনোই “না” বলার অধিকার নেই।

# toy "programs": each step yields; returning means the program halted
def countdown(n):
    while n > 0:
        n -= 1; yield
def collatz(n):
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1; yield
def spin(n):
    while True: yield

def halts_within(prog, x, budget):
    run = prog(x)
    for step in range(budget + 1):
        try: next(run)
        except StopIteration: return step
    return None                         # no answer yet, NOT "never halts"

def recognize_halt(prog, x, max_round=12):  # budgets 1, 2, 4, ... 2^12
    for r in range(max_round + 1):
        s = halts_within(prog, x, 2 ** r)
        if s is not None: return f"accept: halted after {s} steps"
    return f"still running after {2 ** max_round} steps: no verdict"

for prog, x in [(countdown, 5), (collatz, 27), (spin, 0), (collatz, 97)]:
    print(f"{prog.__name__}({x}):", recognize_halt(prog, x))

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

countdown(5): accept: halted after 5 steps
collatz(27): accept: halted after 111 steps
spin(0): still running after 4096 steps: no verdict
collatz(97): accept: halted after 118 steps

collatz(27) ১১১ ধাপে থামে, তাই গ্রহণ। spin কখনো থামে না; ৪০৯৬ ধাপ পরেও recognizer শুধু বলতে পারে “এখনো চলছে”। পাতার ব্লকে সীমা রাখা হয়েছে ব্রাউজারের জন্য; সত্যিকারের recognizer চিরকাল চলত। “৪০৯৬ ধাপে থামেনি, তাই থামবে না” বললে তা decider নয়, ভুল উত্তর।

পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (২); উপপাদ্য আর পালাক্রমে চালানোর যুক্তি (৪); চার শ্রেণির উদাহরণ (৩); কেন একটিকে আগে পুরো চালানো যায় না (১)। পর্ব ৫০ · পর্ব ৫১

যেখানে নম্বর কাটে: recognizer-কে “কখনো ভুল বলে” লেখা (সে শুধু চুপ থাকতে পারে); “recognizable complement-এ বদ্ধ” লেখা।

গ-০৩Mapping reduction (A ≤m B) আর Turing reduction (A ≤T B)-এর সংজ্ঞা দিয়ে তুলনা করুন। Reduction-এর দিকের নিয়ম লিখুন। এমন একটি জোড়া দিন, যেখানে Turing reduction আছে কিন্তু mapping reduction নেই। — ১০ নম্বর (কঠিন)

সংজ্ঞা: A ≤m B, যদি computable f থাকে যাতে প্রতিটি w-এ w ∈ A ⇔ f(w) ∈ B. A ≤T B, যদি B-এর oracle-সহ একটি যন্ত্র A decide করে, যতবার খুশি প্রশ্ন করে।

দিকের নিয়ম
A ≤m B: B decidable ⇒ A decidable; A undecidable ⇒ B undecidable

কঠিনতা বাঁ থেকে ডানে যায়। জানা কঠিন সমস্যাকে বাঁয়ে বসান, নতুন সমস্যাকে ডানে।

মাপকাঠিMapping (≤m)Turing (≤T)
B-কে কয়টি প্রশ্নএকটি, শেষে, উত্তর হুবহুযতগুলো খুশি, উত্তর উল্টানোও চলে
Decidability রক্ষা করেহ্যাঁহ্যাঁ
Recognizability রক্ষা করেহ্যাঁ (B recognizable ⇒ A recognizable)না
সম্পর্ক≤m হলে ≤Tউল্টোটি সবসময় নয়
Complexity-তে রূপ≤p (Karp)polynomial-time oracle (Cook)

উদাহরণ: ĀTM ≤T ATM: oracle-কে জিজ্ঞেস করে উত্তর উল্টে দিন। কিন্তু ĀTM ≤m ATM হতে পারে না: হলে ATM recognizable বলে ĀTM-ও recognizable হতো, যা মিথ্যা। আর ATM ≤m HALTTM: ⟨M, w⟩ থেকে M′ বানান, যা M-কে w-এ চালায়, গ্রহণ করলে থামে, বর্জন করলে ইচ্ছে করে loop করে; f(⟨M, w⟩) = ⟨M′, w⟩। f শুধু বর্ণনা লেখে, M চালায় না, তাই computable.

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); দিকের নিয়ম (২); ছক (৩); ĀTM-এর উদাহরণ ও যুক্তি (২); একটি সঠিক mapping reduction (১)। পর্ব ৫২ · পর্ব ৫৯

যেখানে নম্বর কাটে: নতুন সমস্যাকে বাঁয়ে বসানো (B ≤m ATM দিয়ে B-র কঠিনতা “প্রমাণ”); f-এর ভেতরে M চালানো, যাতে f নিজেই না থামতে পারে।

গ-০৪Rice-এর উপপাদ্য শর্তসহ লিখুন। কোন প্রশ্নে এটি খাটে আর কোনটিতে খাটে না, তিনটি করে উদাহরণ দিন। “Undecidable” মানেই কি “recognizable নয়”? — ৫ নম্বর (মাঝারি)

বক্তব্য (Rice, ১৯৫৩): P যদি recognizable language-এর একটি অতুচ্ছ ধর্ম হয় (কিছু TM-এর language-এ আছে, কিছুর নেই), তবে {⟨M⟩ : L(M) ∈ P} undecidable. দুই শর্ত: ধর্মটি semantic (একই language-এর দুই যন্ত্রে একই উত্তর), আর অতুচ্ছ।

খাটে (undecidable)খাটে না
L(M) = ∅?M-এ ৫টির বেশি state আছে? (syntactic, decidable)
L(M) regular?M ফাঁকা input-এ ১০০ ধাপের মধ্যে থামে? (১০০ ধাপ চালালেই হয়, decidable)
L(M) = Σ∗?DFA D-র L(D) = ∅? (যন্ত্রটি TM নয়, decidable)

Undecidable ≠ unrecognizable: {⟨M⟩ : L(M) ≠ ∅} undecidable, কিন্তু recognizable (dovetailing).

পরীক্ষক যা খোঁজেন: দুই শর্তসহ বক্তব্য (২); ছক (২); recognizability-র পার্থক্য (১)। পর্ব ৫৩

যেখানে নম্বর কাটে: state গোনার মতো syntactic প্রশ্নে Rice খাটানো; DFA বা CFG-এর প্রশ্নে Rice খাটানো।

৫ · অংশ ঘ — P, NP, coNP, PSPACE আর randomness (মডিউল ১০–১২)

রিভিশন: পর্ব ৫৭ (P), পর্ব ৫৮ (NP), পর্ব ৫৯ (≤p), পর্ব ৬২ (coNP ও NP-hard), পর্ব ৬৪ (Savitch), পর্ব ৬৬ (L ও NL), পর্ব ৬৯ (BPP), পর্ব ৭৫ (BQP).

ঘ-০১P, NP, coNP আর PSPACE-এর সংজ্ঞা দিন। এদের মধ্যে কোন অন্তর্ভুক্তি প্রমাণিত, কোনটি কড়া বলে প্রমাণিত, আর কোনটি খোলা? প্রতিটি শ্রেণির একটি complete সমস্যা দিন। P = NP হলে coNP সম্পর্কে কী বলা যায়? — ১০ নম্বর (মাঝারি)

সংজ্ঞা: P = ⋃k TIME(nk). NP: এমন polynomial-time verifier V আর polynomial p আছে যে w ∈ L ⇔ কোনো c, |c| ≤ p(|w|), যাতে V(w, c) গ্রহণ করে; সমতুল্যভাবে ⋃k NTIME(nk). coNP = {L : L̄ ∈ NP}, অর্থাৎ “না” উত্তরের ছোট সাক্ষ্য। PSPACE = ⋃k SPACE(nk).

ছবি ৮৩.২ — L থেকে EXP: কোন ধাপ প্রমাণিত, কোনটি অজানা

প্রতিটি তীর নিচের শ্রেণি ⊆ ওপরের শ্রেণি; “?” মানে সমান কি না জানা নেই

Inclusions from L to EXP with open questions marked EXP PSPACE = NPSPACE NP coNP P NL = coNL L ? ? ? ? ? ? ? P ⊊ EXP NL ⊊ PSPACE সবুজ: প্রমাণিত কড়া · লাল ?: অজানা

প্রমাণিত: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXP; P ⊆ NP ∩ coNP; NP ∪ coNP ⊆ PSPACE. কড়া শুধু hierarchy theorem থেকে: P ⊊ EXP আর NL ⊊ PSPACE; তাই P থেকে EXP-এর অন্তত একটি ধাপ কড়া, কোনটি তা অজানা। খোলা: P বনাম NP, NP বনাম coNP, P বনাম PSPACE, L বনাম NL. P ≠ NP বলে বেশিরভাগ গবেষক মনে করেন, কিন্তু প্রমাণিত নয়।

শ্রেণি“হ্যাঁ”-এর ছোট সাক্ষ্যComplete সমস্যা
Pসাক্ষ্য লাগে নাlog-space reduction-এ CIRCUIT-VALUE
NPআছে (satisfying assignment)SAT, 3SAT, CLIQUE
coNP“না”-এর ছোট সাক্ষ্য আছেUNSAT, TAUTOLOGY
PSPACEবিকল্প quantifier-এর খেলাTQBF, generalized geography

P = NP হলে: P complement-এ বদ্ধ (decider-এর উত্তর উল্টালেই), তাই coNP = co-P = P = NP. সমতুল্যভাবে, NP ≠ coNP প্রমাণ হলে P ≠ NP-ও প্রমাণ হতো।

পরীক্ষক যা খোঁজেন: চার সংজ্ঞা (৩); প্রমাণিত শৃঙ্খল আর দুই কড়া ফল (৩); খোলা প্রশ্ন সৎভাবে (২); complete সমস্যা আর P = NP ⇒ NP = coNP (২)। পর্ব ৫৮ · পর্ব ৬২ · পর্ব ৬৭

যেখানে নম্বর কাটে: “NP মানে non-polynomial” লেখা; coNP-কে “NP-র complement শ্রেণি, অর্থাৎ NP-তে নেই এমন সব” লেখা; “P ⊊ NP প্রমাণিত” লেখা।

ঘ-০২NP-hard আর NP-complete-এর সংজ্ঞা দিন। এমন একটি সমস্যা দিন যা NP-hard কিন্তু NP-complete নয়, আর কারণ লিখুন। নতুন একটি সমস্যা NP-complete প্রমাণের দুই ধাপ কী? Search আর decision রূপের সম্পর্কও লিখুন। — ১০ নম্বর (মাঝারি)

সংজ্ঞা: B NP-hard, যদি প্রতিটি A ∈ NP-এর জন্য A ≤p B. B NP-complete, যদি B NP-hard আর B ∈ NP. NP-hard সমস্যা NP-এর বাইরেও থাকতে পারে।

মাপকাঠিNP-completeNP-hard
NP-তে আছে?হ্যাঁ, সংজ্ঞাতেইদরকার নেই
উদাহরণSAT, VERTEX-COVER, HAMPATH, SUBSET-SUMHALTTM, TQBF, TSP-এর optimisation রূপ

NP-hard কিন্তু NP-complete নয়: HALTTM. SAT ≤p HALTTM: φ থেকে একটি যন্ত্রের বর্ণনা বানাই, যা সব assignment চেষ্টা করে, কোনোটি মিললে থামে, নইলে loop করে। কিন্তু HALTTM undecidable, তাই NP-তে নেই।

প্রমাণের দুই ধাপ: (১) B ∈ NP: একটি সাক্ষ্য আর polynomial-time verifier; (২) জানা NP-complete A থেকে A ≤p B, যেখানে f polynomial সময়ে চলে আর দুই দিকেই “হ্যাঁ ⇔ হ্যাঁ”। নিচের ব্লক সবচেয়ে ছোট উদাহরণটি যাচাই করে: INDEPENDENT-SET ≤p VERTEX-COVER, f(G, k) = (G, n − k), কারণ S independent set ⇔ V − S vertex cover.

from itertools import combinations

# delivery-conflict graph: an edge = two orders that cannot share a slot
V = range(8)
E = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6), (5, 7), (6, 7), (1, 6)]

def independent(S): return all(not (u in S and v in S) for u, v in E)
def cover(C):       return all(u in C or v in C for u, v in E)

def has(pred, k):                       # brute force: some set of size k?
    return any(pred(set(S)) for S in combinations(V, k))

n = len(V)
same = all(has(independent, k) == has(cover, n - k) for k in range(n + 1))
print("for every k: IS(G, k) yes  <=>  VC(G, n - k) yes:", same)
alpha = max(k for k in range(n + 1) if has(independent, k))
tau = min(k for k in range(n + 1) if has(cover, k))
print("largest independent set", alpha, "+ smallest vertex cover", tau, "=", alpha + tau, "= n")
S = next(set(S) for S in combinations(V, alpha) if independent(set(S)))
print("one maximum IS:", sorted(S), " its complement is a cover:", cover(set(V) - S))

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

for every k: IS(G, k) yes  <=>  VC(G, n - k) yes: True
largest independent set 4 + smallest vertex cover 4 = 8 = n
one maximum IS: [0, 3, 5, 6]  its complement is a cover: True

৮টি অর্ডারের বিরোধ-graph-এ প্রতিটি k-তে উত্তর মিলেছে, আর ৪ + ৪ = n. প্রমাণ এক লাইনের: S-এর ভেতরে কোনো edge নেই ⇔ প্রতিটি edge-এর অন্তত এক প্রান্ত V − S-এ; একটি graph-এ মিল শুধু যাচাই।

Search বনাম decision: SAT-এর decision রূপ দ্রুত মেটালে assignment-ও মেলে: x1 = 1 বসিয়ে জিজ্ঞেস করি এখনো satisfiable কি না, তারপর x2, n বার (self-reducibility).

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); ছক (২); HALT-এর উদাহরণ ও যুক্তি (২); দুই ধাপ আর একটি reduction (৩); search বনাম decision (১)। পর্ব ৫৯ · পর্ব ৬১ · পর্ব ৬২

যেখানে নম্বর কাটে: B ≤p SAT দেখিয়ে “B NP-hard” লেখা (দিক উল্টো); B ∈ NP বাদ দেওয়া; f-এর সময় না দেখানো।

ঘ-০৩Savitch-এর উপপাদ্য শর্তসহ লিখুন আর CANYIELD দিয়ে প্রমাণের ধারণা দিন। সময়ের ক্ষেত্রে (P বনাম NP) একই কৌশল কেন কাজ করে না? NL আর coNL সম্পর্কে কী জানা আছে? — ১০ নম্বর (কঠিন)

বক্তব্য (Savitch, ১৯৭০): f(n) ≥ log n হলে NSPACE(f(n)) ⊆ SPACE(f(n)2). ফল: PSPACE = NPSPACE, আর NL ⊆ SPACE(log2 n).

প্রমাণের রূপরেখা: f(n) জায়গার NTM-এর configuration বড়জোর 2O(f(n))টি, তাই গ্রহণ মানে configuration-graph-এ cstart থেকে caccept-এ t = 2O(f(n)) ধাপের মধ্যে পথ।

  1. CANYIELD(c1, c2, t): t ≤ 1 হলে সরাসরি দেখি c1 = c2 বা এক ধাপে যায় কি না।
  2. নইলে প্রতিটি মধ্যবিন্দু cm চেষ্টা করি: CANYIELD(c1, cm, ⌈t/2⌉) আর CANYIELD(cm, c2, ⌊t/2⌋) দুটিই সত্য হলে সত্য।
  3. Recursion-এর গভীরতা log t = O(f(n)), প্রতিটি স্তরে একটি configuration আর counter রাখতে O(f(n)) জায়গা, আর একই জায়গা বারবার ব্যবহার হয়: মোট O(f(n)2). ∎
import random
from collections import deque

def canyield(G, u, v, t, depth, stat):   # path u -> v of length <= t ?
    stat["calls"] += 1; stat["depth"] = max(stat["depth"], depth)
    if t <= 1: return u == v or v in G[u]
    return any(canyield(G, u, m, t // 2, depth + 1, stat) and
               canyield(G, m, v, t - t // 2, depth + 1, stat) for m in G)

def bfs(G, s):
    seen, q = {s}, deque([s])
    while q:
        for y in G[q.popleft()]:
            if y not in seen: seen.add(y); q.append(y)
    return seen

random.seed(83)
n = 8
G = {x: {y for y in range(n) if y != x and random.random() < 0.18} for x in range(n)}
stat = {"calls": 0, "depth": 0}
same = all(canyield(G, u, v, n, 1, stat) == (v in bfs(G, u)) for u in G for v in G)
pairs = sum(len(bfs(G, u)) - 1 for u in G)
print(f"reachable pairs u != v: {pairs}; CANYIELD == BFS on all 64 pairs: {same}")
print(f"max recursion depth: {stat['depth']} (log2 n + 1 = {n.bit_length()})")
print("total calls:", stat["calls"], "-> little space, a lot of time")

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

reachable pairs u != v: 21; CANYIELD == BFS on all 64 pairs: True
max recursion depth: 4 (log2 n + 1 = 4)
total calls: 37036 -> little space, a lot of time

CANYIELD আর BFS সব ৬৪টি জোড়ায় মেলে। গভীরতা মাত্র ৪ (log2 8 + 1): জায়গা কম। কিন্তু call ৩৭,০৩৬টি: Savitch জায়গা বাঁচায় সময়ের বিনিময়ে।

সময়ে কেন নয়: জায়গা পুনর্ব্যবহার করা যায়, সময় নয়; মধ্যবিন্দু খোঁজা সময়ে সূচকীয়। NL ও coNL: NL = coNL প্রমাণিত (Immerman ও Szelepcsényi, ১৯৮৭–৮৮, inductive counting); কিন্তু L = NL কি না, অজানা।

পরীক্ষক যা খোঁজেন: শর্তসহ বক্তব্য (২); configuration গোনা (১); CANYIELD আর জায়গার হিসাব (৪); সময়ে কেন নয় (১); NL = coNL আর L বনাম NL (২)। পর্ব ৬৪ · পর্ব ৬৬

যেখানে নম্বর কাটে: f(n) ≥ log n শর্ত বাদ; “Savitch দিয়ে P = NP” লেখা; “L = NL প্রমাণিত” লেখা।

ঘ-০৪BPP আর BQP-এর সংজ্ঞা দিন। ভুলের সীমা 1/3 কেন বিশেষ কিছু নয়, amplification দিয়ে দেখান। BPP, BQP আর NP-র মধ্যে কী প্রমাণিত আর কী অজানা? Quantum computer কি computability-র সীমা ভাঙে? — ১০ নম্বর (কঠিন)

সংজ্ঞা: BPP: polynomial সময়ের probabilistic TM, যা প্রতিটি input-এ সঠিক উত্তর দেয় অন্তত 2/3 সম্ভাবনায় (দুই দিকের ভুল ≤ 1/3). BQP: polynomial আকারের uniform quantum circuit, যার ভুল প্রতিটি input-এ ≤ 1/3.

Amplification: k বার স্বাধীনভাবে চালিয়ে সংখ্যাগরিষ্ঠ উত্তর নিলে ভুল দ্রুত কমে; Hoeffding-এর সীমায় ≤ e−k/18. নিচের ব্লক 1/3 ভুলের পরীক্ষায় ভুলের নিখুঁত মান (binomial যোগফল) আর সীমা পাশাপাশি দেখায়।

from fractions import Fraction
from math import comb, exp

# a BPP-style test is wrong with probability exactly 1/3 on some input;
# run it k times independently (k odd) and take the majority vote
def majority_error(k, err=Fraction(1, 3)):
    return sum(comb(k, j) * err**j * (1 - err)**(k - j) for j in range(k // 2 + 1, k + 1))

for k in (1, 3, 11, 31, 101):
    e = majority_error(k)
    print(f"k={k:3}  exact error {float(e):.3e}   Hoeffding bound e^(-k/18) = {exp(-k / 18):.3e}")

k = next(k for k in range(1, 400, 2) if majority_error(k) < Fraction(1, 10**6))
print("smallest odd k with error < 10^-6:", k)

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

k=  1  exact error 3.333e-01   Hoeffding bound e^(-k/18) = 9.460e-01
k=  3  exact error 2.593e-01   Hoeffding bound e^(-k/18) = 8.465e-01
k= 11  exact error 1.221e-01   Hoeffding bound e^(-k/18) = 5.427e-01
k= 31  exact error 2.702e-02   Hoeffding bound e^(-k/18) = 1.787e-01
k=101  exact error 2.724e-04   Hoeffding bound e^(-k/18) = 3.657e-03
smallest odd k with error < 10^-6: 193

১০১ বারে ভুল প্রায় 2.7 × 10−4, ১৯৩ বারে দশ লাখে একের নিচে। সীমাটি ঢিলা হলেও যথেষ্ট: ভুল k-এ সূচকীয় হারে কমে, তাই 1/2-এর চেয়ে ছোট যেকোনো ধ্রুবকে একই শ্রেণি।

দাবিঅবস্থা
P ⊆ BPP ⊆ PSPACEপ্রমাণিত
BPP ⊆ BQP ⊆ PP ⊆ PSPACEপ্রমাণিত
P = BPPব্যাপকভাবে অনুমিত (derandomization), প্রমাণিত নয়
Factoring ∈ BQPপ্রমাণিত (Shor, ১৯৯৪); factoring BPP-তে আছে কি না অজানা
NP ⊆ BQP?অজানা; Grover-এর খোঁজে লাভ শুধু বর্গমূল

Computability: সাধারণ TM quantum computer-কে সূচকীয় সময়ে নকল করতে পারে, তাই halting-এর মতো uncomputable সমস্যা quantum-এও uncomputable; প্রশ্ন শুধু দক্ষতার।

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা ভুলের সীমাসহ (২); amplification-এর যুক্তি (২); প্রমাণিত অন্তর্ভুক্তি (৩); অজানা প্রশ্ন সৎভাবে (২); computability-র উত্তর (১)। পর্ব ৬৯ · পর্ব ৭৫

যেখানে নম্বর কাটে: “quantum computer সব সম্ভাবনা একসঙ্গে চেষ্টা করে, তাই NP-complete সমাধান করে” লেখা; “P = BPP প্রমাণিত” লেখা।

৬ · অংশ ঙ — কঠিন সমস্যা সামলানো আর প্রয়োগ (মডিউল ১২–১৩)

রিভিশন: পর্ব ৭১ (approximation), পর্ব ৭২ (FPT), পর্ব ৭৩ (SAT solver ও heuristic), পর্ব ৭৭ (model checking), পর্ব ৭৮ (program analysis).

ঙ-০১একটি NP-hard optimisation সমস্যার মুখে exact algorithm, approximation algorithm আর heuristic-এর তুলনা করুন: কী নিশ্চয়তা দেয়, কী দেয় না, কখন কোনটি। Vertex cover-এ maximal matching কেন 2-approximation, প্রমাণের মূল যুক্তি দিন। — ১০ নম্বর (মাঝারি)

সংজ্ঞা: Minimisation-এ approximation algorithm-এর ratio ρ, যদি polynomial সময়ে প্রতিটি input-এ ALG ≤ ρ · OPT. Heuristic: বাস্তবে প্রায়ই ভালো, কিন্তু প্রমাণিত সীমা নেই। Exact: সবসময় OPT, worst case-এ সময় সূচকীয় হতে পারে।

মাপকাঠিExactApproximationHeuristic
উত্তরের মানOPT≤ ρ · OPT, প্রমাণিতকোনো নিশ্চয়তা নেই
সময়worst case-এ সূচকীয় হতে পারেpolynomialসাধারণত দ্রুত
উদাহরণSAT/ILP solver, branch and bound, FPT (2k · m)matching দিয়ে vertex cover (২), metric TSP (Christofides ১.৫)greedy-by-degree, local search
কখনছোট বা গঠনযুক্ত instanceনিশ্চয়তা দরকারবড় instance, কম সময়

২-এর প্রমাণ: Maximal matching M নিন আর প্রতিটি edge-এর দুই প্রান্ত cover-এ রাখুন। (১) Maximal বলে প্রতিটি edge M-এর কোনো প্রান্ত ছোঁয়, তাই এটি cover. (২) M-এর edge-গুলো কোনো প্রান্ত ভাগ করে না, তাই যেকোনো cover-এ প্রতিটির জন্য আলাদা vertex লাগে: OPT ≥ |M|। (৩) ALG = 2|M| ≤ 2 · OPT. ∎

import random
from itertools import combinations
def opt_vc(n, E):                       # exact, brute force (small n only)
    for k in range(n + 1):
        for C in combinations(range(n), k):
            if all(u in C or v in C for u, v in E): return k
def matching_vc(E):                     # take both ends of a maximal matching
    C = set()
    for u, v in E:
        if u not in C and v not in C: C |= {u, v}
    return len(C)
def greedy_vc(E):                       # heuristic: highest degree first
    E, C = list(E), set()
    while E:
        deg = {}
        for u, v in E: deg[u] = deg.get(u, 0) + 1; deg[v] = deg.get(v, 0) + 1
        x = max(deg, key=lambda y: (deg[y], -y)); C.add(x)
        E = [e for e in E if x not in e]
    return len(C)
random.seed(2026)
rm, rg = [], []
for trial in range(300):
    n = random.randint(5, 11)
    E = [e for e in combinations(range(n), 2) if random.random() < 0.3]
    if not E: continue
    o = opt_vc(n, E)
    rm.append(matching_vc(E) / o); rg.append(greedy_vc(E) / o)
print(f"{len(rm)} graphs  matching: worst {max(rm):.2f} mean {sum(rm)/len(rm):.2f} (proved <= 2)")
print(f"{len(rg)} graphs  greedy:   worst {max(rg):.2f} mean {sum(rg)/len(rg):.2f} (no constant bound)")

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

298 graphs  matching: worst 2.00 mean 1.71 (proved <= 2)
298 graphs  greedy:   worst 1.50 mean 1.02 (no constant bound)

৩০০টির ২৯৮টিতে edge ছিল। এখানে greedy গড়ে প্রায় নিখুঁত (১.০২), matching ১.৭১; তবু নিশ্চয়তা শুধু matching-এর, আর একটিতে তা ঠিক ২ ছুঁয়েছে। বিশেষভাবে বানানো graph-পরিবারে greedy-র ratio log n-এর মতো বাড়ে (পর্ব ৭১)।

সীমা: P ≠ NP ধরে নিলে কিছু সমস্যায় approximation-ও কঠিন: সাধারণ TSP-তে কোনো ধ্রুবক ρ নেই, MAX-3SAT-এ 7/8-এর চেয়ে ভালো নয় (Håstad, ২০০১)।

পরীক্ষক যা খোঁজেন: তিন সংজ্ঞা (২); ছক (৩); ২-এর প্রমাণ তিন ধাপে (৩); inapproximability শর্তসহ (১); কখন কোনটি (১)। পর্ব ৭১ · পর্ব ৭২ · পর্ব ৭৩

যেখানে নম্বর কাটে: “greedy গড়ে ভালো, তাই 2-approximation-এর চেয়ে ভালো” লেখা; ratio-তে “প্রতিটি input-এ” বাদ দেওয়া; শর্ত ছাড়া inapproximability লেখা।

ঙ-০২Model checking আর software testing-এর তুলনা করুন: কী যাচাই করে, কী নিশ্চয়তা দেয়, সীমা কোথায়। Rice-এর উপপাদ্য থাকা সত্ত্বেও model checker আর static analyzer কীভাবে কাজ করে? — ১০ নম্বর (মাঝারি)

সংজ্ঞা: Testing কিছু নির্বাচিত execution চালিয়ে আউটপুট মেলায়। Model checking একটি সসীম মডেলের (Kripke structure) সব reachable state আর পথ স্বয়ংক্রিয়ভাবে খুঁজে দেখে মডেলটি একটি temporal logic সূত্র (LTL বা CTL) মানে কি না; না মানলে একটি counterexample trace দেয়।

মাপকাঠিTestingModel checking
কী দেখেকিছু executionমডেলের সব interleaving
Bug পেলেএকটি ব্যর্থ testসবচেয়ে ছোট counterexample trace (BFS হলে)
Bug না পেলেশুধু “এই test-গুলোতে নেই”এই মডেলে নেই, প্রমাণসহ
সীমাঅনুপস্থিতি দেখাতে পারে নাstate explosion; মডেল আর আসল কোড আলাদা হতে পারে

উদাহরণ: বাজারঘরের দুই checkout worker “busy” flag দেখে, তারপর আলাদা ধাপে flag বসায়। নিচের ব্লক BFS-এ সব interleaving দেখে, আর ২০টি এলোমেলো schedule-এ test চালায়।

import random
from collections import deque
# two checkout workers share one "busy" flag. pc: 0 idle, 1 saw flag free,
# 2 critical (writes stock), 3 done. atomic=True: check-and-set is one step
def moves(s, atomic):
    for i in (0, 1):
        pc, busy = list(s[:2]), s[2]
        if pc[i] == 0 and not busy:
            pc[i] = 2 if atomic else 1; yield (*pc, atomic)  # atomic: set busy now
        elif pc[i] == 1: pc[i] = 2; yield (*pc, True)
        elif pc[i] == 2: pc[i] = 3; yield (*pc, False)
bad = lambda s: s[0] == 2 and s[1] == 2            # both in the critical step
def model_check(atomic):                           # BFS over every interleaving
    start = (0, 0, False); dist, q = {start: 0}, deque([start])
    while q:
        s = q.popleft()
        if bad(s): return len(dist), dist[s]
        for t in moves(s, atomic):
            if t not in dist: dist[t] = dist[s] + 1; q.append(t)
    return len(dist), None
for atomic in (False, True):
    n, d = model_check(atomic)
    print(f"atomic={atomic}: states seen {n}, shortest bug trace: {d}")
random.seed(7); hits = 0
for run in range(20):                              # testing: 20 random schedules
    s = (0, 0, False)
    while (m := list(moves(s, False))):
        s = random.choice(m)
        if bad(s): hits += 1; break
print(f"random testing of the non-atomic version: bug seen in {hits} of 20 runs")

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

atomic=False: states seen 14, shortest bug trace: 4
atomic=True: states seen 8, shortest bug trace: None
random testing of the non-atomic version: bug seen in 5 of 20 runs

Check আর set আলাদা হলে চার ধাপের trace: দুজনেই flag খালি দেখে, তারপর দুজনেই ঢোকে। Atomic test-and-set-এ ৮টি reachable state-এর একটিতেও bug নেই: এই মডেলের জন্য প্রমাণ। Testing ২০ বারের ৫ বারে bug দেখেছে; বাকি ১৫টি দেখে “bug নেই” বলা যেত না। Edsger Dijkstra-র নামে প্রচলিত কথা: testing bug-এর উপস্থিতি দেখায়, অনুপস্থিতি নয়।

Rice-এর সঙ্গে বিরোধ নেই: Rice সাধারণ program-এর কথা বলে; model checking সসীম মডেলে, যেখানে প্রশ্ন decidable. Static analyzer সাধারণ program-এ ছাড় দেয়: sound হলে কোনো bug ছাড়ে না কিন্তু ভুয়া সতর্কতা দেয়, নয়তো কিছু bug ছাড়ে বা সময়সীমায় “জানি না” বলে।

পরীক্ষক যা খোঁজেন: দুই সংজ্ঞা (২); ছক (৩); একটি concurrency উদাহরণ (২); Rice-এর সঙ্গে সম্পর্ক আর sound বনাম complete (৩)। পর্ব ৭৭ · পর্ব ৭৮ · পর্ব ৫৩

যেখানে নম্বর কাটে: “model checking পুরো program প্রমাণ করে” লেখা (প্রমাণ মডেলের); “Rice-এর কারণে কোনো যাচাই-tool সম্ভব নয়” লেখা।

৭ · তিন মিনিটে নতুনকে বোঝান — পাঁচটি আদর্শ উত্তর

“যিনি এই বিষয় পড়েননি, তাঁকে বোঝান”: এখানে দেখা হয় আপনি মূল ধারণা জানেন কি না, আর সরল করতে গিয়ে ভুল বলেন কি না। কাঠামো: উপমা → নিখুঁত মূল কথা → ছোট উদাহরণ → কী জানা নেই বা কোথায় উপমা ভাঙে।

ত-০১Halting problem কী, আর কেন কোনো program তা সমাধান করতে পারে না? (সহজ–মাঝারি)

উপমা: বাজারঘর চায় এমন একটি “পরীক্ষক” program, যে যেকোনো program আর তার input দেখে বলে দেবে সেটি একসময় থামবে, নাকি চিরকাল চলবে।

মূল কথা: Turing ১৯৩৬ সালে দেখান, এমন পরীক্ষক কেউ লিখতে পারবে না, যত দ্রুত কম্পিউটারই হোক। ধরুন H আছে। একটি দুষ্টু program D বানাই: D নিজের code H-কে দেখায়, H “থামবে” বললে D চিরকাল ঘোরে, “থামবে না” বললে থামে। D নিজের ওপর চললে H যা-ই বলুক, ভুল।

উদাহরণ: “প্রতিটি সংখ্যা Collatz নিয়মে ১-এ পৌঁছায় কি না” আসলে একটি program-এর থামার প্রশ্ন; আজও অমীমাংসিত।

সীমা: নির্দিষ্ট অনেক program-এর থামা যাচাই করা যায়; অসম্ভব শুধু সব program-এর জন্য একটি নিখুঁত পরীক্ষক। পর্ব ৫১

ত-০২P বনাম NP প্রশ্নটি কী, আর কেন এত গুরুত্বপূর্ণ? (সহজ–মাঝারি)

উপমা: একটি বড় jigsaw puzzle মেলানো কঠিন, কিন্তু কেউ মিলিয়ে দিলে ঠিক হয়েছে কি না দেখা সহজ।

মূল কথা: P: যেসব হ্যাঁ/না প্রশ্নের উত্তর polynomial সময়ে বের করা যায়। NP: যেসব প্রশ্নে “হ্যাঁ”-এর সাক্ষ্য দিলে দ্রুত যাচাই করা যায়। প্রশ্ন: যা দ্রুত যাচাই করা যায়, তা কি দ্রুত খুঁজেও পাওয়া যায়?

উদাহরণ: বাজারঘরের ৬৪ জেলার প্রতিটিতে একবার গিয়ে ৩০০০ কিলোমিটারের মধ্যে ফেরা যায় কি না: রুট দিলে যোগ করে দেখা সহজ, কিন্তু খুঁজে বের করার দ্রুত পদ্ধতি জানা নেই।

সীমা: উত্তর কেউ জানেন না; বেশিরভাগ গবেষক P ≠ NP মনে করেন, প্রমাণ নেই (Clay Institute-এর Millennium Prize সমস্যার একটি)। NP মানে “non-polynomial” নয়। পর্ব ৬৩

ত-০৩Regular expression দিয়ে কেন বন্ধনীর মিল যাচাই করা যায় না? (সহজ)

উপমা: খাতা ছাড়া একজন দারোয়ান, শুধু কয়েকটি আঙুলে গোনেন; একটি সীমার বেশি গুনতে পারেন না।

মূল কথা: Formal regex যা বর্ণনা করে, ঠিক তা-ই finite automaton চেনে, আর তার স্মৃতি কয়েকটি state. ((( … ))) মেলাতে খোলা বন্ধনীর সংখ্যা মনে রাখতে হয়, যা যেকোনো বড় হতে পারে। k টি state-এর যন্ত্রে k + 1টি আলাদা গভীরতার দুটি একই state-এ পড়বেই, তখন যন্ত্র ভুল করবে।

উদাহরণ: বাজারঘরের order-query-তে nested বন্ধনী থাকলে regex নয়, grammar আর parser লাগে।

সীমা: কিছু বাস্তব regex engine-এ recursion-এর মতো বাড়তি সুবিধা আছে, যা formal regex-এর বাইরে; তবু parser-ই পরিষ্কার সমাধান। পর্ব ১৭ · পর্ব ২৫

ত-০৪এত সরল Turing machine কীভাবে আজকের যেকোনো কম্পিউটারের সমান ক্ষমতাধর? (মাঝারি)

উপমা: একজন হিসাবরক্ষক, অসীম লম্বা খাতা, পেনসিল-রাবার আর এক পাতার নিয়ম; একবারে একটি ঘর পড়েন, লেখেন, বাঁয়ে বা ডানে সরেন।

মূল কথা: একাধিক tape, random-access memory বা একাধিক processor যন্ত্রকে দ্রুত করে, কিন্তু নতুন সমস্যা সমাধান করায় না: প্রতিটি সুবিধা মূল যন্ত্রে ধাপে ধাপে নকল করা যায়। ক্ষমতা আর গতি আলাদা।

উদাহরণ: {w#w} চেনাতে দুই tape-এ প্রায় 3m ধাপ, এক tape-এ প্রায় 2m2; উত্তর একই।

সীমা: “algorithm দিয়ে যা গণনা করা যায়, Turing machine তা পারে” হলো Church–Turing thesis: অত্যন্ত সমর্থিত দাবি, উপপাদ্য নয়। আর আসল কম্পিউটারের memory সসীম। পর্ব ৪৫ · পর্ব ৪৭

ত-০৫একটি সমস্যা NP-complete জানলে বাস্তবে কী করবেন? (মাঝারি–কঠিন)

উপমা: রোগের নিশ্চিত দ্রুত নিরাময় জানা না থাকলেও চিকিৎসা থামে না: উপসর্গ কমানো, বিশেষ ক্ষেত্রে বিশেষ ওষুধ।

মূল কথা: NP-complete মানে “সব input-এ দ্রুত নিখুঁত algorithm জানা নেই”, “অসম্ভব” নয়। পথ: (১) ছোট instance-এ exact খোঁজ বা SAT/ILP solver; (২) বিশেষ গঠন বা ছোট parameter k-তে FPT; (৩) নিশ্চয়তাসহ approximation; (৪) heuristic, ফল আলাদাভাবে যাচাই।

উদাহরণ: বাজারঘরের delivery slot-এ বিরোধী অর্ডার আলাদা রাখা একটি graph coloring; SAT solver প্রায়ই দ্রুত উত্তর দেয় (পর্ব ৭৩)।

সীমা: solver-এর দ্রুততা নিশ্চয়তা নয়; সময়সীমা আর বিকল্প পরিকল্পনা রাখুন। পর্ব ৬১ · পর্ব ৭৩

৮ · ভাইভা — কৌশল, ২৪টি প্রশ্ন, ফাঁদ, সৎ উত্তর আর AI

পরীক্ষক আপনার শেষ বাক্য থেকে পরের প্রশ্ন বানান; গণনার তত্ত্বে প্রায় নিশ্চিত দুটি: “কোন শর্তে?” আর “উল্টো দিকটি কি সত্য?” তাই প্রথম উত্তরেই শর্ত আর দিক বলুন।

কী (এক বাক্য) → কোন শর্তে বা কোন দিকে → একটি উদাহরণ বা প্রতিউদাহরণ

“Pumping lemma কী বলে?” — “Regular language-এর যথেষ্ট লম্বা প্রতিটি string-এ, প্রথম p অক্ষরের মধ্যে, একটি অশূন্য অংশ আছে যা বারবার বসালে বা বাদ দিলে string ভাষাতেই থাকে (কী)। এটি শুধু আবশ্যিক শর্ত; মানলেই regular নয় (দিক)। যেমন anbn এটি ভাঙে, আর {aibjck : i = 0 বা j = k} এটি মানে, তবু regular নয় (উদাহরণ)।”

প্রতিটি প্রশ্ন-উত্তরের পর
পরীক্ষক
প্রার্থী (মূল কথা)
কেন ভালো উত্তর
জোড়া পর্ব
  1. শুরু। পুরো প্রমাণ নয়; D-এর গঠন আর “নিজের ওপর চালানো”, এটুকুই।
  2. এক ধাপ এগিয়ে। L decidable ⇔ L ও complement দুটিই recognizable, এই উপপাদ্য দিয়ে।
  3. নির্দিষ্ট reduction. “reduction করি” বললে নম্বর নেই; f কী বানায়, সেটাই উত্তর।
  4. ফাঁদ এড়ানো। পরীক্ষক ইচ্ছে করে উল্টো দিক দেন; প্রার্থী নিয়মটি নাম ধরে বলেন।
  5. শর্ত আর বাড়তি তথ্য। Rice খাটে কারণ প্রশ্নটি L(M) নিয়ে; সঙ্গে recognizability-র অবস্থান।
  6. শেষ। “অসম্ভব” থেকে “কী ছাড় দিয়ে সম্ভব”: sound বনাম complete.

২৪টি ছোট প্রশ্ন — মুখে বলার উত্তর আর পরের প্রশ্ন

জোরে উত্তর বলুন, তারপর প্রশ্নে চেপে মেলান; প্রতিটিতে ৩০ সেকেন্ডের বেশি নয়। “পরের প্রশ্ন”-এর উত্তরও মুখে বলুন।

Automaton আর regular language (পর্ব ০১–২৪)

ভ-০১∅ আর {ε}-এর পার্থক্য কী? (সহজ)

∅ কোনো string নেই এমন language; {ε}-এ ঠিক একটি string, ফাঁকা string. ∅L = ∅, কিন্তু {ε}L = L; আর ∅∗ = {ε}। পর্ব ০৩

পরের প্রশ্ন: L∗-এ কি সবসময় ε থাকে? — হ্যাঁ, শূন্যবার জোড়া লাগানোর ফল হিসেবে; L+-এ থাকে কেবল ε ∈ L হলে।

ভ-০২DFA-তে dead state কেন দরকার? (সহজ)

DFA-র δ total; বৈধ গন্তব্যহীন transition যায় একটি অ-গ্রহণকারী dead state-এ, যেখান থেকে বেরোনো যায় না। ছবিতে বাদ চলে, complement-এর আগে নয়। পর্ব ০৮

পরের প্রশ্ন: NFA-তে? — দরকার নেই; খালি সেট মানে সেই পথ মরে গেছে, subset construction-এ সেটিই ∅ state.

ভ-০৩Minimal DFA কি অনন্য? (মাঝারি)

হ্যাঁ, state-এর নাম বদল বাদে; কারণ তার state ঠিক Myhill–Nerode-এর class. Table-filling বা Hopcroft (O(n log n)) দিয়ে পাওয়া যায়, আগে unreachable state বাদ দিয়ে। পর্ব ১৯

পরের প্রশ্ন: Minimal NFA? — অনন্য না-ও হতে পারে, আর খুঁজে পাওয়া কঠিন (PSPACE-complete বলে জানা)।

ভ-০৪দুটি DFA একই language চেনে কি না কীভাবে যাচাই করবেন? (মাঝারি)

Product construction দিয়ে symmetric difference-এর DFA বানিয়ে emptiness দেখি (BFS); ফাঁকা না হলে সবচেয়ে ছোট পার্থক্যের string-ও পাওয়া যায়। অথবা দুটিকে minimise করে isomorphic কি না দেখি। EQDFA decidable. পর্ব ২০

পরের প্রশ্ন: দুটি CFG-তে? — undecidable (EQCFG), পর্ব ৫৪।

Grammar, PDA আর parsing (পর্ব ২৫–৪২)

ভ-০৫Ambiguous grammar আর inherently ambiguous language-এর পার্থক্য? (মাঝারি)

Ambiguous grammar: কোনো string-এর দুটি parse tree. প্রায়ই অন্য grammar লিখে সরানো যায় (precedence-এর স্তর)। Inherently ambiguous language-এর প্রতিটি grammar-ই ambiguous, যেমন {aibjck : i = j বা j = k}। পর্ব ২৭

পরের প্রশ্ন: একটি CFG ambiguous কি না decide করা যায়? — না; PCP থেকে reduction (পর্ব ৫৪)।

ভ-০৬CYK কী করে, আর তার খরচ কত? (মাঝারি)

CNF grammar-এ প্রতিটি substring কোন variable থেকে আসে, ছোট থেকে বড় দৈর্ঘ্যে table-এ ভরে; সময় O(n3 · |G|)। তাই CFL-এর membership polynomial সময়ে decidable. পর্ব ৩১

পরের প্রশ্ন: Compiler কেন CYK ব্যবহার করে না? — LL/LR linear সময়ে চলে; CYK সাধারণ কিন্তু ধীর।

ভ-০৭CFL-এর pumping lemma-র শর্তগুলো বলুন। (মাঝারি)

s = uvxyz, যেখানে |vy| ≥ 1, |vxy| ≤ p, আর প্রতিটি i ≥ 0-তে uvixyiz ∈ L. দুটি অংশ একসঙ্গে pump হয়, আর |vxy| ≤ p জানালা যেকোনো জায়গায় বসতে পারে। পর্ব ৩৬

পরের প্রশ্ন: এতে আটকে গেলে? — Ogden-এর lemma: চিহ্নিত অবস্থান দিয়ে জানালা নিয়ন্ত্রণ।

ভ-০৮PDA-তে দুটি stack দিলে কী হয়? (মাঝারি)

Turing machine-এর সমান ক্ষমতা: দুই stack মিলে head-এর বাঁ আর ডান দিকের tape নকল করে (two-stack PDA). একটি stack-এর বদলে একটি queue দিলেও একই। পর্ব ৩২ · পর্ব ৪৫

পরের প্রশ্ন: তাহলে দুই stack-এর PDA-র emptiness? — undecidable, কারণ ETM undecidable.

Turing machine আর computability (পর্ব ৪৩–৫৬)

ভ-০৯Recognizer আর decider-এর পার্থক্য এক বাক্যে? (সহজ)

Decider প্রতিটি input-এ থামে; recognizer শুধু “হ্যাঁ”-তে থামার নিশ্চয়তা দেয়, “না”-তে চিরকাল চলতে পারে। পর্ব ৫০

পরের প্রশ্ন: প্রতিটি language কি কোনো TM-এর language? — না; TM গণনাযোগ্য সংখ্যক, language অগণনযোগ্য।

ভ-১০Universal Turing machine কী? (সহজ)

U, input ⟨M, w⟩ পেয়ে M-কে w-এ নকল করে, M যা করে তা-ই করে। Program-ই data: আজকের stored-program কম্পিউটার আর interpreter-এর তাত্ত্বিক রূপ। পর্ব ৪৮

পরের প্রশ্ন: U কি decider? — না; M না থামলে U-ও থামে না। U ATM-এর recognizer.

ভ-১১Post correspondence problem কেন গুরুত্বপূর্ণ? (মাঝারি)

যন্ত্রহীন একটি string-জোড়ার ধাঁধা (Post, ১৯৪৬), তবু undecidable; তাই grammar-এর প্রশ্নে (CFG ambiguous কি না, দুই CFG-র intersection ফাঁকা কি না) reduction-এর সেতু। পর্ব ৫৪

পরের প্রশ্ন: Alphabet-এ একটিমাত্র চিহ্ন থাকলে? — decidable হয়ে যায়; শুধু দৈর্ঘ্যের পার্থক্যের হিসাব।

ভ-১২Busy Beaver function কেন computable নয়? (কঠিন)

S(n) = n state-এর থামা যন্ত্রগুলোর সবচেয়ে লম্বা run. এটি গণনা করা গেলে halting decide করা যেত: S(n) ধাপেও না থামলে আর থামবে না। S(5) = 47,176,870, যা ২০২৪ সালে bbchallenge দল যন্ত্রে-যাচাই করা প্রমাণে প্রতিষ্ঠা করেছে বলে ঘোষণা করে। পর্ব ৫৫

পরের প্রশ্ন: তাহলে S(5) জানা গেল কীভাবে? — প্রতিটি নির্দিষ্ট n-এর জন্য আলাদা প্রমাণ সম্ভব; অসম্ভব শুধু সব n-এর জন্য একটি algorithm.

P, NP আর NP-completeness (পর্ব ৫৭–৬৩)

ভ-১৩Cook–Levin theorem কী বলে? (সহজ)

SAT NP-complete (Cook ১৯৭১, Levin ১৯৭৩): যেকোনো NP যন্ত্রের গ্রহণকারী computation-এর tableau একটি polynomial আকারের সূত্রে লেখা যায়। পর্ব ৬০

পরের প্রশ্ন: তারপর অন্যগুলো? — SAT বা 3SAT থেকে ≤p দিয়ে; Karp ১৯৭২-এ ২১টি সমস্যা দেখান।

ভ-১৪SUBSET-SUM-এর O(n · t) DP থাকলে সেটি কেন P-তে নয়? (মাঝারি)

t লেখা হয় binary-তে, প্রায় log2 t bit-এ; O(n · t) input-দৈর্ঘ্যের সূচকীয়। এটি pseudo-polynomial. পর্ব ৬১

পরের প্রশ্ন: t unary-তে দিলে? — তখন DP polynomial; এজন্য SUBSET-SUM-কে weakly NP-complete বলা হয়।

ভ-১৫2SAT সহজ, 3SAT কঠিন — কেন? (মাঝারি)

(a ∨ b) clause দুটি implication ¬a → b, ¬b → a; implication graph-এ কোনো x আর ¬x একই strongly connected component-এ থাকলে unsatisfiable. Polynomial সময়। 3SAT NP-complete. পর্ব ৬১

পরের প্রশ্ন: তাহলে কি 3SAT P-তে নেই, প্রমাণিত? — না; সেটি P ≠ NP-এর সমান কথা, যা খোলা।

ভ-১৬একটি coNP-complete সমস্যা বলুন। (মাঝারি)

TAUTOLOGY (সব assignment-এ সত্য) বা UNSAT: “না” উত্তরের সাক্ষ্য একটি assignment, যা দ্রুত যাচাই হয়। পর্ব ৬২

পরের প্রশ্ন: কোনো coNP-complete সমস্যা NP-তে পাওয়া গেলে? — NP = coNP হতো।

উন্নত complexity (পর্ব ৬৪–৭০)

ভ-১৭TQBF কেন PSPACE-এ, আর খেলার সঙ্গে তার সম্পর্ক কী? (মাঝারি)

Quantifier ধরে recursion: ∃x-এ দুই মানের একটিতে সত্য, ∀x-এ দুটিতেই; গভীরতা n, জায়গা polynomial. ∃ আর ∀ পালাক্রমে মানে দুই খেলোয়াড়ের চাল। পর্ব ৬৫

পরের প্রশ্ন: সময় কত লাগে? — সরল recursion-এ 2n; polynomial সময় জানা নেই, কারণ তা P = PSPACE বোঝাত।

ভ-১৮Time hierarchy theorem কী প্রমাণ করে? (মাঝারি)

Time-constructible f-এর জন্য এমন language আছে যা O(f(n)) সময়ে decidable কিন্তু o(f(n)/log f(n)) সময়ে নয়; diagonalization দিয়ে। ফল P ⊊ EXP. পর্ব ৬৭

পরের প্রশ্ন: এটি দিয়ে P ≠ NP হয় না কেন? — এটি একই ধরনের সম্পদের দুই মাত্রা আলাদা করে; deterministic বনাম nondeterministic নয়।

ভ-১৯Relativization বাধা কী? (কঠিন)

Baker–Gill–Solovay (১৯৭৫): এমন oracle A আছে যাতে PA = NPA, আর B যাতে PB ≠ NPB. তাই যে প্রমাণ-কৌশল যেকোনো oracle-এ একইভাবে খাটে (সরল diagonalization বা simulation), তা একা P বনাম NP মেটাতে পারে না। পর্ব ৬৩ · পর্ব ৬৮

পরের প্রশ্ন: আর কোনো বাধা? — natural proofs আর algebrization.

ভ-২০P/poly-তে undecidable language থাকতে পারে কেন? (কঠিন)

প্রতিটি দৈর্ঘ্যের আলাদা circuit, যা কোনো algorithm বানাবে এমন শর্ত নেই। Unary language-এ প্রতিটি n-এ একটি বিট যথেষ্ট, তাই unary halting-ও P/poly-তে। পর্ব ৭০

পরের প্রশ্ন: NP ⊆ P/poly হলে? — Karp–Lipton: polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ে।

নতুন দিগন্ত আর প্রয়োগ (পর্ব ৭১–৮০)

ভ-২১PCP theorem এক বাক্যে? (কঠিন)

NP = PCP(O(log n), O(1)): প্রতিটি NP প্রমাণ এমনভাবে লেখা যায় যে verifier O(log n) এলোমেলো বিট নিয়ে ধ্রুবক সংখ্যক জায়গা পড়েই ভুল প্রমাণ উচ্চ সম্ভাবনায় ধরে। পর্ব ৭১

পরের প্রশ্ন: কারা প্রমাণ করেন? — Arora–Safra আর Arora–Lund–Motwani–Sudan–Szegedy (১৯৯০-এর দশকের শুরু); Dinur পরে combinatorial প্রমাণ দেন।

ভ-২২Fixed-parameter tractable মানে কী? (মাঝারি)

সময় f(k) · nO(1), যেখানে সূচকীয় অংশ শুধু parameter k-তে। k-vertex cover-এ প্রতিটি edge-এর দুই প্রান্তে শাখা দিলে O(2k · m). পর্ব ৭২

পরের প্রশ্ন: k-CLIQUE? — W[1]-hard, তাই FPT নয় বলে বিশ্বাস করা হয় (প্রমাণিত নয়)।

ভ-২৩Zero-knowledge proof কী? (মাঝারি)

Prover verifier-কে কোনো দাবির সত্যতা বোঝান, কিন্তু দাবিটি সত্য হওয়া ছাড়া আর কিছু জানান না; প্রমাণ: verifier-এর দেখা কথোপকথন একটি simulator দাবির সাক্ষ্য ছাড়াই বানাতে পারে। উদাহরণ graph isomorphism protocol. পর্ব ৭৪

পরের প্রশ্ন: IP কত বড়? — IP = PSPACE (Shamir, ১৯৯২)।

ভ-২৪One-way function থাকলে P ≠ NP কেন? (কঠিন)

P = NP হলে “x-এর prefix u দিয়ে শুরু এমন উল্টো ছবি আছে কি?” প্রশ্নটি NP-তে বলে দ্রুত মেটে, আর বিট ধরে ধরে যেকোনো f উল্টানো যায়। তাই OWF ⇒ P ≠ NP. পর্ব ৭৬

পরের প্রশ্ন: উল্টোটি? — জানা নেই; P ≠ NP worst-case কথা, cryptography-র দরকার average-case কঠিনতা।

সাধারণ ফাঁদ — যেসব কথায় নম্বর কাটে

ফাঁদের কথাকেন ভুলঠিক কথা
“Pumping lemma মানে, তাই regular”শর্তটি শুধু আবশ্যিক{aibjck : i = 0 বা j = k} pump হয়, regular নয়
“NFA বেশি শক্তিশালী”subset constructionক্ষমতা সমান, আকার 2n পর্যন্ত আলাদা
“B ≤m ATM, তাই B undecidable”দিক উল্টোATM ≤m B দেখাতে হয়
“Rice বলে M-এর state-সংখ্যা জানা যায় না”প্রশ্নটি syntacticRice শুধু L(M)-এর অতুচ্ছ ধর্মে
“NP মানে non-polynomial”সংজ্ঞা ভুলNondeterministic polynomial; P ⊆ NP
“Quantum computer NP-complete সমাধান করে”জানা নেইBQP বনাম NP অজানা; Grover-এ লাভ বর্গমূল
“L = NL প্রমাণিত” বা “P = BPP প্রমাণিত”খোলা প্রশ্নNL = coNL প্রমাণিত; L বনাম NL, P বনাম BPP খোলা

না জানলে — সৎভাবে উত্তর

আংশিক জানলে বলুন “পুরো প্রমাণ মনে নেই; Savitch-এর মূল কৌশল মধ্যবিন্দু ধরে পথ দুই ভাগ করা, এর বাইরে অনুমান করব না।” সূত্র ভুলে গেলে ছোট উদাহরণে বের করুন: S → AB, A → a, B → b-তে “ab” গুনলে তিন ধাপ, অর্থাৎ 2n − 1. ভুল ধরা পড়লে বলুন “আগে যা বলেছি, তা ভুল; ঠিক হলো …”। সাল, নাম বা শর্ত বানাবেন না।

AI-এর যুগে — AI-কে কড়া পরীক্ষক বানান

AI সহকারী প্রশ্ন বানাতে আর উত্তর যাচাই করাতে কাজে লাগে, কিন্তু গণনার তত্ত্বে প্রায়ই আত্মবিশ্বাসী অথচ ভুল: ভুল language-এর automaton (গোনায় এক কম-বেশি, ε ভোলা, dead state বাদ), pumping-এ ভাগ নিজে বাছা বা একটি ক্ষেত্র দেখানো, decidable আর recognizable গুলিয়ে ফেলা, reduction-এর দিক উল্টানো, শর্ত ছাড়া উপপাদ্য, খোলা প্রশ্নকে মীমাংসিত বলা, বানানো বই বা প্রবন্ধ। তাই তাকে পরীক্ষক বানান, আর প্রতিটি দাবি দৈর্ঘ্য n পর্যন্ত সব string-এ চালিয়ে, প্রতিউদাহরণ খুঁজে আর Sipser, Hopcroft–Motwani–Ullman বা Arora–Barak-এর মতো পাঠ্যবইয়ে মেলান।

তুমি একজন কড়া পরীক্ষক, বিষয় Theory of Computation. নিচে একটি ১০ নম্বরের "তুলনা করুন" ধরনের প্রশ্ন আর আমার উত্তর দিলাম। [প্রশ্ন] [আমার উত্তর — সংজ্ঞা, ছক, উদাহরণ, কখন কোনটি, সীমা] ১. মার্ক-স্কিম বানাও: সংজ্ঞা, তুলনার ছক, উদাহরণ ও প্রতিউদাহরণ, কখন কোনটি, সীমা — কোনটিতে কত। তারপর নম্বর দাও। ২. প্রতিটি উপপাদ্যে কোনো শর্ত বাদ পড়েছে কি না লাইন ধরে বলো (যেমন |xy| ≤ p, f(n) ≥ log n, "অতুচ্ছ" আর "language-এর ধর্ম")। ৩. প্রতিটি reduction-এর দিক ঠিক আছে কি না দেখো: জানা কঠিন সমস্যা বাঁয়ে, নতুনটি ডানে। ৪. কোনো খোলা প্রশ্ন (P বনাম NP, L বনাম NL, P বনাম BPP, BQP বনাম NP) মীমাংসিত বলে লিখেছি কি না দেখো। ৫. আমার দেওয়া প্রতিটি automaton বা grammar-এর জন্য একটি ছোট string দাও, যা আমি নিজে চালিয়ে মেলাতে পারি; উত্তরটি নিজে বলে দিও না। ৬. নিশ্চিত না হলে "নিশ্চিত নই" লেখো; কোনো বই, সাল বা নাম বানাবে না। ৭. শেষে "কোন শর্তে?" আর "উল্টো দিকটি কি সত্য?" ধরনের তিনটি ভাইভা প্রশ্ন দাও, উত্তর ছাড়া।

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

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

ক্রমComplexity শ্রেণিগুলো প্রমাণিত অন্তর্ভুক্তি (⊆) অনুযায়ী ছোট থেকে বড় ক্রমে সাজান (▲▼ চেপে সরান)

  1. L
  2. NL
  3. P
  4. NP
  5. PSPACE
  6. EXP

(সহজ) L3 = {w ∈ {0, 1}∗ : শেষ থেকে তৃতীয় চিহ্ন 1}। এর একটি NFA-তে ৪টি state যথেষ্ট। L3-এর minimal DFA-তে কয়টি state?

  • ৪
  • ৬
  • ৮
  • ১৬

(মাঝারি) আপনি A ≤m B প্রমাণ করেছেন, আর জানেন A undecidable. কোন সিদ্ধান্ত বৈধ?

  • A decidable
  • B undecidable
  • B decidable
  • কোনো সিদ্ধান্ত টানা যায় না

(মাঝারি) একটি Chomsky normal form grammar-এ দৈর্ঘ্য ৬-এর একটি string-এর derivation-এ ঠিক কয়টি ধাপ?

  • ৬
  • ১১
  • ১২
  • ৩৬

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

  • P ≠ NP
  • L = NL
  • NL = coNL
  • P = BPP

(কঠিন) Turing machine M সম্পর্কে নিচের কোন প্রশ্নটি decidable?

  • L(M) regular কি না
  • L(M) = Σ∗ কি না
  • L(M) = ∅ কি না
  • M-এর transition table-এ qreject-এ যাওয়ার কোনো নিয়ম আছে কি না

(কঠিন) একটি polynomial-time randomized algorithm প্রতিটি input-এ ঠিক 1/3 সম্ভাবনায় ভুল করে (দুই দিকেই)। স্বাধীনভাবে ১০১ বার চালিয়ে সংখ্যাগরিষ্ঠ উত্তর নিলে ভুলের সম্ভাবনা প্রায় কত?

  • 1/3
  • প্রায় 2.7 × 10−4
  • ০
  • (1/3)101

শব্দকোষ

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

মনে রাখুন

  1. কাঠামোই নম্বর: সংজ্ঞা → একই সারির তুলনার ছক → উদাহরণ ও প্রতিউদাহরণ → কখন কোনটি → সীমা।
  2. শর্ত ছাড়া উপপাদ্য নয়: pumping-এ |xy| ≤ p ও |y| ≥ 1, CFL-এ |vxy| ≤ p ও |vy| ≥ 1, Savitch-এ f(n) ≥ log n, Rice-এ অতুচ্ছ আর language-এর ধর্ম।
  3. ক্ষমতা বনাম আকার বা গতি: DFA = NFA কিন্তু আকার 2n পর্যন্ত; DTM = NTM কিন্তু সময়ের প্রশ্ন খোলা; DPDA < NPDA.
  4. দিক আর অবস্থা: জানা কঠিন সমস্যা বাঁয়ে; NL = coNL আর PSPACE = NPSPACE প্রমাণিত, P বনাম NP, L বনাম NL, P বনাম BPP খোলা।
  5. ভাইভায় তিন বাক্য: কী → কোন শর্তে বা দিকে → একটি উদাহরণ; না জানলে সৎভাবে বলুন, কিছু বানাবেন না।

পরের পর্বে: পর্ব ৮৪ (প্রমাণ লেখার অনুশীলন — pumping lemma, reduction আর diagonalization)-এ এখানকার তুলনার পেছনের উপপাদ্যগুলোর পূর্ণ প্রমাণ ধাপে ধাপে লেখা, rubric দিয়ে মেলানো আর ভুল প্রমাণ ধরার অনুশীলন।

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

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