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

Randomized complexity — RP, BPP আর ZPP

Randomized Complexity — Probabilistic Turing Machines, One-sided and Two-sided Error, RP, coRP, BPP, ZPP and PP, Amplification, BPP ⊆ PSPACE and the P = BPP Conjecture

Taught in Bangla, this lesson defines probabilistic Turing machines and the classes RP, coRP, BPP, ZPP and PP. It proves amplification by repetition and majority vote, places compositeness in RP with Miller–Rabin, verifies matrix products with Freivalds and compares order lists with Schwartz–Zippel fingerprints, and proves ZPP = RP ∩ coRP and BPP ⊆ PSPACE. In-page Python (Pyodide) measures error rates, and a real desktop run checks its Miller–Rabin against sympy below one million.

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

  • Probabilistic Turing machine-এর নিখুঁত সংজ্ঞা, শাখার সম্ভাবনা আর ভুলের সম্ভাবনা
  • RP, coRP, BPP, ZPP আর PP-র সংজ্ঞা, আর Monte Carlo বনাম Las Vegas
  • Amplification-এর প্রমাণ: one-sided ভুলে পুনরাবৃত্তি, two-sided ভুলে সংখ্যাগরিষ্ঠ ভোট
  • Miller–Rabin, Freivalds আর Schwartz–Zippel দিয়ে তিনটি সমস্যা randomized শ্রেণিতে রাখা
  • ZPP = RP ∩ coRP আর BPP ⊆ PSPACE-এর প্রমাণ, আর P = BPP প্রশ্নের প্রকৃত অবস্থা

১ · মুদ্রা ছুড়ে সিদ্ধান্ত — probabilistic Turing machine

বাজারঘরের দুটি গুদাম, একটি ঢাকায় আর একটি চট্টগ্রামে। প্রতিটির কাছে দিনের শেষে দশ হাজার অর্ডারের একটি তালিকা। দুই তালিকা হুবহু এক কি না, তা জানা দরকার, কিন্তু পুরো তালিকা পাঠানো ধীর। একটি deterministic পদ্ধতিকে, যত চালাকই হোক, প্রায় পুরো তালিকাটাই পাঠাতে হয় (অংশ ৫-এ ফিরব)। অথচ ঢাকা যদি একটি এলোমেলো সংখ্যা r বেছে নিয়ে তালিকার একটি ছোট “আঙুলের ছাপ” (fingerprint) পাঠায়, মাত্র কয়েক ডজন bit-এই প্রায় নিশ্চিত উত্তর মেলে। এলোমেলোতা এখানে সত্যিকারের সম্পদ।

ঈদের আগে মিষ্টির দোকানে এক হাঁড়ি রসগোল্লা ঠিকমতো হয়েছে কি না, দোকানি সবগুলো খেয়ে দেখেন না। হাঁড়ির এলোমেলো জায়গা থেকে কয়েকটি তুলে চেখে দেখেন। কোনো এক জায়গায় গোলমাল থাকলে হয়তো একবারে ধরা পড়ে না, কিন্তু কয়েকবার চাখলে না ধরা পড়ার সম্ভাবনা দ্রুত কমে। এলোমেলো বাছাইয়ের জোর এখানেই: প্রতিপক্ষ জানে না কোথায় চাখা হবে, তাই কোনো নির্দিষ্ট গোলমাল লুকিয়ে রাখা যায় না।

এই ধারণাকে গণনার মডেলে আনতে পর্ব ৪৬-এর nondeterministic Turing machine-এর কাঠামো নেওয়া হয়, শুধু “অনুমান”-কে বদলে “মুদ্রা ছোড়া” করা হয়।

সংজ্ঞা ১.১ (Probabilistic Turing machine, Sipser-এর অনুসরণে)

একটি probabilistic Turing machine M হলো এমন একটি nondeterministic Turing machine, যার প্রতিটি nondeterministic ধাপে ঠিক দুটি বৈধ পরের চাল থাকে; এমন ধাপকে বলা হয় মুদ্রা-ছোড়ার ধাপ. Input w-এর ওপর M-এর computation tree-এর কোনো শাখা b-তে k-টি মুদ্রা-ছোড়ার ধাপ থাকলে

Pr[b] = 2−k,   Pr[M accepts w] = Σb গ্রহণকারী Pr[b],   Pr[M rejects w] = 1 − Pr[M accepts w]

M ভাষা A-কে ভুলের সম্ভাবনা ε নিয়ে চেনে, যদি প্রতিটি w-এর জন্য: w ∈ A হলে Pr[M accepts w] ≥ 1 − ε, আর w ∉ A হলে Pr[M rejects w] ≥ 1 − ε.

সময়ের সংজ্ঞা আগের মতো: M-এর সময় t(n), যদি দৈর্ঘ্য n-এর প্রতিটি input-এ প্রতিটি শাখা t(n) ধাপের মধ্যে থামে। একটি সমতুল্য ছবি প্রায়ই কাজে লাগে: M আসলে একটি deterministic যন্ত্র, যে input w-এর সঙ্গে একটি এলোমেলো bit-string r নেয়, যার দৈর্ঘ্য t(n)-এর বেশি নয়। তখন “Pr[M accepts w]” মানে সব r-এর মধ্যে কত ভাগ r-এ M(w, r) accept করে।

পর্ব ৪৬-এর NTM-এর সঙ্গে মূল পার্থক্য গ্রহণের নিয়মে। NTM accept করে, যদি অন্তত একটি শাখা accept করে, যত বিরলই হোক। Probabilistic যন্ত্রে শাখাগুলো গোনা হয়: একটি শাখা মোট সম্ভাবনার কত অংশ, সেটাই আসল। NTM একটি তাত্ত্বিক “জাদুকরী অনুমানকারী”, বাস্তবে বানানো যায় না; মুদ্রা-ছোড়া যন্ত্র বানানো যায়, যদি এলোমেলো bit-এর একটি ভালো উৎস থাকে (অংশ ৭)।

একটি probabilistic যন্ত্রের computation tree

প্রতিটি শাখার সম্ভাবনা 2−(মুদ্রা-ছোড়ার সংখ্যা). শাখাগুলোর দৈর্ঘ্য আলাদা হতে পারে।

Probabilistic computation tree: accept with probability 1/2 + 1/4 = 3/4 w 1 acc acc rej 0 1 0 1 ১/২ ১/৪ ১/৪ Pr[accept] = ৩/৪
ছবি ৬৯.১ — প্রথম মুদ্রা 0 হলে যন্ত্র সঙ্গে সঙ্গে accept করে (সম্ভাবনা ১/২)। 1 হলে আবার মুদ্রা: 10 শাখা accept (১/৪), 11 শাখা reject (১/৪)। গ্রহণের সম্ভাবনা ১/২ + ১/৪ = ৩/৪. NTM-এর নিয়মে এই input গৃহীত, কারণ একটি গ্রহণকারী শাখা আছে; probabilistic নিয়মে প্রশ্নটি হলো ৩/৪ যথেষ্ট কি না।

২ · ভুলের রকম আর শ্রেণির সংজ্ঞা — RP, coRP, BPP, ZPP, PP

একটি randomized algorithm দুইভাবে “অনিশ্চিত” হতে পারে: উত্তরে, অথবা সময়ে। Monte Carlo algorithm-এর সময় নির্দিষ্ট, কিন্তু উত্তর ছোট সম্ভাবনায় ভুল হতে পারে। Las Vegas algorithm-এর উত্তর সবসময় ঠিক, শুধু সময় এলোমেলো। চেনা উদাহরণ randomized quicksort: যেকোনো input-এ ফল সাজানো তালিকা, আর প্রত্যাশিত সময় O(n log n) (DSA কোর্সের পর্ব ২২)। Monte Carlo-র ভুল আবার দুই রকম: one-sided error, যেখানে একটি উত্তর সবসময় সঠিক; আর two-sided error, যেখানে দুই উত্তরই ভুল হতে পারে।

নিচের সব সংজ্ঞায় M একটি polynomial সময়ের probabilistic Turing machine (প্রতিটি শাখা nk ধাপে থামে), যদি না অন্য কিছু বলা হয়।

সংজ্ঞা ২.১ (পাঁচটি randomized শ্রেণি)

RP: A ∈ RP, যদি এমন M থাকে যে w ∈ A হলে Pr[M accepts w] ≥ 1/2, আর w ∉ A হলে Pr[M accepts w] = 0.

coRP = {A : A-র complement Ā ∈ RP}. অর্থাৎ w ∈ A হলে M সবসময় accept করে, আর w ∉ A হলে অন্তত 1/2 সম্ভাবনায় reject.

BPP: A ∈ BPP, যদি এমন M থাকে যে প্রতিটি w-এ ভুলের সম্ভাবনা ≤ 1/3: w ∈ A হলে Pr[accept] ≥ 2/3, আর w ∉ A হলে Pr[accept] ≤ 1/3.

ZPP: A ∈ ZPP, যদি এমন probabilistic M থাকে, যা প্রতিটি শাখায় সঠিক উত্তর দিয়ে থামে, আর প্রতিটি w-এ তার প্রত্যাশিত সময় |w|-এর polynomial.

PP: A ∈ PP, যদি এমন M থাকে যে w ∈ A ⇔ Pr[M accepts w] > 1/2.

শ্রেণিw ∈ A হলে Pr[accept]w ∉ A হলে Pr[accept]ধরন
P10এলোমেলোতা নেই
RP≥ 1/20Monte Carlo, one-sided: “হ্যাঁ” সবসময় ঠিক
coRP1≤ 1/2Monte Carlo, one-sided: “না” সবসময় ঠিক
BPP≥ 2/3≤ 1/3Monte Carlo, two-sided
ZPP10Las Vegas: শুধু সময় এলোমেলো
PP> 1/2≤ 1/2ব্যবধান অতি ক্ষুদ্র হতে পারে

সারণিটি পড়ার একটি সহজ উপায়: RP-র যন্ত্র “হ্যাঁ” বললে সেটি একটি নিশ্চিত প্রমাণ, যেমন মিষ্টির হাঁড়িতে একটি নষ্ট রসগোল্লা পাওয়া। “না” বললে হয়তো খারাপটি চোখ এড়িয়ে গেছে। BPP-র যন্ত্রের কোনো উত্তরই নিশ্চিত নয়, কিন্তু প্রতিটি উত্তর অন্তত 2/3 সম্ভাবনায় ঠিক। একটি সূক্ষ্ম বিষয়: সীমাগুলো প্রতিটি input-এর জন্য খাটে, সম্ভাবনা শুধু যন্ত্রের মুদ্রার ওপর। “গড় input-এ ভালো” এখানে যথেষ্ট নয়; input সবচেয়ে খারাপটি হলেও সীমা মানতে হবে।

ধ্রুবক নিয়ে সতর্কতা: RP-র 1/2 আর BPP-র 1/3 প্রচলিত পছন্দ মাত্র। পরের অংশের amplification দেখাবে, RP-তে 1/2-এর জায়গায় যেকোনো ধ্রুবক > 0 আর BPP-তে 1/3-এর জায়গায় 1/2-এর চেয়ে ছোট যেকোনো ধ্রুবক নিলেও একই শ্রেণি পাওয়া যায়। কিন্তু PP-তে তা খাটে না, কারণ সেখানে 1/2 থেকে দূরত্ব 2−n-এর মতো ক্ষুদ্র হতে পারে।

৩ · Primality — Fermat-এর ফাঁদ আর Miller–Rabin

প্রথম বড় উদাহরণ মৌলিকতা। COMPOSITES = {⟨n⟩ : n একটি যৌগিক স্বাভাবিক সংখ্যা}, আর PRIMES তার complement (n ≥ 2-এর মধ্যে)। Input-এর দৈর্ঘ্য n-এর bit-সংখ্যা, প্রায় log2 n; তাই √n পর্যন্ত ভাগ করে দেখা exponential (পর্ব ৫৭)। সংখ্যাতত্ত্বের দিকটি, অর্থাৎ Fermat-এর ছোট উপপাদ্য আর Miller–Rabin-এর প্রমাণ, ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২৫-এ বিস্তারিত আছে। এখানে প্রশ্নটি complexity-র: কোন শ্রেণি, আর কেন।

Fermat primality test: একটি base a নিয়ে an−1 mod n হিসাব করা; 1 না হলে n নিশ্চিত যৌগিক। সমস্যা হলো Carmichael number: এমন যৌগিক n, যা প্রতিটি সহমৌলিক base-এ পরীক্ষায় পাস করে। এদের জন্য “বেশিরভাগ base সাক্ষী” কথাটি মিথ্যা, তাই Fermat-এর পরীক্ষা RP-র সংজ্ঞা মানে না। Miller–Rabin test একটি বাড়তি তথ্য কাজে লাগায়: n মৌলিক হলে mod n-এ 1-এর বর্গমূল শুধু ±1. n − 1 = 2s · d (d বিজোড়) লিখে ad থেকে বারবার বর্গ করা হয়; পথে ±1 ছাড়া অন্য কোনো বর্গমূল পেলে n যৌগিক।

নিচের stepper সবচেয়ে ছোট Carmichael number 561 = 3 · 11 · 17-এ base a = 2 দিয়ে একটি round চালায়।

1n − 1 = 2^s · d লেখা2x ← a^d mod n3x = 1 বা n − 1 → পাস4s − 1 বার: x ← x² mod n5  x = n − 1 → পাস6নইলে → COMPOSITE
n = 561, a = 2, 560 = 2⁴ · 35
ঘাত
x mod 561
সিদ্ধান্ত
  1. Fermat আগে. 2560 mod 561 = 1, তাই Fermat-এর পরীক্ষা 561-কে “সম্ভবত মৌলিক” বলে। 561 Carmichael, তাই 2-এর জায়গায় যেকোনো সহমৌলিক base নিলেও একই ফল।
  2. ভাঙা আর শুরু. 560 = 24 · 35, তাই s = 4, d = 35. x = 235 mod 561 = 263. এটি 1-ও নয়, 560-ও নয়, তাই বর্গ করা চলবে।
  3. প্রথম বর্গ. 2632 = 69,169 ≡ 166 (mod 561). এটি 270 mod 561. এখনো 560 আসেনি।
  4. দ্বিতীয় বর্গ. 1662 = 27,556 ≡ 67 (mod 561), অর্থাৎ 2140 ≡ 67. এখনো 560 আসেনি।
  5. তৃতীয় বর্গ. 672 = 4,489 = 8 · 561 + 1 ≡ 1. অর্থাৎ 67 হলো 1-এর একটি বর্গমূল, যা 1-ও নয়, 560-ও নয়। মৌলিক মডুলাসে এমন সংখ্যা থাকতে পারে না, তাই 561 নিশ্চিত যৌগিক; 2 একটি সাক্ষী (witness).
  6. বাড়তি পাওনা. 672 − 1 = (67 − 1)(67 + 1) ≡ 0, কিন্তু কোনো উৎপাদক একা 0 নয়। তাই gcd(66, 561) = 33 আর gcd(68, 561) = 17 উৎপাদক দেয়: 33 · 17 = 561.

এবার সব base একসঙ্গে গোনা যাক। নিচের ব্লক কয়েকটি Carmichael number-এ (আর তুলনার জন্য একটি সাধারণ যৌগিক 9991 আর একটি মৌলিক 7919-এ) 1 থেকে n − 1 পর্যন্ত প্রতিটি base-এ Fermat আর একটি Miller–Rabin round চালিয়ে দেখে কয়টি base “মিথ্যা বলে”, অর্থাৎ যৌগিক সংখ্যাকে পাস করায়।

# Fermat test vs one Miller-Rabin round: how many bases a lie?
from math import gcd
def fermat_liar(n, a):              # a^(n-1) = 1 (mod n), though n is composite
    return pow(a, n - 1, n) == 1
def mr_liar(n, a):                  # a passes one Miller-Rabin round
    d, s = n - 1, 0
    while d % 2 == 0: d //= 2; s += 1
    x = pow(a, d, n)
    if x in (1, n - 1): return True
    for _ in range(s - 1):
        x = x * x % n
        if x == n - 1: return True
    return False                    # a is a witness: n surely composite
print("    n   factors      Fermat liars   MR liars  (out of n-1 bases)")
for n, f in ((561, "3*11*17"), (1105, "5*13*17"), (1729, "7*13*19"),
             (2821, "7*13*31"), (8911, "7*19*67"), (9991, "97*103")):
    fl = sum(fermat_liar(n, a) for a in range(1, n))
    ml = sum(mr_liar(n, a) for a in range(1, n))
    print(f"{n:5}   {f:10} {fl:6} = {fl/(n-1):5.1%} {ml:6} = {ml/(n-1):5.1%}")
p = 7919                            # a prime: no base can be a witness
print("prime 7919: MR liars =", sum(mr_liar(p, a) for a in range(1, p)), "of", p - 1)
print("561, base 2: Fermat says", "pass" if fermat_liar(561, 2) else "fail",
      "| MR says", "pass" if mr_liar(561, 2) else "COMPOSITE")

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

    n   factors      Fermat liars   MR liars  (out of n-1 bases)
  561   3*11*17       320 = 57.1%     10 =  1.8%
 1105   5*13*17       768 = 69.6%     30 =  2.7%
 1729   7*13*19      1296 = 75.0%    162 =  9.4%
 2821   7*13*31      2160 = 76.6%    270 =  9.6%
 8911   7*19*67      7128 = 80.0%   1782 = 20.0%
 9991   97*103         36 =  0.4%     18 =  0.2%
prime 7919: MR liars = 7918 of 7918
561, base 2: Fermat says pass | MR says COMPOSITE

Carmichael সংখ্যাগুলোতে Fermat-এর মিথ্যাবাদী base ৫৭ থেকে ৮০ শতাংশ; 561-এ ঠিক ৩২০টি, যা 561-এর সঙ্গে সহমৌলিক base-এর সংখ্যা। এক round Miller–Rabin-এ মিথ্যাবাদী অনেক কম, আর সবচেয়ে খারাপ সারিতেও (8911) ঠিক ২০ শতাংশ, যা প্রমাণিত সীমা ১/৪-এর নিচে। সাধারণ যৌগিক 9991-এ Fermat-ও ভালো কাজ করে; সমস্যা শুধু Carmichael-এর মতো সংখ্যায়। মৌলিক 7919-এ প্রতিটি base পাস করে: Miller–Rabin কখনো মৌলিক সংখ্যাকে যৌগিক বলে না। শেষ লাইন stepper-এর ফল মেলায়।

উপপাদ্য ৩.১

COMPOSITES ∈ RP, সমতুল্যভাবে PRIMES ∈ coRP.

প্রমাণের রূপরেখা।

  1. যন্ত্র M = “input n-এর ওপর: n জোড় আর n > 2 হলে accept. নইলে {1, …, n − 1} থেকে এলোমেলো a নিয়ে একটি Miller–Rabin round চালানো; সাক্ষী পেলে accept, নইলে reject.” এলোমেলো a বাছতে O(log n) মুদ্রা লাগে (n-এর সীমার নিচে না আসা পর্যন্ত আবার চেষ্টা, যা একটি ছোট খুঁটিনাটি)। — polynomial সময়: modular exponentiation
  2. n মৌলিক হলে কোনো a সাক্ষী নয়, কারণ মৌলিক মডুলাসে 1-এর বর্গমূল শুধু ±1, আর Fermat অনুসারে an−1 ≡ 1. তাই Pr[accept] = 0. — “হ্যাঁ, যৌগিক” কখনো ভুল নয়
  3. n বিজোড় যৌগিক হলে মিথ্যাবাদী base বড়জোর (n − 1)/4টি (Monier আর Rabin, ১৯৮০; প্রমাণ এখানে বাদ, পাওয়া যাবে Rabin-এর ১৯৮০ সালের প্রবন্ধে; ফলটির ব্যবহার ডিসক্রিট ম্যাথমেটিক্সের পর্ব ২৫-এ)। তাই Pr[accept] ≥ 3/4 ≥ 1/2. ∎

সত্যিকারের run (ডেস্কটপ, uv প্রকল্পে sympy 1.14.0, BSD licence, Python 3.12.13). নিজের লেখা Miller–Rabin (ওপরের round, এলোমেলো base, seed 69) ১০ লাখের নিচের প্রতিটি সংখ্যায় চালিয়ে sympy-র isprime-এর সঙ্গে মেলানো হয়েছে। sympy-তে কোনো usage-reporting বা telemetry নেই; installed package-এর code-এ শুধু দুটি ঐচ্ছিক function-এ network ব্যবহার আছে (একটি অনলাইন factor-ডাটাবেস খোঁজা, যা isprime ডাকে না):

~/bazarghar-toc$ uv add sympy
 + mpmath==1.3.0
 + sympy==1.14.0
~/bazarghar-toc$ uv run python check_mr.py
python 3.12.13 | sympy 1.14.0
n < 1,000,000: primes = 78498
Miller-Rabin, 1 round : disagreements with sympy = 92 | primes called composite = 0
Miller-Rabin, 20 rounds: disagreements with sympy = 0
Fermat base 2 fooled by 245 composites; first: [341, 561, 645, 1105, 1387]

এক round-এ ৯২টি অমিল, আর প্রতিটিই একটি যৌগিক সংখ্যা, যাকে এলোমেলো base ভুল করে পাস করিয়েছে; একটিও মৌলিক সংখ্যা “যৌগিক” হয়নি, ঠিক one-sided error-এর প্রতিশ্রুতি অনুযায়ী। ২০ round-এ অমিল শূন্য। ভুলের সীমা 4−20 = 2−40, তবে মনে রাখুন, শূন্য অমিল একটি পরীক্ষা মাত্র, প্রমাণ নয়। শেষ লাইনে base 2-এর Fermat পরীক্ষা ২৪৫টি যৌগিক সংখ্যায় ঠকেছে, যার প্রথমটি 341 = 11 · 31.

Randomized primality test-এর গল্প derandomization-এর সবচেয়ে সুন্দর উদাহরণ। Solovay আর Strassen ১৯৭৭ সালে একটি randomized পরীক্ষা দেন; Gary Miller ১৯৭৬ সালে একটি deterministic পরীক্ষা দেন, যার সঠিকতা একটি অপ্রমাণিত অনুমানের (extended Riemann hypothesis) ওপর নির্ভর করে; Michael Rabin ১৯৮০ সালে সেটিকে শর্তহীন randomized পরীক্ষায় রূপ দেন। Adleman আর Huang ১৯৯০-এর দশকের শুরুতে দেখান PRIMES ∈ RP-ও, তাই PRIMES ∈ ZPP বলে পরিচিত। শেষে ২০০২ সালে Agrawal, Kayal আর Saxena দেখান PRIMES ∈ P (পর্ব ৫৭)। তবু বাস্তবে Miller–Rabin-ই চলে, কারণ AKS অনেক ধীর।

৪ · Amplification — বারবার চালিয়ে ভুল কমানো

1/2 বা 1/3 ভুল বাস্তবে অনেক। কিন্তু মুদ্রা প্রতিবার নতুন করে ছোড়া হয়, তাই একই যন্ত্র স্বাধীনভাবে কয়েকবার চালানো যায়। Amplification মানে এভাবে ভুল ইচ্ছেমতো ছোট করা। One-sided আর two-sided ভুলে নিয়ম আলাদা।

উপপাদ্য ৪.১ (RP-তে amplification)

A ∈ RP হলে যেকোনো polynomial q(n)-এর জন্য এমন polynomial সময়ের probabilistic যন্ত্র M′ আছে, যে w ∈ A হলে Pr[M′ accepts w] ≥ 1 − 2−q(n), আর w ∉ A হলে Pr[M′ accepts w] = 0.

প্রমাণ। M′ = “input w-এর ওপর: RP-র যন্ত্র M-কে q(n) বার স্বাধীন মুদ্রা দিয়ে চালানো; কোনো একবার accept করলে accept, নইলে reject.”

  1. w ∉ A: M কখনো accept করে না, তাই M′-ও না। — one-sided
  2. w ∈ A: M′ ভুল করে শুধু তখন, যখন q(n)টি run-এর প্রতিটি reject করে। প্রতিটির সম্ভাবনা ≤ 1/2, আর run-গুলো স্বাধীন, তাই মোট ≤ (1/2)q(n). — স্বাধীন ঘটনার গুণফল
  3. সময়: q(n) গুণ polynomial = polynomial. ∎

এই “যেকোনো একবার হ্যাঁ হলেই হ্যাঁ” নিয়ম BPP-তে চলে না: w ∉ A হলেও প্রতিটি run 1/3 পর্যন্ত সম্ভাবনায় accept করতে পারে, তাই বেশি run মানে ভুল “হ্যাঁ”-এর সম্ভাবনা বাড়া। BPP-তে নিয়ম হলো সংখ্যাগরিষ্ঠ ভোট। তার বিশ্লেষণে লাগে Chernoff bound-জাতীয় একটি সীমা (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৪১)। এখানে একটি সুবিধাজনক রূপ, যা Hoeffding-এর অসমতা (১৯৬৩) নামে পরিচিত:

X1, …, Xk স্বাধীন, প্রতিটি 0 বা 1, আর E[Xi] ≥ 1/2 + δ হলে   Pr[X1 + ⋯ + Xk ≤ k/2] ≤ e−2δ2k

এখানে Xi = 1 মানে i-তম run সঠিক, আর δ হলো সঠিকতার সম্ভাবনা 1/2-এর চেয়ে কত বেশি। বইভেদে Chernoff সীমার ধ্রুবক আলাদা দেখা যায়; মূল কথা একই: ভুল k-এর সাথে exponential হারে কমে।

উপপাদ্য ৪.২ (BPP-তে amplification)

A ∈ BPP হলে যেকোনো polynomial q(n)-এর জন্য এমন polynomial সময়ের probabilistic যন্ত্র M′ আছে, যার প্রতিটি input-এ ভুলের সম্ভাবনা ≤ 2−q(n).

প্রমাণ। M′ = “M-কে k = 18 q(n) বার (বিজোড় করতে দরকারে একবার বেশি) স্বাধীনভাবে চালিয়ে যে উত্তর বেশিবার এসেছে সেটি দেওয়া।”

  1. যেকোনো w নিন, আর Xi = 1 যদি i-তম run সঠিক উত্তর দেয়। BPP-র সংজ্ঞায় E[Xi] ≥ 2/3 = 1/2 + 1/6, আর Xi-গুলো স্বাধীন। — প্রতিবার নতুন মুদ্রা
  2. M′ ভুল করে শুধু তখন, যখন সঠিক run বড়জোর k/2টি। Hoeffding থেকে সেই সম্ভাবনা ≤ e−2(1/6)2k = e−k/18. — δ = 1/6
  3. k = 18 q(n) হলে ভুল ≤ e−q(n) < 2−q(n), কারণ e > 2. — সরল তুলনা
  4. সময়: k গুণ polynomial, তাই polynomial. ∎

একই যুক্তি দেখায়, সঠিকতার সম্ভাবনা 1/2 + 1/p(n) হলেও (p একটি polynomial) amplification চলে, কারণ তখন k ≈ p(n)2 · q(n) run যথেষ্ট, যা এখনো polynomial. নিচের stepper k বাড়ার সঙ্গে আসল ভুল (binomial যোগফল থেকে হুবহু হিসাব) আর Hoeffding সীমা পাশাপাশি দেখায়, যেখানে প্রতিটি run-এর ভুল ঠিক 1/3.

1A-কে k বার স্বাধীনভাবে চালানো2প্রতিটি উত্তর একটি ভোট3বেশি ভোট যে উত্তরে, সেটিই ফল4ভুল ⇔ অন্তত (k + 1)/2টি run ভুল
প্রতিটি run: ঠিক ২/৩, ভুল ১/৩
k
আসল ভুল
e^(−k/18)
  1. k = 1. একবার চালানো মানে মূল যন্ত্র: ভুল ঠিক 1/3. Hoeffding সীমা 0.946 প্রায় অর্থহীন; ছোট k-তে সীমাটি ঢিলে।
  2. k = 3. ভোট ভুল হয় যদি অন্তত দুটি run ভুল: 3 · (1/3)2 · (2/3) + (1/3)3 = 6/27 + 1/27 = 7/27 ≈ 0.259.
  3. k = 5. অন্তত তিনটি ভুল লাগে; যোগফল ≈ 0.210. প্রতি দুটি বাড়তি run-এ ভুল কমছে, কিন্তু শুরুতে ধীরে।
  4. k = 21. ভুল ≈ 0.0557, সীমা ≈ 0.311. আসল মান সীমার অনেক নিচে; সীমা শুধু নিশ্চয়তা দেয়, হুবহু মান নয়।
  5. k = 101. ভুল ≈ 2.7 × 10−4, সীমা ≈ 3.7 × 10−3. এখন দুটিই দ্রুত পড়ছে।
  6. k = 401. ভুল ≈ 3.1 × 10−12. k চারগুণ করায় ভুল কোটি গুণের বেশি কমেছে: এটিই exponential পতন। সময়ের দাম কিন্তু শুধু ৪০১ গুণ, একটি ধ্রুবক।

সংখ্যাগুলো সত্যিকারের পরীক্ষায় মেলে কি না, দেখা যাক। নিচের ব্লকে একটি খেলনা “BPP algorithm” আছে, যা প্রতিবার ঠিক 1/3 সম্ভাবনায় ভুল করে (Python-এর random, নির্দিষ্ট seed). প্রতিটি k-এর জন্য ২০,০০০ বার সংখ্যাগরিষ্ঠ ভোট নিয়ে মাপা ভুল, হুবহু ভুল আর সীমা ছাপা হয়।

# Amplification of a BPP-style algorithm: error 1/3 per run, majority of k runs.
import random
from math import comb, exp
rng = random.Random(69)
def one_run():                      # correct with prob. 2/3, wrong with prob. 1/3
    return rng.random() >= 1/3
def majority(k):                    # run k times (k odd), take the majority answer
    return sum(one_run() for _ in range(k)) > k // 2
def exact_error(k):                 # P[at least (k+1)/2 of k runs are wrong]
    return sum(comb(k, i) * (1/3)**i * (2/3)**(k - i) for i in range(k // 2 + 1, k + 1))
T = 20000                           # experiments per row
print("  k   measured   exact      Hoeffding bound e^(-k/18)")
for k in (1, 5, 11, 21, 41, 101):
    wrong = sum(not majority(k) for _ in range(T))
    print(f"{k:3}   {wrong/T:.4f}    {exact_error(k):.6f}   {min(1, exp(-k/18)):.6f}")
for k in (201, 401):                # too rare to measure: exact values only
    print(f"{k:3}   -          {exact_error(k):.2e}   {exp(-k/18):.2e}")

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

  k   measured   exact      Hoeffding bound e^(-k/18)
  1   0.3350    0.333333   0.945959
  5   0.2135    0.209877   0.757465
 11   0.1238    0.122085   0.542747
 21   0.0544    0.055723   0.311403
 41   0.0136    0.013515   0.102512
101   0.0003    0.000272   0.003657
201   -          5.53e-07   1.41e-05
401   -          3.06e-12   2.11e-10

মাপা কলাম হুবহু কলামের খুব কাছে, যেমন k = 21-এ 0.0544 বনাম 0.0557; পার্থক্যটুকু ২০,০০০ নমুনার স্বাভাবিক ওঠানামা। প্রতিটি সারিতে আসল ভুল সীমার নিচে, তাই উপপাদ্য ৪.২-এর হিসাব নিরাপদ দিকে আছে। k = 201 আর 401-এ ভুল এত কম যে এই আকারের পরীক্ষায় একটি ভুলও দেখার আশা নেই; সেখানে শুধু হিসাব ছাপা হয়েছে। এটিও একটি শিক্ষা: খুব ছোট ভুলের সম্ভাবনা পরীক্ষা চালিয়ে “দেখা” যায় না, প্রমাণ করতে হয়।

PP-তে এই কৌশল ব্যর্থ কেন, তা এখন স্পষ্ট। PP শুধু চায় সঠিকতার সম্ভাবনা > 1/2; ব্যবধান δ হতে পারে 2−n. তখন e−2δ2k-কে ছোট করতে k-কে প্রায় 4n-এর ক্রমে নিতে হয়, যা exponential. তাই PP-কে “দক্ষভাবে সমাধানযোগ্য” ধরা হয় না, আর BPP-কে ধরা হয়।

৫ · যাচাইয়ের তিনটি কৌশল — Freivalds, Schwartz–Zippel আর fingerprint

অনেক randomized algorithm-এর মূল ছক একই: “কোনো একটি বস্তু শূন্য কি না” প্রশ্নকে একটি এলোমেলো বিন্দুতে মান হিসাব করার প্রশ্নে বদলানো। বস্তুটি শূন্য হলে মান সবসময় শূন্য; অশূন্য হলে খুব কম বিন্দুতে শূন্য। এটি সরাসরি one-sided error দেয়।

৫.১ Freivalds — matrix-গুণফল যাচাই

প্রশ্ন: n × n integer matrix A, B, C দেওয়া; AB = C কি না? সরাসরি গুণ করলে স্কুলের পদ্ধতিতে n3 গুণ, আর জানা সবচেয়ে দ্রুত পদ্ধতিগুলোও n2.37-এর মতো। Freivalds' algorithm একটি এলোমেলো 0/1 vector r নিয়ে A(Br) আর Cr মেলায়: তিনটি matrix-vector গুণ, 3n2 গুণন। AB = C হলে দুটি সবসময় সমান। AB ≠ C হলে D = AB − C অশূন্য, আর Dr = 0 হওয়ার সম্ভাবনা ≤ 1/2 (প্রমাণ ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৪৩-এ)। তাই {⟨A, B, C⟩ : AB ≠ C} RP-তে, O(n2) সময়ে, এখানে n মানে matrix-এর মাপ।

নিচের stepper একটি 2 × 2 উদাহরণে চারটি সম্ভাব্য r-ই দেখে। A = [1 2; 3 4], B = [5 6; 7 8], তাই আসল AB = [19 22; 43 50]. দাবি করা C = [19 22; 43 51], শুধু শেষ ঘরে 1 বেশি।

1r ← এলোমেলো 0/1 vector2y ← B · r3z ← A · y4w ← C · r5z ≠ w → “C ভুল” (নিশ্চিত)6z = w → “সম্ভবত ঠিক”
A = [1 2; 3 4], B = [5 6; 7 8], C = [19 22; 43 51]
r
y = B·r
z = A·y
w = C·r
  1. প্রস্তুতি. D = AB − C = [0 0; 0 −1]: ভুল শুধু দ্বিতীয় সারির দ্বিতীয় ঘরে। Dr = (0, −r2), তাই ভুল ধরা পড়ে ঠিক তখন, যখন r2 = 1.
  2. r = (0, 0). সবকিছু শূন্য, z = w = (0, 0). পরীক্ষা ঠকে গেল; শূন্য vector কোনো তথ্য দেয় না।
  3. r = (1, 0). y = (5, 7), z = (19, 43), আর w = C-এর প্রথম কলাম = (19, 43). আবার সমান: ভুল ঘরটি দ্বিতীয় কলামে, r তাকে “দেখেনি”।
  4. r = (0, 1). y = (6, 8), z = (22, 50), কিন্তু w = (22, 51). অমিল: C নিশ্চিত ভুল। এই উত্তর কখনো ভুল হয় না।
  5. r = (1, 1). y = (11, 15), z = (41, 93), w = (41, 94). আবার ধরা পড়ল।
  6. হিসাব. চারটি সমান সম্ভাব্য r-এর দুটিতে ঠকা: সম্ভাবনা ঠিক 1/2. এই উদাহরণে সীমা ১/২ হুবহু অর্জিত। ২০ round চালালে ঠকার সম্ভাবনা ≤ 2−20.

বড় matrix-এ সংখ্যাটি মাপা যাক। নিচের ব্লক 20 × 20 এলোমেলো integer matrix-এ সঠিক C আর কয়েকটি ভুল C-তে বহুবার একটি round চালিয়ে গোনে কতবার পরীক্ষা ঠকে।

# Freivalds: check A*B == C with a random 0/1 vector r, in O(n^2) per round.
import random
rng = random.Random(69)
def matvec(M, v): return [sum(x * y for x, y in zip(row, v)) for row in M]
def matmul(A, B):                   # the slow O(n^3) way, only to build test data
    Bt = list(zip(*B)); return [[sum(x * y for x, y in zip(r, c)) for c in Bt] for r in A]
def freivalds_round(A, B, C):       # True = "looks equal", False = "surely unequal"
    r = [rng.randrange(2) for _ in range(len(A))]
    return matvec(A, matvec(B, r)) == matvec(C, r)
n = 20
A = [[rng.randrange(-9, 10) for _ in range(n)] for _ in range(n)]
B = [[rng.randrange(-9, 10) for _ in range(n)] for _ in range(n)]
C = matmul(A, B)
print("correct C: 'equal' in", sum(freivalds_round(A, B, C) for _ in range(500)),
      "of 500 rounds")
for i, j, delta in ((7, 3, 1), (0, 0, -5)):   # one wrong entry
    W = [row[:] for row in C]; W[i][j] += delta
    fooled = sum(freivalds_round(A, B, W) for _ in range(2000))
    print(f"C[{i}][{j}] off by {delta:2}: fooled in {fooled} of 2000 rounds = {fooled/2000:.3f}")
W = [row[:] for row in C]
for i in range(n): W[i][i] += 1                   # n wrong entries
fooled = sum(freivalds_round(A, B, W) for _ in range(2000))
print(f"diagonal all off by 1: fooled in {fooled} of 2000 rounds")
print("10 rounds on the first wrong C: P[fooled] <= 2^-10 =", 2 ** -10)

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

correct C: 'equal' in 500 of 500 rounds
C[7][3] off by  1: fooled in 999 of 2000 rounds = 0.499
C[0][0] off by -5: fooled in 990 of 2000 rounds = 0.495
diagonal all off by 1: fooled in 0 of 2000 rounds
10 rounds on the first wrong C: P[fooled] <= 2^-10 = 0.0009765625

সঠিক C প্রতিবার “সমান” পায়: one-sided ভুলের প্রতিশ্রুতি। একটি ঘরে ভুল থাকলে পরীক্ষা প্রায় অর্ধেকবার ঠকে (0.499 আর 0.495), কারণ ভুলটি ধরা পড়ে শুধু যখন সেই কলামের r-এর মান 1; সীমা ১/২ এখানে প্রায় হুবহু। কর্ণের ২০টি ঘরেই ভুল থাকলে D = C − AB একক matrix, Dr = r, যা শূন্য শুধু r = 0 হলে, সম্ভাবনা 2−20; তাই ২,০০০ বারে একবারও ঠকেনি। বেশি ভুল মানে সহজে ধরা পড়া। শেষ লাইন: ১০টি স্বাধীন round-এ ঠকার সীমা 2−10, প্রায় হাজারে এক।

৫.২ Schwartz–Zippel আর polynomial-এর অভেদ

Polynomial identity testing: দুটি রাশি, যেমন (x + y)(x − y) আর x2 − y2, আসলে একই polynomial কি না। গুণ করে খুলে ফেললে পদ exponential হারে বাড়তে পারে। Schwartz–Zippel lemma বলে: একটি field-এর ওপর মোট degree d-এর অশূন্য polynomial-এ সসীম সেট S থেকে স্বাধীন এলোমেলো মান বসালে শূন্য হওয়ার সম্ভাবনা ≤ d/|S|. তাই “P − Q শূন্য polynomial কি না” প্রশ্ন coRP-তে: সমান হলে মান সবসময় মেলে, অসমান হলে |S| ≥ 2d নিলে অন্তত 1/2 সম্ভাবনায় অমিল। Lemma-টি DeMillo–Lipton (১৯৭৮), Zippel (১৯৭৯) আর Schwartz (১৯৮০) আলাদাভাবে প্রকাশ করেন বলে পরিচিত। আশ্চর্যের বিষয়: এই সমস্যার কোনো polynomial সময়ের deterministic algorithm আজও জানা নেই।

৫.৩ বাজারঘরের fingerprint

অংশ ১-এর গুদামের প্রশ্নে ফিরি। ঢাকার তালিকা a0, …, an−1-কে একটি polynomial হিসেবে দেখা হয়: Fa(x) = a0 + a1x + ⋯ + an−1xn−1, একটি বড় মৌলিক q-এর mod-এ। ঢাকা এলোমেলো r ∈ {0, …, q − 1} বেছে (r, Fa(r)) পাঠায়; চট্টগ্রাম নিজের Fb(r) মিলিয়ে দেখে। তালিকা আলাদা হলে Fa − Fb একটি অশূন্য polynomial, degree ≤ n − 1, তাই এক-চলকের Schwartz–Zippel থেকে ঠকার সম্ভাবনা ≤ (n − 1)/q. এই fingerprinting-এর ধারণা hash-এরও মূলে (DSA কোর্সের পর্ব ৩২)। নিচের ব্লক প্রথমে একটি ছোট field-এ সীমাটি হুবহু ছুঁয়ে দেখায়, তারপর বাস্তব আকারে চালায়।

# Bazarghar: are two warehouse order databases identical? Send a fingerprint only.
import random
rng = random.Random(69)
def fingerprint(orders, r, q):      # F(r) = sum of orders[i] * r^i  (mod q), Horner
    h = 0
    for x in reversed(orders): h = (h * r + x) % q
    return h
# 1) Small field q = 101: D(x) = (x-1)(x-2)...(x-10) is nonzero but has 10 roots.
q, D = 101, [1]
for i in range(1, 11):              # multiply D by (x - i), coefficients mod q
    D = [((D[k - 1] if k else 0) - i * (D[k] if k < len(D) else 0)) % q
         for k in range(len(D) + 1)]
zeros = [r for r in range(q) if fingerprint(D, r, q) == 0]
print("q = 101, degree 10: D(r) = 0 for r in", zeros)
print(f"P[miss] = {len(zeros)}/{q} = {len(zeros)/q:.3f}  (Schwartz-Zippel bound d/|S| = 10/101)")
# 2) Realistic: n orders (IDs below 10000), prime q = 2^31 - 1.
n, q = 10000, 2**31 - 1
dhaka = [rng.randrange(10000) for _ in range(n)]
ctg = dhaka[:]; ctg[4321] += 1      # one order differs
same = dhaka[:]
caught = equal_ok = 0
for _ in range(30):
    r = rng.randrange(q)            # Dhaka picks r and sends (r, F(r))
    fd = fingerprint(dhaka, r, q)
    caught += fd != fingerprint(ctg, r, q)
    equal_ok += fd == fingerprint(same, r, q)
print(f"n = {n}: identical copies judged equal in {equal_ok}/30 trials")
print(f"one changed order caught in {caught}/30 trials; bound P[miss] <= {(n-1)/q:.1e}")
print("bits sent: about", 2 * 31, "instead of about", n * 14)

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

q = 101, degree 10: D(r) = 0 for r in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
P[miss] = 10/101 = 0.099  (Schwartz-Zippel bound d/|S| = 10/101)
n = 10000: identical copies judged equal in 30/30 trials
one changed order caught in 30/30 trials; bound P[miss] <= 4.7e-06
bits sent: about 62 instead of about 140000

প্রথম অংশে D(x) = (x − 1)(x − 2)⋯(x − 10) ইচ্ছা করে এমনভাবে বানানো, যাতে তার ঠিক ১০টি মূল থাকে। তাই q = 101-এ এলোমেলো r ঠিক 10/101 সম্ভাবনায় পার্থক্য ধরতে ব্যর্থ হয়: Schwartz–Zippel-এর সীমা এখানে হুবহু অর্জিত, এর চেয়ে ভালো সীমা সাধারণভাবে সম্ভব নয়। দ্বিতীয় অংশে ১০,০০০টি অর্ডারের তালিকা, একটিতে শুধু একটি অর্ডার আলাদা। একই কপি প্রতিবার “সমান”, আর আলাদা কপি ৩০ বারের ৩০ বারই ধরা পড়েছে; ঠকার সম্ভাবনার সীমা প্রায় 4.7 × 10−6. পাঠানো হয়েছে প্রায় ৬২ bit (r আর F(r)), পুরো তালিকার প্রায় ১,৪০,০০০ bit-এর বদলে।

একটি সতর্কতা: এখানে random ব্যবহার করা হয়েছে শুধু পরীক্ষা পুনরুৎপাদনযোগ্য রাখতে। প্রতিপক্ষ যদি ইচ্ছা করে দুটি আলাদা তালিকা বানাতে চায়, যাদের fingerprint মেলে, তাহলে r অনুমানযোগ্য হলে চলবে না; তখন অংশ ৭-এর CSPRNG লাগবে।

৬ · শ্রেণির মানচিত্র — P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE

এবার শ্রেণিগুলোর সম্পর্ক প্রমাণ করা যাক। সবচেয়ে সুন্দর ফলটি ZPP-কে RP আর coRP দিয়ে বর্ণনা করে।

উপপাদ্য ৬.১

ZPP = RP ∩ coRP.

প্রমাণ।

  1. ZPP ⊆ RP: ধরুন M সবসময় সঠিক, আর প্রতিটি input-এ প্রত্যাশিত সময় ≤ t(n), একটি polynomial. নতুন যন্ত্র M1: M-কে 2t(n) ধাপ চালানো; এর মধ্যে থামলে তার উত্তর দেওয়া, নইলে reject. Markov's inequality থেকে Pr[M-এর সময় > 2t(n)] ≤ 1/2. তাই w ∈ A হলে Pr[accept] ≥ 1/2, আর w ∉ A হলে M1 কখনো accept করে না। — সময় কেটে দেওয়া
  2. ZPP ⊆ coRP: একই যন্ত্র, শুধু সময় ফুরালে accept. তাহলে “না” উত্তরটি সবসময় ঠিক। — প্রতিসম যুক্তি
  3. RP ∩ coRP ⊆ ZPP: A-র জন্য RP-র যন্ত্র M1 (তার accept সবসময় ঠিক) আর Ā-র জন্য RP-র যন্ত্র M2 (তার accept মানে নিশ্চিত w ∉ A). নতুন যন্ত্র: বারবার M1 আর M2 চালানো; M1 accept করলে accept, M2 accept করলে reject. যে উত্তরই আসে, তা নিশ্চিত সঠিক। — দুই দিকের নিশ্চিত সাক্ষী
  4. প্রত্যাশিত সময়: প্রতিটি দফায় সঠিক দিকের যন্ত্র অন্তত 1/2 সম্ভাবনায় accept করে, তাই প্রত্যাশিত দফা ≤ 2, আর প্রত্যাশিত সময় ≤ 2 · (দুই যন্ত্রের সময়ের যোগফল), polynomial. ∎
উপপাদ্য ৬.২ (অন্তর্ভুক্তির শৃঙ্খল)

P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE, আর RP ⊆ NP, BPP = coBPP, NP ⊆ PP ⊆ PSPACE, BPP ⊆ PP.

প্রমাণ।

  1. P ⊆ ZPP: deterministic যন্ত্র কোনো মুদ্রা ছোড়ে না, সবসময় সঠিক। ZPP ⊆ RP উপপাদ্য ৬.১ থেকে। — সংজ্ঞা
  2. RP ⊆ BPP: RP-র যন্ত্র দুবার চালিয়ে যেকোনো একবার accept হলে accept: w ∈ A-তে ভুল ≤ 1/4 ≤ 1/3, w ∉ A-তে ভুল 0. — উপপাদ্য ৪.১
  3. RP ⊆ NP: w ∈ A হলে অন্তত একটি এলোমেলো string r-এ M(w, r) accept করে, আর সেই r একটি certificate; w ∉ A হলে কোনো r-এ নয়। Verifier হলো M(w, r) নিজে (পর্ব ৫৮)। একইভাবে coRP ⊆ coNP. — এলোমেলো string = certificate
  4. BPP = coBPP: যন্ত্রের accept আর reject অদলবদল করলে ভুলের সীমা একই থাকে, কারণ সংজ্ঞাটি দুই দিকে প্রতিসম। — two-sided ভুল প্রতিসম
  5. BPP ⊆ PSPACE: M যদি p(n) সময়ে চলে, তবে সে বড়জোর p(n)টি মুদ্রা ছোড়ে। Deterministic যন্ত্র সব r ∈ {0, 1}p(n) একটি counter-এ একে একে তৈরি করে, প্রতিটিতে M(w, r) চালায় (একই জায়গা মুছে আবার ব্যবহার করে), আর accept করা r গোনে p(n) + 1 bit-এর আরেকটি counter-এ। গোনা সংখ্যা 2p(n)-এর অর্ধেকের বেশি হলে accept. জায়গা O(p(n)), সময় exponential; পর্ব ৬৪-এর SAT-এর একই ছক। একই যুক্তিতে PP ⊆ PSPACE. ∎

NP ⊆ PP-র যুক্তিটিও ছোট। Verifier-এর certificate দৈর্ঘ্য m হলে যন্ত্রটি একটি এলোমেলো certificate নিয়ে verifier চালায়; সফল হলে accept, নইলে 1/2 − 2−(m+1) সম্ভাবনায় accept. কোনো সঠিক certificate থাকলে মোট সম্ভাবনা অন্তত 1/2 + 2−(2m+1), না থাকলে 1/2 − 2−(m+1). ব্যবধান অতি ক্ষুদ্র, কিন্তু PP-র সংজ্ঞায় তা-ই যথেষ্ট। একই কারণে PP NP-র চেয়ে অনেক “বড়” শ্রেণি বলে ধরা হয়।

Randomized শ্রেণির মানচিত্র

তীর মানে “⊆, প্রমাণিত”. ড্যাশ দেওয়া রেখা আর “?” মানে সম্পর্ক অজানা।

Map of randomized classes: P, ZPP, RP, coRP, BPP, NP, coNP, PP, PSPACE PSPACE PP NP BPP coNP RP coRP ZPP P ? ? P = BPP? অনুমান, অপ্রমাণিত ZPP = RP ∩ coRP
ছবি ৬৯.২ — প্রতিটি তীর একটি প্রমাণিত ⊆, কিন্তু কোনোটি কঠোর বলে প্রমাণিত নয়: P = ZPP = RP = BPP হলেও কোনো জানা ফলের বিরোধ হয় না, আর সেটাই অনুমান। BPP আর NP-র কোনোটি অন্যটির ভেতরে কি না, অজানা। PP আর PSPACE-এর মধ্যে আরও শ্রেণি আছে (পর্ব ৬৮-এর polynomial hierarchy), এখানে দেখানো হয়নি।

BPP আর NP প্রশ্নটি একটু খুঁটিয়ে দেখা যাক। BPP ⊆ NP জানা নেই, কারণ BPP-র যন্ত্রের একটি গ্রহণকারী r “হ্যাঁ”-এর প্রমাণ নয়: w ∉ A হলেও ১/৩ পর্যন্ত r accept করতে পারে। উল্টো দিকে NP ⊆ BPP হলে SAT-এর একটি দ্রুত randomized algorithm থাকত; বেশিরভাগ গবেষক তা অসম্ভব মনে করেন, কারণ জানা ফল অনুযায়ী তখন polynomial hierarchy ভেঙে পড়ত (পর্ব ৬৮)। আরও দুটি জানা ফল, পরের পর্বগুলোর সঙ্গে সংযোগ হিসেবে: Adleman ১৯৭৮ সালে RP ⊆ P/poly দেখান, আর Bennett ও Gill ১৯৮১ সালে একই যুক্তি BPP-তে খাটান, অর্থাৎ BPP ⊆ P/poly (পর্ব ৭০-এর circuit), আর Sipser, Gács আর Lautemann-এর ১৯৮৩ সালের কাজ থেকে BPP ⊆ Σ2p ∩ Π2p (পর্ব ৬৮)।

৭ · P = BPP? — derandomization আর বাস্তবের এলোমেলোতা

এলোমেলোতা কি সত্যিই polynomial সময়ে বাড়তি শক্তি দেয়? প্রমাণিত উত্তর নেই। কিন্তু গত কয়েক দশকে পাল্লা ভারী হয়েছে “না”-এর দিকে, অর্থাৎ P = BPP-এর দিকে। Derandomization মানে একটি randomized algorithm থেকে মুদ্রা সরিয়ে একই রকম দক্ষ deterministic algorithm পাওয়া।

  • সাফল্য: PRIMES বহু বছর শুধু coRP আর পরে ZPP-তে জানা ছিল; ২০০২ সালে P-তে এল। Undirected graph-এ দুটি vertex সংযুক্ত কি না, তার একটি সহজ randomized log-space পদ্ধতি (এলোমেলো হাঁটা) অনেক আগে থেকে জানা ছিল; Omer Reingold ২০০৫ সালের দিকে deterministic log-space algorithm দেন (পর্ব ৬৬)।
  • শর্তসাপেক্ষ ফল: Impagliazzo আর Wigderson ১৯৯৭ সালে দেখান বলে পরিচিত: যদি E = TIME(2O(n))-এর কোনো সমস্যার জন্য 2Ω(n) আকারের Boolean circuit লাগে, তাহলে P = BPP. অর্থাৎ যথেষ্ট কঠিন সমস্যা থাকলে সেই কঠিনতা থেকে এমন pseudorandom bit বানানো যায়, যা যেকোনো polynomial সময়ের যন্ত্রকে ঠকায়। এই ধারার নাম hardness vs randomness.
  • উল্টো দিকের বাধা: Kabanets আর Impagliazzo ২০০৩–০৪ সালে দেখান বলে পরিচিত, polynomial identity testing-কে derandomize করলে এমন circuit lower bound প্রমাণ হবে, যা এখনো কেউ প্রমাণ করতে পারেনি। তাই P = BPP প্রমাণ করা circuit lower bound-এর মতো কঠিন হতে পারে।

সংক্ষেপে: “P = BPP বলে বেশিরভাগ গবেষক মনে করেন, কিন্তু প্রমাণিত নয়।” মজার বৈপরীত্য হলো, P বনাম NP-তে বিশ্বাস “আলাদা”-র দিকে, আর P বনাম BPP-তে “সমান”-এর দিকে।

বাস্তবের প্রোগ্রামে মুদ্রা আসে একটি pseudorandom number generator থেকে: একটি নির্দিষ্ট সূত্র, যার পুরো ধারা seed থেকে নির্ধারিত। Python-এর random module ভেতরে Mersenne Twister ব্যবহার করে; তার documentation নিজেই সতর্ক করে যে এটি security বা cryptography-র কাজে একেবারে অনুপযুক্ত। আগের কয়েকশো আউটপুট দেখে ভেতরের অবস্থা পুনর্গঠন করা যায় বলে পরিচিত, তারপর ভবিষ্যতের প্রতিটি সংখ্যা জানা হয়ে যায়। OTP, কুপন-টোকেন বা fingerprint-এর r যদি প্রতিপক্ষের কাছ থেকে লুকাতে হয়, তাহলে CSPRNG লাগে, যেমন Python-এর secrets module. এই পর্বের ব্লকগুলোতে random নির্দিষ্ট seed-সহ ব্যবহার হয়েছে শুধু পরীক্ষা পুনরুৎপাদন করতে। তত্ত্বের probabilistic যন্ত্র ধরে নেয় সত্যিকারের ন্যায্য, স্বাধীন মুদ্রা; বাস্তবের pseudorandom ধারা সেই অনুমান কতটা পূরণ করে, সেটিই pseudorandom generator-এর তত্ত্ব (পর্ব ৭৬)। এলোমেলো algorithm-এর আরও উদাহরণ আর প্রোগ্রামিংয়ের দিক DSA কোর্সের পর্ব ৬১-এ আছে।

আরও গভীরে: BPP একটি “semantic” শ্রেণি: যন্ত্রটি প্রতিটি input-এ সীমা মানে কি না, তা যন্ত্রের লেখা দেখে বোঝা যায় না। এ কারণে BPP-র কোনো complete সমস্যা জানা নেই, আর BPP-র জন্য time hierarchy theorem-ও প্রমাণিত নয়। অন্যদিকে Toda-র ১৯৯১ সালের উপপাদ্য দেখায়, PP-র oracle পেলে পুরো polynomial hierarchy polynomial সময়ে নেমে আসে (PH ⊆ PPP). Quantum যন্ত্রের শ্রেণি BQP-তে BPP আছে, আর BQP-র সঙ্গে NP-র সম্পর্ক অজানা (পর্ব ৭৫)।

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

  • RP, BPP আর ZPP-র সংজ্ঞা দিন। RP: “হ্যাঁ”-তে ≥ 1/2, “না”-তে 0; BPP: দুই দিকে ভুল ≤ 1/3; ZPP: সবসময় সঠিক, প্রত্যাশিত polynomial সময়।
  • ZPP = RP ∩ coRP প্রমাণ করুন। একদিকে Markov দিয়ে সময় কাটা; অন্যদিকে দুই one-sided যন্ত্র পালাক্রমে, প্রত্যাশিত দফা ≤ 2.
  • BPP-তে ভুল 2−n-এ নামান। O(n) বার চালিয়ে সংখ্যাগরিষ্ঠ ভোট; Chernoff–Hoeffding সীমা।
  • BPP ⊆ PSPACE কেন? সব এলোমেলো string একে একে, একই জায়গায়, আর গ্রহণকারী string গোনা।
  • Miller–Rabin কোন শ্রেণিতে কী দেখায়? COMPOSITES ∈ RP, অর্থাৎ PRIMES ∈ coRP; আজ জানা PRIMES ∈ P (AKS).

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

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

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“P = BPP প্রমাণিত” বা “BPP ⊆ NP জানা”দুটিই খোলা; P = BPP শুধু অনুমান আর শর্তসাপেক্ষ ফল (Impagliazzo–Wigderson)
BPP-তে “যেকোনো একবার হ্যাঁ হলেই হ্যাঁ” দিয়ে amplificationএই নিয়ম শুধু one-sided ভুলে খাটে; two-sided-এ সংখ্যাগরিষ্ঠ ভোট লাগে
“Miller–Rabin প্রতি round-এ 1/2 ভুল করে” বা “কখনো কখনো মৌলিককে যৌগিক বলে”সীমা 1/4, আর ভুল শুধু যৌগিককে পাস করানো; ছোট সংখ্যায় সব base গুনে দেখুন
“ZPP = RP ∪ coRP” বা ZPP-কে নির্দিষ্ট (worst-case) সময়ের শ্রেণি বলাZPP = RP ∩ coRP, আর সময় প্রত্যাশিত (expected) polynomial
“Python random দিয়ে token বানানো নিরাপদ”Mersenne Twister cryptographic নয়; secrets বা অন্য CSPRNG
PP-কে BPP-র মতো “দক্ষ” বলাPP-তে ব্যবধান 2−n হতে পারে; NP ⊆ PP
বানানো সাল বা রেফারেন্স (Gill, Rabin, Impagliazzo–Wigderson)Sipser, Arora–Barak বা মূল প্রবন্ধে নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞাগুলো হুবহু চাওয়া, প্রতিটি সম্ভাবনার সীমা কোন অসমতা থেকে এল তা জিজ্ঞাসা করা, আর এমন একটি ছোট script চাওয়া, যা সব base বা সব r গুনে সীমাটি পরীক্ষা করে।

আমি গণনার তত্ত্ব শিখছি, randomized complexity নিয়ে প্রশ্ন। ১. RP, coRP, BPP, ZPP আর PP-র নিখুঁত সংজ্ঞা দাও, প্রতিটিতে w ∈ A আর w ∉ A-এর জন্য accept-এর সম্ভাবনার সীমা আলাদা করে লেখো। ২. ZPP = RP ∩ coRP-এর দুই দিকের প্রমাণ দাও; কোথায় Markov-এর অসমতা লাগে, স্পষ্ট বলো। ৩. BPP-র amplification-এর প্রমাণ দাও: কোন Chernoff বা Hoeffding সীমা ব্যবহার করছ, তার সঠিক রূপ আর ধ্রুবক লেখো। ৪. শুধু Python standard library দিয়ে একটি script দাও, যা 561, 1105 আর 8911-এর প্রতিটি base-এ একটি Miller–Rabin round চালিয়ে মিথ্যাবাদী base গোনে আর দেখায় যে অনুপাত 1/4-এর বেশি নয়। ৫. P = BPP, BPP বনাম NP কোনগুলো প্রমাণিত আর কোনগুলো খোলা, আলাদা করে লেখো; নিশ্চিত না হলে বলো, আর বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১P বনাম NP-তে বেশিরভাগ গবেষক “আলাদা” মনে করেন, অথচ P বনাম BPP-তে “সমান”। এই দুই বিশ্বাসের পেছনের প্রমাণ বা ইঙ্গিত কী?

১৯৭০-এর দশকে randomized algorithm-এর প্রথম বড় সাফল্যগুলো দেখে অনেকে ভেবেছিলেন এলোমেলোতা সত্যিই বাড়তি শক্তি দেয়। Solovay–Strassen (১৯৭৭) আর Rabin (১৯৮০)-এর primality test, Freivalds-এর matrix যাচাই, Schwartz–Zippel-এর polynomial পরীক্ষা: সবগুলো দ্রুত, আর কোনোটির deterministic সমতুল্য তখন জানা ছিল না।

কিন্তু পরের কয়েক দশকে একের পর এক randomized algorithm-এর deterministic রূপ মিলেছে। সবচেয়ে বিখ্যাত AKS (২০০২): PRIMES ∈ P. Reingold-এর undirected connectivity আরেকটি উদাহরণ। আরও গুরুত্বপূর্ণ তাত্ত্বিক ইঙ্গিত এসেছে hardness vs randomness ধারা থেকে। Yao, Blum আর Micali-র ১৯৮০-এর দশকের শুরুর কাজ থেকে ধারণা আসে যে কঠিন function থেকে pseudorandom bit বানানো যায়; Nisan আর Wigderson ১৯৯৪ সালের দিকে এটিকে complexity-র ভাষায় আনেন, আর Impagliazzo আর Wigderson ১৯৯৭ সালে দেখান, E-তে যদি একটি সমস্যার জন্য exponential আকারের circuit লাগে, তাহলে P = BPP. আর সেই অনুমানটি (কঠিন সমস্যা আছে) প্রায় সবাই সত্য মনে করেন, যেমন সবাই P ≠ NP মনে করেন।

অর্থাৎ দুটি বিশ্বাস আসলে একই উৎস থেকে আসে: “কঠিন সমস্যা সত্যিই কঠিন।” কঠিনতা থাকলে NP-র সমস্যা P-তে নামে না, আবার সেই কঠিনতাই এলোমেলোতার জায়গা নেয়। P ≠ NP আর P = BPP তাই পরস্পরবিরোধী নয়, বরং একই ছবির দুই অংশ।

তবু প্রমাণ নেই। Kabanets–Impagliazzo দেখান, polynomial identity testing-এর মতো একটি নির্দিষ্ট সমস্যাকেও derandomize করলে নতুন circuit lower bound প্রমাণ হবে, যা বহু দশকের চেষ্টাতেও আসেনি। তাই P = BPP প্রমাণ সম্ভবত P ≠ NP-র কাছাকাছি কঠিন কাজ।

মূল উপলব্ধি: P = BPP বিশ্বাসের ভিত্তি একের পর এক derandomization-এর সাফল্য আর “কঠিনতা থেকে এলোমেলোতা” তত্ত্ব; এটি P ≠ NP বিশ্বাসের সঙ্গে সামঞ্জস্যপূর্ণ, কিন্তু দুটিই অপ্রমাণিত।

প্র ০২BPP আর PP-র সংজ্ঞায় পার্থক্য শুধু “≥ 2/3” আর “> 1/2”. এই ছোট পার্থক্য দুটি শ্রেণিকে এত আলাদা করে কেন?

দুটি সংজ্ঞাই John Gill-এর ১৯৭৭ সালের প্রবন্ধ থেকে পরিচিত, যেখানে probabilistic Turing machine আর PP, BPP, ZPP-সহ শ্রেণিগুলো প্রথম গুছিয়ে সংজ্ঞায়িত হয়। পার্থক্যের মূলে আছে ব্যবধান (gap): সঠিকতার সম্ভাবনা 1/2 থেকে কত দূরে। BPP-তে ব্যবধান অন্তত 1/6, একটি ধ্রুবক, আর amplification দেখায় যে 1/poly ব্যবধানও যথেষ্ট। PP-তে ব্যবধান 2−n বা তার চেয়েও ছোট হতে পারে।

ব্যবধান ছোট হলে সংখ্যাগরিষ্ঠ ভোট দিয়ে ঠিক উত্তর বের করতে k ≈ 1/δ2 run লাগে, PP-তে যা exponential. অর্থাৎ PP-র যন্ত্র “অল্প একটু ঝোঁক” দেখায়, কিন্তু সেই ঝোঁক বাস্তবে মাপা যায় না। একটি উপমা: একটি মুদ্রা 1/2 + 2−100 সম্ভাবনায় হেড দেয়, আর 1/2 সম্ভাবনায় দেয় আরেকটি; দুটি আলাদা করতে মহাবিশ্বের বয়সেও যথেষ্ট টস হবে না।

এই কারণেই PP অনেক শক্তিশালী শ্রেণি। NP ⊆ PP (অংশ ৬-এ দেখানো), PP complement-এ বদ্ধ, তাই coNP ⊆ PP-ও। MAJSAT, অর্থাৎ “একটি সূত্রের অর্ধেকের বেশি মান-নির্ধারণ কি সত্য?”, PP-complete. আর Seinosuke Toda ১৯৯১ সালে দেখান, PP-র একটি oracle পেলে পুরো polynomial hierarchy polynomial সময়ে নেমে আসে। অর্থাৎ PP “গোনা”-র শক্তি রাখে, যা NP-র “খোঁজা”-র চেয়ে অনেক বেশি বলে মনে করা হয়।

BPP উল্টো দিকে এতটাই “নিরীহ” যে তাকে বাস্তবে দক্ষ গণনার শ্রেণি ধরা হয়; extended Church–Turing thesis-এর প্রচলিত রূপেও probabilistic Turing machine-ই আদর্শ মডেল। দুই শ্রেণির মধ্যে জানা সম্পর্ক শুধু BPP ⊆ PP.

মূল উপলব্ধি: ব্যবধানই আসল; ধ্রুবক বা 1/poly ব্যবধান amplification-এ বড় হয় আর দক্ষ গণনা দেয়, কিন্তু exponential-ভাবে ছোট ব্যবধান “গোনা”-র শক্তি এনে PP-কে NP-র চেয়েও বড় করে তোলে।

প্র ০৩Las Vegas আর Monte Carlo — বাস্তবের software-এ কখন কোনটি বেছে নেওয়া হয়, আর একটি থেকে অন্যটি কখন পাওয়া যায়?

Las Vegas algorithm কখনো ভুল উত্তর দেয় না, ঝুঁকি শুধু সময়ে। Randomized quicksort এর সবচেয়ে পরিচিত উদাহরণ। এলোমেলো pivot-এর আসল লাভ হলো, কোনো নির্দিষ্ট input আর “খারাপ” নয়: আগে থেকে সাজানো তালিকা বা ইচ্ছাকৃতভাবে বানানো প্রতিপক্ষ-input, সবকিছুতে প্রত্যাশিত সময় O(n log n). Hash table-এ এলোমেলো hash function (universal hashing) একই কাজ করে; ইচ্ছা করে একই bucket-এ সব key পাঠানোর আক্রমণ (hash flooding) এড়াতে অনেক ভাষার runtime এলোমেলো seed ব্যবহার করে।

Monte Carlo algorithm-এর সময় নিশ্চিত, ঝুঁকি উত্তরে। এটি বেছে নেওয়া হয় যখন ভুলের সম্ভাবনা ইচ্ছেমতো কমানো যায় আর যাচাইয়ের সস্তা উপায় নেই। RSA key বানাতে বড় মৌলিক সংখ্যা খোঁজায় Miller–Rabin-এর কয়েক ডজন round চালানো হয়; ভুলের সীমা তখন এত কম যে hardware-এর ত্রুটিই বড় ঝুঁকি বলে অনেকে যুক্তি দেন।

একটি থেকে অন্যটি পাওয়ার নিয়ম ZPP = RP ∩ coRP-এর প্রমাণেই আছে। Las Vegas থেকে Monte Carlo সবসময় পাওয়া যায়: সময় কেটে দিন, আর সময় ফুরালে একটি নির্দিষ্ট উত্তর দিন; Markov-এর অসমতা ভুল সীমিত রাখে। উল্টো দিক কঠিন: Monte Carlo থেকে Las Vegas পেতে উত্তরটি যাচাই করার উপায় লাগে। Matrix গুণের ক্ষেত্রে Freivalds একটি দাবি করা গুণফলকে শুধু “সম্ভবত ঠিক” বলে; একটি নিশ্চিত “ঠিক” পেতে দরকার দুই দিকের one-sided যন্ত্র, যেমন উপপাদ্য ৬.১-এ।

বাস্তবে আরেকটি বিবেচনা পুনরুৎপাদনযোগ্যতা। Debug করতে বা test-এ একই ফল পেতে নির্দিষ্ট seed রাখা হয়, যেমন এই পর্বের ব্লকগুলোতে। কিন্তু seed নির্দিষ্ট থাকলে প্রতিপক্ষও তা জানতে পারে; তখন প্রতিপক্ষ-input-এর বিরুদ্ধে এলোমেলোতার সুরক্ষা হারিয়ে যায়।

মূল উপলব্ধি: Las Vegas ঝুঁকি রাখে সময়ে, Monte Carlo উত্তরে; Las Vegas থেকে Monte Carlo সবসময় পাওয়া যায় সময় কেটে, কিন্তু উল্টোটির জন্য দুই দিকেই নিশ্চিত সাক্ষী লাগে, যা ZPP = RP ∩ coRP-এর সারকথা।

প্র ০৪তত্ত্বের probabilistic যন্ত্র সত্যিকারের ন্যায্য মুদ্রা ধরে নেয়, অথচ কম্পিউটার deterministic. তাহলে বাস্তবের randomized algorithm-এর নিশ্চয়তা কোথা থেকে আসে?

কঠোরভাবে বললে, pseudorandom number generator দিয়ে চালানো একটি “randomized” প্রোগ্রাম আসলে একটি deterministic প্রোগ্রাম, যার আচরণ seed দিয়ে ঠিক হয়। তত্ত্বের সীমা, যেমন “ভুল ≤ 2−k”, সত্যিকারের স্বাধীন মুদ্রার জন্য প্রমাণিত, কোনো নির্দিষ্ট generator-এর জন্য নয়।

Python-এর random ব্যবহার করে Mersenne Twister, যা Matsumoto আর Nishimura ১৯৯৮ সালে প্রকাশ করেন বলে পরিচিত। এর পর্যায় (period) বিশাল আর পরিসংখ্যানের অনেক পরীক্ষায় এটি ভালো করে, তাই simulation আর বেশিরভাগ randomized algorithm-এ বাস্তবে কোনো সমস্যা দেখা যায় না। কিন্তু এর ভেতরের অবস্থা আউটপুট থেকে পুনর্গঠন করা যায়, তাই কেউ ইচ্ছা করে ঠকাতে চাইলে এটি অচল। Python-এর documentation নিজেই বলে, security-র কাজে secrets ব্যবহার করতে হবে, যা অপারেটিং সিস্টেমের cryptographic উৎস থেকে bit নেয়।

তত্ত্বের দিক থেকে প্রশ্নটি হলো: এমন generator কি আছে, যার আউটপুটকে কোনো polynomial সময়ের যন্ত্র সত্যিকারের এলোমেলো bit থেকে আলাদা করতে পারে না? Blum–Micali (১৯৮৪) আর Yao (১৯৮২)-র কাজে এর শুরু, আর Håstad, Impagliazzo, Levin ও Luby ১৯৯৯ সালে দেখান বলে পরিচিত যে যেকোনো one-way function থেকে এমন cryptographic generator বানানো যায়। আর এমন generator থাকলে BPP-কে subexponential সময়ে deterministic ভাবে চালানো যায় বলে পরিচিত। অর্থাৎ বাস্তবের নিরাপত্তা আর complexity-র derandomization একই প্রশ্নের দুই মুখ, যা পর্ব ৭৬-এ বিস্তারিত আসবে।

এর একটি ব্যবহারিক শিক্ষা আছে: তত্ত্বের নিশ্চয়তা পেতে চাইলে এলোমেলোতার উৎস নিয়েও ভাবতে হয়। Simulation-এ পুনরুৎপাদনযোগ্য seed ভালো; OTP, পাসওয়ার্ড-রিসেট টোকেন বা কুপন কোডে CSPRNG বাধ্যতামূলক।

মূল উপলব্ধি: তত্ত্বের সীমা সত্যিকারের মুদ্রার জন্য; বাস্তবের PRNG সাধারণ কাজে যথেষ্ট, কিন্তু প্রতিপক্ষ থাকলে cryptographic generator লাগে, আর এমন generator-এর অস্তিত্ব one-way function আর derandomization-এর গভীর প্রশ্নের সঙ্গে জড়িত।

প্র ০৫বাজারঘরের দুই গুদামের তালিকা মেলাতে deterministic পদ্ধতিকে প্রায় পুরো তালিকা পাঠাতে হয়, অথচ randomized পদ্ধতি কয়েক ডজন bit-এ পারে। এই ব্যবধান কতটা মৌলিক?

প্রশ্নটি communication complexity-র, যার ভিত্তি Andrew Yao ১৯৭৯ সালে স্থাপন করেন বলে পরিচিত। দুই পক্ষের কাছে n-bit string x আর y; প্রশ্ন x = y কি না (EQUALITY). একটি পরিচিত উপপাদ্য বলে, যেকোনো deterministic protocol-এ সবচেয়ে খারাপ ক্ষেত্রে প্রায় n bit আদান-প্রদান লাগে। প্রমাণের ধারণা: যদি কম bit-এ কাজ হতো, তাহলে দুটি আলাদা x, x′ একই কথোপকথন দিত, আর (x, x′) জোড়ায় protocol ভুল করত।

Randomized protocol-এ ঢাকা একটি এলোমেলো r আর fingerprint F(r) পাঠায়, মোট O(log n) bit (q যদি n-এর polynomial হয়)। ভুলের সম্ভাবনা ≤ (n − 1)/q, আর তা কমাতে কয়েকটি স্বাধীন fingerprint পাঠালেই চলে। তাই এখানে randomization-এর লাভ exponential, n থেকে log n, আর এটি প্রমাণিত, অনুমান নয়। Complexity শ্রেণির বেলায় (P বনাম BPP) এমন প্রমাণিত ব্যবধান নেই; communication-এর মডেলে প্রমাণ সহজ, কারণ সেখানে শুধু তথ্য গোনা হয়, গণনার সময় নয়।

একই ধারণা বাস্তবে সর্বত্র। Rabin ১৯৮১ সালে polynomial-ভিত্তিক fingerprint প্রস্তাব করেন বলে পরিচিত, যার রূপ string-matching-এর Rabin–Karp algorithm-এ দেখা যায়। ফাইল সমন্বয়ের tool, backup ব্যবস্থা আর বিতরণকৃত database ছোট checksum বা hash মিলিয়ে বোঝে কোন অংশ বদলেছে। তবে বাস্তবে প্রায়ই নির্দিষ্ট (এলোমেলো নয়) hash function ব্যবহার হয়; তখন প্রতিপক্ষ ইচ্ছা করে একই hash-এর দুটি আলাদা ফাইল বানাতে পারে কি না, সেটি cryptographic hash-এর প্রশ্ন, এই পর্বের সম্ভাবনার সীমা আর সেখানে খাটে না।

মূল উপলব্ধি: EQUALITY-তে deterministic protocol-এর প্রায় n bit আর randomized protocol-এর O(log n) bit-এর ব্যবধান প্রমাণিত; এলোমেলো r প্রতিপক্ষের কাছে অজানা থাকে বলেই কয়েকটি bit যথেষ্ট, আর এই ধারণাই checksum ও hash-ভিত্তিক সমন্বয়ের তাত্ত্বিক ভিত্তি।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। fermat_vs_mr.py আর fingerprint.py বদলে নিজের সংখ্যা দিয়েও যাচাই করতে পারেন।

  1. নকশা: বাজারঘরের দুই শাখার কাছে n-টি অর্ডার-নম্বরের দুটি তালিকা, কিন্তু ক্রম আলাদা হতে পারে। প্রশ্ন হলো তালিকা দুটি একই multiset কি না (একই নম্বর, একই সংখ্যকবার)। একটি randomized protocol নকশা করুন, যা কয়েক ডজন bit পাঠায়, সমান হলে সবসময় “সমান” বলে, আর অসমান হলে ছোট সম্ভাবনায় ভুল করে। ভুলের সীমা দিন।

    অংশ ৫-এর polynomial ক্রমের ওপর নির্ভর করে, তাই এখানে চলবে না। ক্রম-নিরপেক্ষ polynomial নিন: Pa(x) = (x − a1)(x − a2)⋯(x − an) mod q, যেখানে q একটি মৌলিক, সব অর্ডার-নম্বরের চেয়ে বড়। গুণফল ক্রমের ওপর নির্ভর করে না, আর তালিকা একই multiset ⇔ Pa = Pb polynomial হিসেবে (একক উৎপাদকে বিশ্লেষণ অনন্য)। Protocol: প্রথম শাখা এলোমেলো r ∈ {0, …, q − 1} বেছে (r, Pa(r)) পাঠায়, দ্বিতীয় শাখা Pb(r) মেলায়।

    সমান হলে মান সবসময় মেলে (one-sided). অসমান হলে Pa − Pb অশূন্য, degree ≤ n, তাই Schwartz–Zippel থেকে ঠকার সম্ভাবনা ≤ n/q. q ≈ 231 আর n = 104 হলে সীমা প্রায় 4.7 × 10−6; পাঠানো bit প্রায় ৬২. Scratch-এ ১,০০০টি নম্বরের তালিকা আর তার এলোমেলো ক্রমে সাজানো কপি দিয়ে পরীক্ষা করা হয়েছে: ২০টি r-এ প্রতিবার “সমান”, আর একটি নম্বর বদলালে ২০টির একটিতেও মেলেনি। চাইলে k বার চালিয়ে সীমা (n/q)k.

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: BPP-র যেকোনো যন্ত্রের ভুল k বার চালিয়ে (1/3)k-এ নামানো যায়। প্রমাণ: M-কে k বার স্বাধীনভাবে চালাই, আর যেকোনো একবার accept করলে accept করি। একবারের ভুল ≤ 1/3, run-গুলো স্বাধীন, তাই সবগুলো ভুল হওয়ার সম্ভাবনা ≤ (1/3)k. ∎” ভুল কোথায়? সঠিক নিয়ম কী?

    যুক্তিটি শুধু w ∈ A-র দিক দেখেছে: সেখানে M′ ভুল করে কেবল যখন সব run reject করে, সম্ভাবনা ≤ (1/3)k. কিন্তু w ∉ A হলে প্রতিটি run 1/3 পর্যন্ত সম্ভাবনায় ভুল করে accept করতে পারে, আর “যেকোনো একবার accept” নিয়মে M′ ভুল করে যখন অন্তত একটি run ভুল: সম্ভাবনা 1 − (2/3)k, যা k বাড়লে 1-এর দিকে যায়। দাবিটি তাই মিথ্যা।

    এই নিয়ম শুধু one-sided ভুলে, অর্থাৎ RP-তে, কাজ করে, যেখানে w ∉ A হলে কোনো run accept করে না। BPP-র সঠিক নিয়ম সংখ্যাগরিষ্ঠ ভোট, আর ভুলের সীমা আসে Chernoff–Hoeffding থেকে: ≤ e−k/18, (1/3)k নয়।

  3. Trace আর আগাম অনুমান: n = 91 = 7 · 13. n − 1 = 90 = 2 · 45, তাই s = 1. (ক) base 3: Fermat-এর পরীক্ষা আর একটি Miller–Rabin round কী বলে? দেওয়া আছে 345 mod 91 = 27. (খ) base 10: দেওয়া আছে 1045 mod 91 = 90. (গ) fermat_vs_mr.py-র তালিকায় 91 যোগ করলে MR-মিথ্যাবাদী base কয়টি আসবে বলে আন্দাজ করেন, আর তা ১/৪-এর সীমা মানে কি?

    (ক) 390 = (345)2 = 272 = 729 = 8 · 91 + 1 ≡ 1, তাই Fermat পাস (3 একটি Fermat-মিথ্যাবাদী)। কিন্তু MR-এ s = 1, তাই বর্গ করার কোনো ধাপ নেই: x = 345 = 27, যা 1-ও নয়, 90-ও নয়, তাই COMPOSITE. 27 হলো 1-এর একটি অদ্ভুত বর্গমূল; gcd(26, 91) = 13 আর gcd(28, 91) = 7.

    (খ) x = 1045 ≡ 90 ≡ −1, তাই MR পাস: 10 একটি strong liar. Fermat-ও পাস। (গ) Scratch-এ গোনা হয়েছে: 1 থেকে 90-এর মধ্যে ঠিক ১৮টি base MR-এ পাস করে (1, 9, 10, 12, 16, 17, …, 81, 82, 90), অর্থাৎ ২০ শতাংশ, যা ১/৪-এর নিচে।

  4. হিসাব: (ক) একটি RP algorithm-এর প্রতিটি run-এ “হ্যাঁ”-কে ভুল করে “না” বলার সম্ভাবনা ≤ 1/2. ভুল 10−9-এর নিচে নামাতে কমপক্ষে কতবার চালাতে হবে? (খ) Miller–Rabin-এ ভুল ≤ 2−40 চাইলে কত round? (গ) 1000 × 1000 matrix-এ Freivalds-এর ২০ round-এ মোট কত গুণন, আর স্কুলের পদ্ধতির n3-এর সঙ্গে তুলনা কী? (ঘ) BPP-র যন্ত্রের ভুল 1/3; উপপাদ্য ৪.২-এর সীমা e−k/18 ব্যবহার করে ভুল ≤ 2−50 নিশ্চিত করতে সবচেয়ে ছোট বিজোড় k কত?

    (ক) 2−k ≤ 10−9 চাই। 229 ≈ 5.4 × 108 যথেষ্ট নয়, 230 ≈ 1.07 × 109 যথেষ্ট; তাই k = 30. (খ) প্রতি round-এ ≤ 1/4, তাই 4−k = 2−2k ≤ 2−40 থেকে k = 20.

    (গ) প্রতি round-এ তিনটি matrix-vector গুণ, প্রতিটিতে n2 = 106 গুণন, মোট 3 × 106; ২০ round-এ 6 × 107. স্কুলের পদ্ধতিতে n3 = 109, প্রায় ১৭ গুণ বেশি, আর n বাড়লে অনুপাত n-এর সমানুপাতে বাড়ে। (ঘ) e−k/18 ≤ 2−50 ⇔ k ≥ 18 · 50 · ln 2 ≈ 623.8, তাই k = 624 যথেষ্ট, আর সবচেয়ে ছোট বিজোড় k = 625. আসল ভুল এর অনেক কম, কারণ সীমাটি ঢিলে।

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

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

ক্রমBPP ⊆ PSPACE-এর প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. BPP-র যন্ত্র M-কে input w আর দৈর্ঘ্য p(n)-এর এলোমেলো string r নেওয়া deterministic যন্ত্র M(w, r) হিসেবে দেখা
  2. সব r ∈ {0, 1}p(n) একটি counter-এ একে একে তৈরি করা
  3. প্রতিটি r-এ M(w, r) চালানো, একই জায়গা মুছে আবার ব্যবহার করে
  4. Accept করা r-গুলো p(n) + 1 bit-এর আরেকটি counter-এ গোনা
  5. গোনা সংখ্যা 2p(n)-এর অর্ধেকের বেশি হলে accept, মোট জায়গা O(p(n))

একটি polynomial সময়ের probabilistic যন্ত্র w ∈ A হলে অন্তত 1/2 সম্ভাবনায় accept করে, আর w ∉ A হলে কখনো accept করে না। A নিশ্চিতভাবে কোন শ্রেণিতে?

  • coRP
  • RP
  • ZPP
  • P

নিচের কোনটি ZPP-র একটি প্রমাণিত বর্ণনা?

  • ZPP = RP ∪ coRP
  • ZPP = BPP
  • ZPP = RP ∩ coRP
  • ZPP = NP ∩ coNP

Miller–Rabin পরীক্ষার একটি round সম্পর্কে কোন বক্তব্যটি সঠিক (n বিজোড়, n > 3)?

  • n মৌলিক হলে কখনো “যৌগিক” বলে না; n যৌগিক হলে বড়জোর 1/4 সম্ভাবনায় পাস করায়
  • Carmichael সংখ্যায় প্রতিটি সহমৌলিক base পাস করে, তাই এরা Miller–Rabin-কেও ঠকায়
  • দুই দিকেই ভুল সম্ভব, প্রতিটি ≤ 1/3, তাই PRIMES ∈ BPP মাত্র
  • Miller–Rabin নিজেই দেখায় যে PRIMES ∈ P

একটি BPP algorithm প্রতিটি input-এ 1/3 সম্ভাবনায় ভুল করে। ভুল কমানোর সঠিক উপায় আর ফল কোনটি?

  • k বার চালিয়ে যেকোনো একবার accept হলে accept; ভুল (1/3)k
  • একবার চালিয়ে উত্তর দুবার পড়া; ভুল 1/9
  • k বার চালিয়ে সংখ্যাগরিষ্ঠ ভোট; ভুল প্রায় 1/(3k)
  • k বার চালিয়ে সংখ্যাগরিষ্ঠ ভোট; ভুল ≤ e−k/18

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

  • P = BPP
  • BPP ⊆ PSPACE
  • BPP ⊆ NP
  • NP ⊆ BPP

Freivalds-এর পদ্ধতিতে n × n matrix A, B, C-র জন্য এলোমেলো 0/1 vector r নিয়ে A(Br) আর Cr মেলানো হয়। AB ≠ C হলে একটি round-এ ভুল ধরা না পড়ার সম্ভাবনা আর এক round-এর খরচ কত?

  • ≤ 3/4, আর খরচ n3 গুণন
  • 0, আর খরচ n2 গুণন
  • ≤ 1/2, আর খরচ প্রায় 3n2 গুণন
  • ≤ 1/n, আর খরচ n log n গুণন

শব্দকোষ

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

মনে রাখুন

  1. Probabilistic Turing machine-এ k মুদ্রার শাখার সম্ভাবনা 2−k; গ্রহণের সম্ভাবনা গ্রহণকারী শাখাগুলোর যোগফল, আর সীমা প্রতিটি input-এর জন্য।
  2. RP: “হ্যাঁ”-তে ≥ 1/2, “না”-তে 0; BPP: দুই দিকে ভুল ≤ 1/3; ZPP: সবসময় সঠিক, প্রত্যাশিত polynomial সময়; PP: শুধু > 1/2.
  3. Amplification: one-sided-এ পুনরাবৃত্তি (2−k), two-sided-এ সংখ্যাগরিষ্ঠ ভোট (≤ e−k/18); PP-তে ব্যবধান ক্ষুদ্র বলে চলে না।
  4. COMPOSITES ∈ RP (Miller–Rabin), AB ≠ C যাচাই RP-তে (Freivalds), polynomial-এর অভেদ coRP-তে (Schwartz–Zippel); fingerprint কয়েকটি bit-এ তালিকা মেলায়।
  5. P ⊆ ZPP = RP ∩ coRP, RP ⊆ NP ∩ BPP, BPP ⊆ PSPACE প্রমাণিত; P = BPP অনুমান মাত্র, আর বাস্তবে নিরাপত্তার কাজে CSPRNG লাগে।

পরের পর্বে: Circuit complexity: Boolean circuit-এর আকার আর গভীরতা, P/poly, প্রায় সব function-এর জন্য বিশাল circuit লাগে কেন, আর NP-র জন্য বড় lower bound প্রমাণ এত কঠিন কেন।

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

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