Approximation ও Randomized Complexity — যখন নিখুঁত উত্তর অপেক্ষা করতে পারে না

আগে এটা বুঝি

একটা delivery কোম্পানির dispatcher-কে কল্পনা করুন। আজ সকালে ২০০টা package, ৩০টা ট্রাক, আর optimal route খুঁজে বের করতে হবে যাতে মোট দূরত্ব সর্বনিম্ন হয়। এটা classic Vehicle Routing Problem — Traveling Salesman-এর একটা আত্মীয়, NP-hard।

Dispatcher-এর কাছে দুইটা বিকল্প নেই — একটা মাত্র। এক্সপোনেনশিয়াল সময় নিয়ে বসে থাকা কোনো বিকল্পই না; ট্রাকগুলো আজই বের হবে। তাহলে dispatcher কী করেন?

গত দুইটা লেসনে আমরা দেখেছি NP-complete সমস্যার জন্য exact polynomial algorithm সম্ভবত নেই (P \ne NP} বিশ্বাস করা হয়), আর এই “সম্ভবত”-টা প্রমাণ করা কতটা কঠিন। কিন্তু বাস্তব জগৎ এই তাত্ত্বিক অনিশ্চয়তার জন্য অপেক্ষা করে না — dispatcher একটা route বেছে নেন যা “মোটামুটি ভালো, দ্রুত পাওয়া যায়, আর কতটা খারাপ হতে পারে তা জানা যায়”।

এই লেসনে আমরা এই “মোটামুটি ভালো, কিন্তু প্রমাণযোগ্যভাবে” ধারণাটাকে আনুষ্ঠানিক করব — তিনটা ভিন্ন কৌশলে: approximation algorithm (গাণিতিক গ্যারান্টি সহ কাছাকাছি সমাধান), randomized algorithm (কয়েন-ফ্লিপ দিয়ে speed কেনা, নিয়ন্ত্রিত ঝুঁকিতে), আর দেখব কেন — বিস্ময়করভাবে — কিছু সমস্যায় আনুমানিক সমাধান খোঁজাও ঠিক ততটাই কঠিন যতটা নিখুঁত সমাধান খোঁজা (PCP theorem)।

মূল ধারণা

Approximation ratio — ‘কতটা খারাপ হতে পারে’ তার একটা সংখ্যা

একটা minimization সমস্যার জন্য (যেমন Vertex Cover — যত ছোট কভার, তত ভালো), একটা algorithm A-কে α-approximation বলা হয় যদি প্রতিটা instance x-এর জন্য:

A(x) \le \alpha \cdot \mathrm{OPT}(x)

যেখানে \mathrm{OPT}(x) হলো সত্যিকার অপটিমাল মান (যা আমরা জানি না, কারণ সেটা খুঁজতেই তো exponential সময় লাগত — কিন্তু গাণিতিক প্রমাণে এর অস্তিত্ব ও নিম্নসীমা ব্যবহার করি)। Maximization সমস্যার জন্য (যেমন Independent Set) অসমতা উল্টো দিকে: A(x) \ge \mathrm{OPT}(x) / \alpha।

\alpha = 1 মানে নিখুঁত (exact) algorithm — সাধারণত NP-hard সমস্যায় অসম্ভব বলে বিশ্বাস করা হয় polynomial সময়ে। \alpha যত 1-এর কাছাকাছি, algorithm তত ভালো। গুরুত্বপূর্ণ: এই গ্যারান্টি প্রতিটা instance-এর জন্য সত্য হতে হবে — শুধু গড়ে ভালো হলেই চলবে না।

Vertex Cover — একটা 2-approximation, হাতে-কলমে

\text{VERTEX-COVER}: একটা graph G = (V, E)-এ সর্বনিম্ন node-সেট খুঁজুন যা প্রতিটা edge-এর অন্তত একটা প্রান্ত ঢাকে (আগের লেসনে এই সমস্যাই NP-complete প্রমাণিত হয়েছিল)।

Greedy algorithm — “matching-based”:

C = ∅  (কভার, খালি থেকে শুরু)
E' = E  (ঢাকা বাকি এমন edge-এর সেট)
যতক্ষণ E' খালি না হয়:
    (u, v) কে E' থেকে যেকোনো একটা edge বাছুন
    C-তে u এবং v দুইটাই যোগ করুন
    E' থেকে u বা v-কে স্পর্শ করে এমন সব edge বাদ দিন
ফেরত দিন C

দাবি: এই algorithm একটা 2-approximation।

প্রমাণ। লক্ষ্য করুন algorithm যে edge-গুলো বাছে ((u_1,v_1), (u_2,v_2), \ldots), এরা পরস্পর থেকে স্বতন্ত্র (disjoint) — কারণ একটা edge বাছার সাথে সাথে তার দুই প্রান্তকে স্পর্শ করা সব edge বাদ দেওয়া হয়, তাই পরের বাছা edge-টা আগেরটার সাথে কোনো node share করতে পারে না। এই বাছা edge-গুলোর সেট একটা matching (কোনো দুইটা edge কোনো node share করে না)।

ধরুন algorithm k-টা edge বাছল, তাই |C| = 2k (প্রতি edge-এ ২টা node)।

এখন যেকোনো বৈধ vertex cover (এমনকি optimal-ও) এই k-টা matching edge-এর প্রতিটা-র অন্তত একটা প্রান্ত ধারণ করতেই হবে (নাহলে সেই edge-টাই অ-ঢাকা থেকে যাবে)। যেহেতু matching edge-গুলো পরস্পর disjoint (কোনো node share করে না), একটা node দুইটা matching edge-কে একসাথে ঢাকতে পারবে না। তাই:

\mathrm{OPT}(G) \ge k

আর আমাদের algorithm-এর কভার:

A(G) = 2k \le 2 \cdot \mathrm{OPT}(G)

তাই \alpha = 2 ∎

প্রমাণের কৌশলটাই গুরুত্বপূর্ণ শিক্ষা

লক্ষ্য করুন — আমরা কখনো \mathrm{OPT}(G)-এর প্রকৃত মান জানি না (সেটা NP-hard খুঁজে বের করা)। প্রমাণের কৌশল হলো একটা সহজে-গণনাযোগ্য lower bound (k, matching-এর আকার) খুঁজে বের করা যা \mathrm{OPT}-এর নিচে থাকতে বাধ্য, আর তারপর algorithm-এর output-কে সেই lower bound-এর সাথে তুলনা করা। প্রায় প্রতিটা approximation-ratio প্রমাণ এই একই প্যাটার্ন অনুসরণ করে — “আমি জানি না optimal কত, কিন্তু জানি এটা অন্তত এতটা বড়/ছোট হতেই হবে।”

Set Cover — greedy, কিন্তু ratio ভিন্ন চরিত্রের

\text{SET-COVER}: একটা universe U (n-টা element) আর কিছু subset S_1, \ldots, S_m \subseteq U দেওয়া আছে — সর্বনিম্ন কতগুলো subset বাছলে তাদের union পুরো U ঢাকে?

Greedy algorithm: প্রতি ধাপে সেই subset বাছুন যেটা এখনো-না-ঢাকা element সবচেয়ে বেশি ঢাকে; পুনরাবৃত্তি করুন যতক্ষণ না সব ঢাকা হয়।

এই algorithm-এর approximation ratio \ln n + 1 (প্রায় O(\log n)) — constant নয়, n-এর সাথে বাড়ে। প্রমাণের মূল কৌশল potential-function যুক্তি: প্রতিটা ধাপে যদি greedy একটা subset বাছে যা remaining uncovered element-এর 1/t অংশ ঢাকে (t = optimal সমাধানের size), তাহলে uncovered element সংখ্যা প্রতি রাউন্ডে গুণিতক হারে কমে — harmonic series-এর মতো যোগফল দিয়ে \ln n bound বেরিয়ে আসে।

সমস্যা	Algorithm	Approximation ratio	ratio-র চরিত্র
Vertex Cover	matching-based greedy	`2`	constant — instance size নির্বিশেষে সবসময় `2×`-এর মধ্যে
Set Cover	most-uncovered-first greedy	`\ln n + 1`	logarithmic — `n` বাড়লে ratio-ও (ধীরে) বাড়ে

দুইটা greedy approximation, দুই ভিন্ন ধরনের গ্যারান্টি।

গুরুত্বপূর্ণ ফলাফল (পরের “hood” অংশে PCP-এর সাথে যুক্ত): Set Cover-এর \ln n ratio optimal — প্রমাণিত (Feige, ১৯৯৮, PCP theorem-ভিত্তিক কৌশলে) যে (1-\epsilon)\ln n factor-এর চেয়ে ভালো approximation NP-hard, যদি না NP \subseteq \mathrm{DTIME}(n^{O(\log \log n)}) (যা P \ne NP}-এর প্রায় সমতুল্য একটা অসম্ভাব্য দাবি)। অর্থাৎ এই সাধারণ greedy algorithm-টাই — কোনো আরো চতুর কৌশল না — তাত্ত্বিকভাবে যতটা ভালো সম্ভব ততটাই ভালো।

BPP — bounded-error randomization

algorithms/randomized-algorithms লেসনে Monte Carlo algorithm দেখেছেন — এমন algorithm যা সবসময় polynomial সময়ে থামে, কিন্তু ছোট সম্ভাবনায় ভুল উত্তর দিতে পারে। এই ধারণাটার আনুষ্ঠানিক complexity class হলো BPP (Bounded-error Probabilistic Polynomial time):

L \in \mathbf{BPP} \iff \exists \text{ polynomial-time probabilistic TM } M :

x \in L \implies \Pr[M(x) = \text{accept}] \ge \frac{2}{3}, \qquad x \notin L \implies \Pr[M(x) = \text{accept}] \le \frac{1}{3}

2/3 আর 1/3-এর সংখ্যাগুলো নির্দিষ্ট কিছু নয় — যেকোনো constant p > 1/2 (সঠিক উত্তরের সম্ভাবনা) কাজ করবে, কারণ…

Error amplification — কেন “১/৩ ভুল” আসলে ব্যবহারিকভাবে “প্রায় শূন্য ভুল”

একটা algorithm যেটা 1/3 সম্ভাবনায় ভুল করে শোনাতে অনির্ভরযোগ্য মনে হতে পারে। কিন্তু independent repetition দিয়ে এই error সূচকীয় হারে কমানো যায়।

M-কে k-বার স্বাধীনভাবে চালান, majority vote নিন। Chernoff bound (একটা concentration inequality, mathematics module-এর probability লেসনের সম্প্রসারণ) অনুযায়ী, majority ভুল হওয়ার সম্ভাবনা:

\Pr[\text{majority ভুল}] \le e^{-c \cdot k}

কোনো ধ্রুবক c > 0-এর জন্য (মূল error probability-র উপর নির্ভরশীল)। k রৈখিকভাবে বাড়ালে error সূচকীয়ভাবে কমে।

`k` (repetition)	আনুমানিক error probability
`1`	`1/3 ≈ 0.33`
`10`	`~10^{-2}`
`50`	`~10^{-7}`
`100`	`~10^{-14}`
`300`	`~10^{-40}` — মহাবিশ্বে atom-এর সংখ্যার চেয়ে ছোট সম্ভাবনা

k বার independent repetition-এ error কীভাবে কমে (illustrative, মূল error 1/3 ধরে)।

k = 300-এ error এতটাই ক্ষুদ্র যে মহাজাগতিক রশ্মির আঘাতে RAM-এর একটা bit উল্টে যাওয়ার সম্ভাবনা (hardware cosmic-ray bit-flip rate) algorithm-এর নিজের ভুলের সম্ভাবনার চেয়ে বেশি — ব্যবহারিকভাবে “নিশ্চিত” বলা যায়, যদিও তাত্ত্বিকভাবে শূন্য নয়।

P ⊆ BPP ⊆ PSPACE, আর derandomization-এর প্রশ্ন

\mathbf{P} \subseteq \mathbf{BPP} তুচ্ছ (deterministic algorithm randomness ব্যবহারই না করে BPP-এর শর্ত পূরণ করে)। \mathbf{BPP} \subseteq \mathbf{PSPACE} প্রমাণিত (সব সম্ভাব্য coin-flip sequence পুনর্ব্যবহারযোগ্য space-এ enumerate করা যায়, ঠিক NP \subseteq PSPACE-এর মতো যুক্তিতে)। আরেকটা বড় খোলা প্রশ্ন (যদিও P বনাম NP-এর চেয়ে কম বিখ্যাত): \mathbf{P} = \mathbf{BPP}? অনেক complexity theorist বিশ্বাস করেন হ্যাঁ (এই বিশ্বাসের ভিত্তি derandomization তত্ত্ব — pseudorandom generator দিয়ে randomness-কে নিয়ন্ত্রিতভাবে বাদ দেওয়া যায়, যদি নির্দিষ্ট circuit-lower-bound অনুমান সত্য হয়)। এটাও P বনাম NP-এর মতোই একটা “বিশ্বাস করি, প্রমাণ নেই” পরিস্থিতি — এই module-এর একটা পুনরাবৃত্ত থিম।

ভেতরে কী ঘটছে

PCP theorem — কেন কিছু সমস্যায় ‘প্রায়’ খোঁজাও কঠিন

এতক্ষণ আমরা ধরে নিয়েছি approximation সবসময় exact সমাধানের চেয়ে সহজ। এখন একটা চমকপ্রদ বিপরীত ফলাফল দেখব: কিছু সমস্যায় approximation নিজেও NP-hard।

এর ভিত্তি PCP theorem (Probabilistically Checkable Proofs, Arora-Safra ও Arora-Lund-Motwani-Sudan-Szegedy, ১৯৯২) — জটিলতা তত্ত্বের সবচেয়ে গভীর ফলাফলগুলোর একটা:

\mathbf{NP} = \mathrm{PCP}(O(\log n),\ O(1))

স্বজ্ঞাতভাবে এর মানে: প্রতিটা NP সমস্যার (যেমন SAT) জন্য প্রমাণ-গুলোকে (satisfying assignment) এমনভাবে পুনরায়-এনকোড করা যায় যে একটা verifier —

মাত্র O(\log n)-বিট random বাছে (যা কোন অংশ পড়বে তা নির্ধারণ করতে ব্যবহার করে)
প্রমাণের মাত্র O(1) (ধ্রুবক সংখ্যক!) bit পড়ে (পুরো প্রমাণ নয়!)
এই সামান্য তথ্য দিয়েই সিদ্ধান্ত নেয়: সঠিক প্রমাণ সবসময় accept, ভুল প্রমাণ অন্তত 1/2 সম্ভাবনায় reject করে

Cook-Levin-এর প্রমাণের সাথে সংযোগ

মনে করুন আগের লেসনের computation tableau — সেই এনকোডিং-এ প্রমাণের একটা bit ভুল হলে verifier-কে ঠিক সেই bit-টা পড়তে হতো ধরার জন্য। PCP theorem বলছে একটা সম্পূর্ণ ভিন্ন এনকোডিং সম্ভব — যেখানে প্রমাণে যেকোনো ভুল (এমনকি একটা মাত্র bit ভুল) পুরো এনকোডিং জুড়ে “ছড়িয়ে” যায়, এতটাই ব্যাপকভাবে যে মাত্র কয়েকটা এলোমেলো bit চেক করলেও ধরা পড়ার সম্ভাবনা 50%-এর বেশি। এই “error-spreading” এনকোডিং কৌশলটাই (error-correcting code-এর একটা গভীর সম্প্রসারণ) PCP theorem-এর প্রমাণের হৃদয়, আর এই module-এর “information theory” লেসনে error-correcting code-এর মূল ধারণাগুলো ফিরে আসবে।

PCP থেকে inapproximability — ‘gap-producing reduction’

PCP theorem থেকে সরাসরি বেরিয়ে আসে একটা শক্তিশালী কৌশল: gap-producing reduction। ধারণাটা:

SAT-এর একটা instance \phi-কে (PCP verifier ব্যবহার করে) একটা নতুন optimization instance-এ (যেমন Max-3-SAT — সর্বোচ্চ কতগুলো clause একসাথে satisfy করা যায়) রূপান্তর করা যায়, এমনভাবে যে:

যদি \phi satisfiable হয় ⟹ নতুন instance-এ সব clause satisfy করা যায় (100%)
যদি \phi unsatisfiable হয় ⟹ নতুন instance-এ কোনো সমাধান clause-এর (1-\epsilon) ভগ্নাংশের বেশি satisfy করতে পারে না, কোনো fixed \epsilon > 0-এর জন্য

এখন যদি কারো কাছে একটা algorithm থাকে যা Max-3-SAT-এর (1-\epsilon)-এর চেয়ে ভালো approximation দিতে পারে, সেই algorithm ব্যবহার করে \phi satisfiable কি না নিশ্চিতভাবে বলে দেওয়া যাবে (কারণ approximate উত্তরটাই 100% আর \le 1-\epsilon}-এর মধ্যে পার্থক্য করে দেবে) — কিন্তু SAT NP-complete, তাই এটা P = NP প্রমাণ করে দেবে!

উপসংহার: Max-3-SAT-কে (1-\epsilon)-এর চেয়ে ভালো approximate করা NP-hard — approximation-ও NP-hard, নিখুঁত সমাধানের মতোই। Håstad (২০০১) সঠিক threshold প্রমাণ করেন: Max-3-SAT-এর সেরা সম্ভাব্য (polynomial-time) approximation ratio ঠিক 7/8 (একটা সরল random-assignment algorithm এই ratio অর্জন করে, আর PCP theorem প্রমাণ করে এর চেয়ে ভালো করা NP-hard) — উপরের সীমা আর নিচের সীমা হুবহু মিলে যায়, একটা বিরল “tight” ফলাফল।

সমস্যা	সেরা জানা approximation	Inapproximability (PCP-based)
Vertex Cover	`2` (এই লেসনের প্রমাণ)	`1.36`-এর কম কোনো ratio অসম্ভব বলে জানা (Unique Games Conjecture ধরলে আরো শক্ত bound)
Set Cover	`\ln n` (greedy)	`(1-\epsilon)\ln n` অসম্ভব (Feige)
Max-3-SAT	`7/8` (random assignment)	`7/8`-এর বেশি অসম্ভব (Håstad) — tight
Max-Clique	`n^{1-\epsilon}` factor-এর মধ্যেও কঠিন	কার্যত কোনো ভালো constant-factor approximation নেই

সব NP-hard optimization সমস্যা সমান 'approximation-resistant' নয় — PCP theorem এই পার্থক্যটা প্রমাণ করে।

উদাহরণ

Vertex Cover approximation — একটা সম্পূর্ণ concrete উদাহরণ

Graph G:
   1 ── 2 ── 3
   │    │    │
   4 ── 5 ── 6

Edges: (1,2) (2,3) (1,4) (2,5) (3,6) (4,5) (5,6)

একটা ৬-node graph — greedy matching-based algorithm ধাপে ধাপে।

Greedy চালানো:

ধাপ ১: (1,2) বাছুন → C = {1,2}
        বাদ দিন: (1,2)(1,4)(2,3)(2,5) — বাকি E' = {(3,6)(4,5)(5,6)}
ধাপ ২: (3,6) বাছুন → C = {1,2,3,6}
        বাদ দিন: (3,6) — বাকি E' = {(4,5)(5,6)}
ধাপ ৩: (4,5) বাছুন → C = {1,2,3,4,5,6}
        বাদ দিন: (4,5)(5,6) — বাকি E' = ∅

ফলাফল: |C| = 6 (পুরো graph, এই ছোট উদাহরণে)

এই ছোট উদাহরণে greedy-র ফলাফল খারাপ দেখাচ্ছে (পুরো ৬-node নিয়েছে), কারণ graph-টা ছোট এবং ঘন। প্রকৃত optimal এখানে \{2, 5, 6\} বা \{2, 4, 6\} (৩-node দিয়ে সব edge ঢাকা সম্ভব — হাতে verify করুন)। তাই এখানে A(G) = 6, \mathrm{OPT}(G) = 3, অনুপাত = 2 — ঠিক প্রমাণিত \alpha = 2 bound-এর সীমানায়, যা দেখায় bound-টা tight (আরো ভালো constant প্রমাণ করা যাবে না এই সাধারণ algorithm-এর জন্য)।

Greedy 'বাছার ক্রম' গুরুত্বপূর্ণ নয়, কিন্তু ফলাফলের মান নির্ভরশীল

লক্ষ্য করুন algorithm যেকোনো ক্রমে edge বাছলেও 2×-এর গ্যারান্টি বজায় থাকে (প্রমাণে কোনো নির্দিষ্ট ক্রম ধরা হয়নি) — কিন্তু ভিন্ন ক্রমে ভিন্ন actual output সাইজ আসতে পারে (এই উদাহরণে ভিন্ন ক্রমে 4 বা 6 node-এর কভার আসতে পারে, উভয়ই \le 2 \times \mathrm{OPT} = 6 মেনে চলে)। এটাই approximation guarantee-র প্রকৃতি — একটা worst-case upper bound, প্রতিটা রানে সবচেয়ে ভালো সম্ভব ফলাফলের প্রতিশ্রুতি নয়।

নিজে চালিয়ে দেখুন

EXPERIMENT

Greedy Vertex Cover-এর ratio পরিমাপ — বনাম brute-force optimal

Python 3· ২০ মিনিট

import itertools, random

def greedy_vertex_cover(n, edges):
    cover = set()
    remaining = set(edges)
    while remaining:
        u, v = next(iter(remaining))
        cover.add(u); cover.add(v)
        remaining = {(a, b) for (a, b) in remaining if a not in (u, v) and b not in (u, v)}
    return cover

def optimal_vertex_cover(n, edges):
    """Brute force — শুধু ছোট graph-এ যাচাইয়ের জন্য"""
    nodes = list(range(n))
    for k in range(n + 1):
        for subset in itertools.combinations(nodes, k):
            s = set(subset)
            if all(u in s or v in s for u, v in edges):
                return s
    return set(nodes)

random.seed(3)
print(f"{'n':>4} {'edges':>6} {'greedy':>7} {'optimal':>8} {'ratio':>7}")
ratios = []
for trial in range(15):
    n = random.randint(4, 9)
    all_pairs = list(itertools.combinations(range(n), 2))
    m = random.randint(n, min(len(all_pairs), 2 * n))
    edges = random.sample(all_pairs, m)

    g = greedy_vertex_cover(n, edges)
    o = optimal_vertex_cover(n, edges)
    ratio = len(g) / len(o) if o else 1.0
    ratios.append(ratio)
    print(f"{n:>4} {m:>6} {len(g):>7} {len(o):>8} {ratio:>7.2f}")

print(f"\nসর্বোচ্চ measured ratio: {max(ratios):.2f}  (তাত্ত্বিক upper bound: 2.00)")
print(f"গড় ratio             : {sum(ratios)/len(ratios):.2f}")

প্রত্যাশিত (illustrative) আউটপুট:

   n  edges  greedy  optimal   ratio
   5      6       4        3    1.33
   6      8       4        3    1.33
   7     10       6        4    1.50
   8     12       6        4    1.50
   9     14       8        5    1.60
   ...

সর্বোচ্চ measured ratio: 1.75  (তাত্ত্বিক upper bound: 2.00)
গড় ratio             : 1.42

লক্ষ্য করুন: measured ratio কখনো 2.00 অতিক্রম করে না (প্রমাণ অনুযায়ী এটাই হওয়ার কথা), আর গড় ratio সাধারণত bound-এর চেয়ে অনেক কম — এটাই approximation algorithm-এর বাস্তব ব্যবহারের সাধারণ চিত্র: worst-case bound একটা নিরাপত্তা-গ্যারান্টি, সাধারণ instance-এ প্রায়ই ফলাফল আরো ভালো হয়।

নিজে বাড়ান: এমন একটা graph পরিবার বানানোর চেষ্টা করুন (হাতে, নির্মিতভাবে) যেখানে ratio 2.00-এর যত কাছাকাছি সম্ভব পৌঁছায় — ইঙ্গিত: বহু disjoint “স্টার” গ্রাফ (একটা কেন্দ্র, বহু leaf) একসাথে জোড়া লাগিয়ে দেখুন, যেখানে greedy leaf-node বাছতে “বাধ্য” হয়।

এটা কী প্রমাণ করে

Greedy matching-based algorithm-এর measured approximation ratio বহু random graph-এ কখনোই তাত্ত্বিক upper bound (2) অতিক্রম করে না — একটা প্রমাণিত worst-case গ্যারান্টি পরীক্ষামূলকভাবে যাচাই।

নিজে বানান

BUILD IT

Amplification দেখুন — Monte Carlo error কীভাবে অদৃশ্য হয়ে যায়

Python · ●●●○○

একটা ইচ্ছাকৃতভাবে ভুল-প্রবণ (৩০% error) randomized decision procedure বানান
একে k-বার independently চালিয়ে majority vote নিন
k বাড়ানোর সাথে সাথে actual measured error rate পরিমাপ করুন
Chernoff bound-এর তাত্ত্বিক প্রেডিকশনের সাথে তুলনা করুন

import random

def noisy_oracle(true_answer, error_rate=0.3):
    """সত্যিকার উত্তর জানে, কিন্তু error_rate সম্ভাবনায় ভুল বলে —
    একটা কাল্পনিক BPP algorithm-এর simulation"""
    if random.random() < error_rate:
        return not true_answer
    return true_answer

def amplified_oracle(true_answer, k, error_rate=0.3):
    votes = [noisy_oracle(true_answer, error_rate) for _ in range(k)]
    return sum(votes) > k / 2  # majority

random.seed(11)
TRUE_ANSWER = True
N_TRIALS = 5000

print(f"{'k':>5} {'measured error':>16} {'তাত্ত্বিক আনুমানিক':>20}")
import math
for k in [1, 3, 7, 15, 31, 63, 127]:
    wrong = sum(1 for _ in range(N_TRIALS) if amplified_oracle(TRUE_ANSWER, k) != TRUE_ANSWER)
    measured = wrong / N_TRIALS
    # Chernoff-এর সরলীকৃত আনুমানিক রূপ (illustrative constant সহ)
    theoretical = math.exp(-0.1 * k)  # illustrative, প্রকৃত constant error_rate-এর উপর নির্ভরশীল
    print(f"{k:>5} {measured:>16.5f} {theoretical:>20.5f}")

প্রত্যাশিত (illustrative) প্যাটার্ন:

    k   measured error   তাত্ত্বিক আনুমানিক
    1           0.30200              0.90484
    3           0.16400              0.74082
    7           0.05600              0.49659
   15           0.00680              0.22313
   31           0.00040              0.04479
   63           0.00000              0.00181
  127           0.00000              0.00000

লক্ষ্য করুন প্যাটার্নটা: k = 1 থেকে k = 127 পর্যন্ত measured error প্রায় 30% থেকে অ-পরিমাপযোগ্য পর্যায়ে নেমে গেছে — সূচকীয় হ্রাস, রৈখিক নয়। এটাই ব্যাখ্যা করে কেন BPP-এর সংজ্ঞায় নির্দিষ্ট constant (1/3 বনাম 2/3) আসলে গুরুত্বপূর্ণ নয় — যেকোনো constant gap (1/2-এর চেয়ে বেশি সঠিক হলেই) amplification দিয়ে যেকোনো কাঙ্ক্ষিত নির্ভুলতায় নেওয়া যায়, polynomial সংখ্যক repetition-এই।

নিজে বাড়ান:

error_rate = 0.49 (প্রায় coin-flip-এর কাছাকাছি) দিয়ে চালান — দেখুন k কত বড় করতে হয় একই নির্ভুলতা পেতে, আর কেন error_rate = 0.5-এ amplification সম্পূর্ণ ব্যর্থ হয় (ইঙ্গিত: 0.5-এ randomized algorithm-টা কোনো তথ্যই দিচ্ছে না, বিশুদ্ধ coin flip)
algorithms/randomized-algorithms লেসনের Miller-Rabin primality test-এ এই একই amplification কৌশল প্রয়োগ করে দেখুন কতগুলো witness পরীক্ষা করলে একটা ভুল “মৌলিক” রায়ের সম্ভাবনা 10^{-30}-এর নিচে নামে
প্লট করুন k বনাম \log(\text{error}) — একটা সরলরেখা পাওয়া উচিত, কারণ সূচকীয় হ্রাস log-scale-এ রৈখিক দেখায়

বাস্তব সিস্টেমে

NP-hardness-এর সাথে বাস্তব সিস্টেমের তিনটা বসবাসের কৌশল

কৌশল ১ — Provable approximation, যখন গ্যারান্টি জরুরি। Cloud provider-দের load balancing (bin-packing-এর একটা রূপ) প্রায়ই provable-ratio heuristic ব্যবহার করে (First-Fit-Decreasing-এর মতো, যার 11/9-approximation প্রমাণিত) — কারণ SLA (Service Level Agreement) নিশ্চয়তা দিতে হয় যে resource ব্যবহার একটা নির্দিষ্ট সীমার বেশি খারাপ হবে না।

কৌশল ২ — Randomization, যখন average-case performance যথেষ্ট। Randomized quicksort, hash table-এর randomized hashing, বড় ডেটাতে randomized sampling দিয়ে quantile estimation (এই সব algorithms/randomized-algorithms লেসনের বিষয়) — Big data system-এ (Spark, ক্লিকস্ট্রিম analytics) সুনির্দিষ্ট নিশ্চয়তার বদলে “সাধারণত দ্রুত, আর কতটা ভুল হতে পারে তা bounded” দিয়েই কাজ চলে।

কৌশল ৩ — Heuristic + exact solver hybrid, যখন industrial-strength সমাধান দরকার। আধুনিক SAT solver (এই module-এর প্রজেক্ট — DPLL, CDCL) আর ILP solver (Gurobi, CPLEX) কোনো provable approximation ratio দেয় না — বরং তারা branch-and-bound দিয়ে exact optimal খোঁজে, কিন্তু clever heuristic branching, clause learning, আর cutting plane দিয়ে বাস্তব instance-এ exponential worst-case এড়িয়ে যায় (worst-case-এ এখনো exponential, কিন্তু বাস্তব industrial instance-এ প্রায়ই সেকেন্ডে সমাধান)। Chip design (EDA), airline crew scheduling, supply chain optimization — এই সব শিল্পক্ষেত্র মূলত এই hybrid পদ্ধতির উপর দাঁড়িয়ে আছে।

PCP theorem-এর একটা আধুনিক উত্তরাধিকার — zk-SNARK/zk-STARK। Blockchain-এ ব্যবহৃত succinct zero-knowledge proof system সরাসরি PCP theorem-এর ধারণা ব্যবহার করে — একটা বড় গণনা সঠিকভাবে হয়েছে তা প্রমাণ করতে পুরো গণনা “verify” করার বদলে, প্রমাণটাকে PCP-ধাঁচের এনকোডিং-এ রূপান্তর করে মাত্র কয়েকটা এলোমেলো বিন্দু চেক করেই উচ্চ সম্ভাবনায় নিশ্চিত হওয়া যায় — Cook-Levin-এর “গণনা = formula” ধারণা (আগের লেসন) আর PCP-এর “robust encoding” ধারণা একসাথে মিলে আজকের blockchain scalability সমাধানের গাণিতিক ভিত্তি তৈরি করেছে।

Machine learning training। Stochastic Gradient Descent (SGD) — deep learning-এর মূল optimization পদ্ধতি — নিজেই একটা randomized algorithm: প্রতি ধাপে ডেটার একটা random subset (mini-batch) ব্যবহার করে gradient আনুমানিক হিসাব করা হয়, পুরো dataset নয়। এটা কোনো provable approximation ratio দেয় না (loss landscape non-convex), কিন্তু ব্যবহারিকভাবে এটাই কাজ করে — এই module-এর “AI/ML foundations” লেসনে এই সংযোগ আরো গভীরভাবে আসবে।

যে ভুলগুলো সবাই করে

“Approximation algorithm মানে 'একটা heuristic যা সাধারণত ভালো কাজ করে' — কোনো প্রকৃত গ্যারান্টি নেই।”

সম্পূর্ণ বিপরীত — এটাই approximation algorithm-কে সাধারণ heuristic থেকে আলাদা করে।

একটা প্রকৃত α-approximation algorithm একটা গাণিতিকভাবে প্রমাণিত worst-case bound দেয় — এই লেসনের Vertex Cover প্রমাণে দেখা গেছে, A(x) \le 2 \cdot \mathrm{OPT}(x) প্রতিটা সম্ভাব্য instance-এর জন্য সত্য, কোনো ব্যতিক্রম ছাড়া। এটা “সাধারণত ভালো” নয় — এটা “সবসময় এই সীমার মধ্যে, প্রমাণসহ”।

একটা সাধারণ heuristic (যেমন “sorted order-এ greedy করুন” কোনো formal analysis ছাড়া) ভালো কাজ করতে পারে বেশিরভাগ instance-এ কিন্তু কিছু adversarial instance-এ arbitrarily খারাপ হতে পারে — কোনো bound নেই। Approximation algorithm-এর সংজ্ঞাই দাবি করে একটা প্রমাণ, যা এটাকে science-এর কাছাকাছি নিয়ে আসে, শুধু engineering trick নয়।

“Randomized algorithm অনির্ভরযোগ্য — deterministic algorithm সবসময় ভালো, যদি পাওয়া যায়।”

এই লেসনের amplification অংশ ঠিক এর বিপরীত দেখায়।

একটা BPP algorithm-এর error probability amplification দিয়ে এত ক্ষুদ্র করা যায় (10^{-40} বা তার চেয়েও ছোট) যে এটা hardware ব্যর্থতা, cosmic ray bit-flip, বা এমনকি deterministic algorithm-এর নিজের কোডে থাকা un-caught bug-এর সম্ভাবনার চেয়েও নির্ভরযোগ্য হয়ে যায়। “Randomized” মানে “অনির্ভরযোগ্য” নয় — এটা মানে “নির্ভুলতা একটা tunable parameter, যত ইচ্ছা টাকা (extra computation) খরচ করে বাড়ানো যায়”।

আরেকটা বাস্তব কারণ randomized algorithm প্রায়ই পছন্দ করা হয়: কিছু সমস্যায় (যেমন প্রাইমালিটি টেস্টিং-এর ঐতিহাসিক অবস্থা, deterministic polynomial algorithm (AKS) পাওয়ার আগে) randomized algorithm-ই ছিল একমাত্র পরিচিত দ্রুত পদ্ধতি — আর এমনকি এখন, randomized সংস্করণ প্রায়ই deterministic সংস্করণের চেয়ে অনেক দ্রুত ব্যবহারিকভাবে।

“PCP theorem বলছে প্রমাণ (proof) দীর্ঘ ও জটিল করা লাগবে, তাই এটা ব্যবহারিকভাবে খারাপ একটা ফলাফল।”

PCP theorem-এর তাৎপর্য ঠিক উল্টো দিকে — এটা একটা শক্তিশালী, ইতিবাচক সরঞ্জাম, “খারাপ খবর” নয়।

হ্যাঁ, PCP-এনকোডেড প্রমাণ মূল প্রমাণের চেয়ে দীর্ঘ (polynomial factor-এ) — কিন্তু বিনিময়ে যা পাওয়া যায় তা বিস্ময়কর: verifier-কে পুরো প্রমাণ পড়তেই হয় না, মাত্র O(1) bit পড়ে উচ্চ-সম্ভাবনায় সিদ্ধান্ত নিতে পারে। এই “sub-linear verification” ক্ষমতাই আজকের zk-SNARK/zk-STARK প্রযুক্তির (আগের অংশে আলোচিত) ভিত্তি — যেখানে একটা বিশাল গণনার সঠিকতা একটা ছোট, দ্রুত-যাচাইযোগ্য প্রমাণ দিয়ে প্রতিষ্ঠিত করা যায়।

তাত্ত্বিক দিক থেকেও PCP theorem শক্তিশালী কারণ এটা inapproximability প্রমাণের একটা সম্পূর্ণ নতুন হাতিয়ার দিয়েছে (এই লেসনের gap-producing reduction) — জটিলতা তত্ত্বের একটা সবচেয়ে গভীর ও ফলপ্রসূ আবিষ্কার, যার প্রভাব cryptography থেকে blockchain পর্যন্ত ছড়িয়ে আছে।

বুঝেছেন কি না দেখুন

একটা graph-এ greedy matching-based Vertex Cover algorithm 5-টা matching edge বাছল। এই তথ্য থেকে \mathrm{OPT}(G)-এর একটা lower bound আর algorithm-এর output size-এর একটা upper bound বলুন।

প্রয়োগ

Lower bound (OPT-এর উপর): \mathrm{OPT}(G) \ge 5 — কারণ ৫টা matching edge পরস্পর disjoint, তাই যেকোনো বৈধ cover-কে প্রতিটার জন্য অন্তত একটা আলাদা node ব্যবহার করতেই হবে (একটা node দুইটা disjoint edge একসাথে ঢাকতে পারে না)।

Algorithm output size: A(G) = 2 \times 5 = 10 (প্রতিটা matching edge থেকে দুইটা node যোগ হয়)।

Ratio bound: A(G) / \mathrm{OPT}(G) \le 10 / 5 = 2 — লক্ষ্য করুন এখানে প্রকৃত \mathrm{OPT}(G) হয়তো 5-এর চেয়ে বড়ও হতে পারে (matching size শুধু একটা lower bound, exact মান নয়) — তাই প্রকৃত ratio 2-এর চেয়ে কম বা সমান হবে, এই উদাহরণ শুধু worst-case সম্ভাবনা দেখাচ্ছে।

Set Cover-এর greedy algorithm-এর ratio (\ln n) Vertex Cover-এর greedy algorithm-এর ratio (2, একটা constant) থেকে গুণগতভাবে আলাদা। কেন এই পার্থক্যটা তাৎপর্যপূর্ণ — বড় n-এর ক্ষেত্রে এর ব্যবহারিক প্রভাব কী?

যুক্তি

Vertex Cover-এর 2-approximation নিশ্চিত করে output সবসময় optimal-এর দ্বিগুণের বেশি না, n (node সংখ্যা) যতই বড় হোক — একটা fixed, instance-size-নির্বিশেষ গ্যারান্টি।

Set Cover-এর \ln n-approximation-এর গ্যারান্টি n-এর সাথে ক্ষয়িষ্ণু — n = 10-এ ratio \approx 2.3, কিন্তু n = 10^6-এ ratio \approx 13.8, n = 10^9-এ \approx 20.7। যদিও \ln n খুব ধীরে বাড়ে (logarithmic), তবুও এটা মানে বড় universe-এ greedy-র গ্যারান্টি আনুপাতিকভাবে দুর্বল হয়ে যায় — একটা 20×-এর কাছাকাছি worst-case ratio ব্যবহারিকভাবে অনেক বড় গ্যাপ হতে পারে।

ব্যবহারিক প্রভাব: এই পার্থক্যটাই ব্যাখ্যা করে কেন Set Cover-এর জন্য গবেষকরা এত বছর ধরে constant-factor approximation খুঁজেছিলেন (ব্যর্থ হয়ে, কারণ এই লেসনের PCP-based ফলাফল অনুযায়ী এটা NP-hard) — Vertex Cover-এর জন্য এই একই প্রশ্নের উত্তর সহজেই “হ্যাঁ, 2” (যদিও 2-এর চেয়ে ভালো constant পাওয়া নিজেই একটা বিখ্যাত খোলা প্রশ্ন — উপরের Figure-এ উল্লেখিত 1.36 lower bound)। দুইটা সমস্যাই NP-hard, কিন্তু তাদের “approximability profile” সম্পূর্ণ ভিন্ন — এই পার্থক্যটা চেনাই approximation algorithm ডিজাইনের একটা কেন্দ্রীয় দক্ষতা।

BPP-এর সংজ্ঞায় error bound 1/3 ব্যবহার করা হয়েছে, কিন্তু বলা হয়েছে যেকোনো constant > 1/2 accuracy কাজ করবে। কেন ঠিক 1/2-এ amplification ভেঙে পড়ে (আগের BuildIt-এর ইঙ্গিত অনুযায়ী), গাণিতিক যুক্তি দিন।

যুক্তি

Majority-vote amplification-এর মূল ভিত্তি হলো: প্রতিটা independent trial সত্য উত্তরের দিকে একটা সামান্য bias রাখে (accuracy 1/2-এর চেয়ে বেশি)। যত বেশি trial নেওয়া হয়, majority সেই bias-এর দিকে “concentrate” করে — এটাই Chernoff/Hoeffding bound-এর মূল বক্তব্য, যা নির্ভর করে গড়ের চারপাশে বিচ্যুতি (deviation) নিয়ন্ত্রণ করার উপর, যা নিজে নির্ভর করে bias-এর (p - 1/2, যেখানে p হলো সঠিক উত্তরের সম্ভাবনা) অস্তিত্বের উপর।

p = 1/2-এ bias শূন্য — প্রতিটা trial সঠিক উত্তরের ব্যাপারে কোনো তথ্যই বহন করে না, এটা বিশুদ্ধ coin flip-এর সমতুল্য। k-টা এমন trial নিলেও majority vote ৫০-৫০ সম্ভাবনায় থাকবে (symmetric random walk-এর মতো, কোনো drift নেই) — k যতই বাড়ান, error ঠিক 1/2-এই থেকে যাবে, কমবে না। গাণিতিকভাবে, Chernoff bound-এর exponent bias-এর বর্গের সমানুপাতিক (\propto (p - 1/2)^2) — p \to 1/2 হলে এই exponent শূন্যের দিকে যায়, তাই bound-টা অর্থহীন (কোনো decay guarantee থাকে না) হয়ে পড়ে।

এটাই ব্যাখ্যা করে কেন BPP-এর সংজ্ঞায় কোনো fixed constant > 1/2 ব্যবহার করা যায় (2/3, 0.51, 0.9999 — সবই সমতুল্য class দেয়, শুধু amplification-এ প্রয়োজনীয় k-এর সংখ্যা ভিন্ন হবে) — কিন্তু 1/2 নিজে একটা অতিক্রমণীয় (unreachable) সীমা, কারণ সেখানে কোনো bias-ই নেই বাড়ানোর জন্য।

আপনাকে একটা নতুন optimization সমস্যা দেওয়া হলো যা NP-hard বলে প্রমাণিত। ব্যবহারিক সমাধানের জন্য এগোনোর আগে, এই লেসনের কাঠামো ব্যবহার করে তিনটা প্রশ্ন তালিকা করুন যা আপনি প্রথমে জিজ্ঞাসা করবেন — প্রতিটা প্রশ্নের উত্তর কোন দিকে সিদ্ধান্ত নিয়ে যায় তাও বলুন।

ডিজাইন

প্রশ্ন ১ — “একটা provable constant-factor approximation কি জানা আছে, বা খুঁজে পাওয়া সম্ভব?” যদি হ্যাঁ (Vertex Cover-এর মতো), সেই algorithm ব্যবহার করুন — গ্যারান্টিসহ দ্রুত সমাধান, যেখানে worst-case বিশ্লেষণযোগ্য loss মেনে নেওয়া চলে (SLA-জাতীয় প্রয়োজনে আদর্শ)।

প্রশ্ন ২ — “এই সমস্যার inapproximability সীমা কি জানা (PCP-based ফলাফল)?” যদি “না, ভালো approximation NP-hard” (Max-Clique-এর মতো), তাহলে exact approximation-guarantee খোঁজায় বেশি সময় নষ্ট না করে সরাসরি heuristic বা randomized পদ্ধতিতে যান — জেনে রাখুন কোনো provable ভালো bound পাওয়ার আশা নেই।

প্রশ্ন ৩ — “সমস্যাটাতে কি randomization স্বাভাবিকভাবে প্রয়োগযোগ্য (যেমন সমাধানের গুণমান একটা probabilistic guarantee দিয়ে যথেষ্ট)?” যদি হ্যাঁ, একটা randomized algorithm বিবেচনা করুন (Monte Carlo, sampling-based) — amplification দিয়ে যেকোনো কাঙ্ক্ষিত নির্ভরযোগ্যতায় আনা যাবে, প্রায়ই deterministic/exact পদ্ধতির চেয়ে অনেক দ্রুত।

সাধারণ সিদ্ধান্ত-গাছ: provable approximation থাকলে সেটাই প্রথম পছন্দ (predictable worst-case); inapproximable হলে heuristic/ML-ভিত্তিক পদ্ধতিতে যান (average-case ভালো, worst-case-এ কোনো প্রতিশ্রুতি নেই); randomization যেখানেই প্রযোজ্য, সেখানে amplification-এর সাশ্রয়ী নির্ভরযোগ্যতা কাজে লাগান। এই তিনটা প্রশ্নই আসলে এই লেসনের তিনটা প্রধান section-এর (approximation, PCP/inapproximability, randomization) সরাসরি প্রয়োগ।

এরপর কী

আমরা P, NP, co-NP, PSPACE-এর সংজ্ঞা থেকে শুরু করে (Cook-Levin theorem দিয়ে) NP-completeness-এর কাঠামো, তারপর P বনাম NP-এর গভীর তাৎপর্য, আর অবশেষে বাস্তব জগৎ কীভাবে NP-hardness-এর সাথে বসবাস করে — একটা সম্পূর্ণ চক্র সম্পন্ন করেছি।

কিন্তু “সমস্যা কতটা কঠিন” জানাই যথেষ্ট নয় — একটা প্রকৃত সিস্টেম (একটা distributed database, একটা concurrent scheduler, একটা security protocol) সঠিকভাবে তৈরি হয়েছে তা কীভাবে নিশ্চিত করব, যখন সব সম্ভাব্য input বা সব সম্ভাব্য thread-interleaving হাতে পরীক্ষা করা অসম্ভব? পরের লেসনগুলোতে আমরা প্রবেশ করব formal methods-এর জগতে — Hoare logic দিয়ে program-এর correctness গাণিতিকভাবে প্রমাণ করা, আর model checking/TLA+ দিয়ে সম্পূর্ণ state-space স্বয়ংক্রিয়ভাবে explore করে bug ধরা, exhaustive টেস্টিং ছাড়াই।

Approximation ও Randomized Complexity — যখন নিখুঁত উত্তর অপেক্ষা করতে পারে না

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Approximation ratio — ‘কতটা খারাপ হতে পারে’ তার একটা সংখ্যা

Vertex Cover — একটা 2-approximation, হাতে-কলমে

Set Cover — greedy, কিন্তু ratio ভিন্ন চরিত্রের

BPP — bounded-error randomization

Error amplification — কেন “১/৩ ভুল” আসলে ব্যবহারিকভাবে “প্রায় শূন্য ভুল”

ভেতরে কী ঘটছে

PCP theorem — কেন কিছু সমস্যায় ‘প্রায়’ খোঁজাও কঠিন

PCP থেকে inapproximability — ‘gap-producing reduction’

উদাহরণ

Vertex Cover approximation — একটা সম্পূর্ণ concrete উদাহরণ

নিজে চালিয়ে দেখুন

Greedy Vertex Cover-এর ratio পরিমাপ — বনাম brute-force optimal

নিজে বানান

Amplification দেখুন — Monte Carlo error কীভাবে অদৃশ্য হয়ে যায়

বাস্তব সিস্টেমে

NP-hardness-এর সাথে বাস্তব সিস্টেমের তিনটা বসবাসের কৌশল

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Approximation ratio — ‘কতটা খারাপ হতে পারে’ তার একটা সংখ্যা

Vertex Cover — একটা 2-approximation, হাতে-কলমে

Set Cover — greedy, কিন্তু ratio ভিন্ন চরিত্রের

BPP — bounded-error randomization

Error amplification — কেন “১/৩ ভুল” আসলে ব্যবহারিকভাবে “প্রায় শূন্য ভুল”

⚙ভেতরে কী ঘটছেUnder the hood

PCP theorem — কেন কিছু সমস্যায় ‘প্রায়’ খোঁজাও কঠিন

PCP থেকে inapproximability — ‘gap-producing reduction’

▶উদাহরণExample

Vertex Cover approximation — একটা সম্পূর্ণ concrete উদাহরণ

⌘নিজে চালিয়ে দেখুনExperiment

Greedy Vertex Cover-এর ratio পরিমাপ — বনাম brute-force optimal

⚒নিজে বানানBuild it yourself

Amplification দেখুন — Monte Carlo error কীভাবে অদৃশ্য হয়ে যায়

◉বাস্তব সিস্টেমেReal-world usage

NP-hardness-এর সাথে বাস্তব সিস্টেমের তিনটা বসবাসের কৌশল

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী