এই পর্বে যা শিখবেন
- Parameterized problem, FPT আর XP-এর নিখুঁত সংজ্ঞা, আর কেন f(k) · nc আর nk এক জিনিস নয়
- Vertex cover-এর bounded search tree আর Buss kernel, প্রমাণসহ, আর “kernel থাকা ⇔ FPT” উপপাদ্য
- Parameterized reduction, W-hierarchy, k-CLIQUE-এর W[1]-কঠিনতা আর color coding
- ETH, SETH, sparsification আর তাদের থেকে আসা শর্তসাপেক্ষ নিম্নসীমা
- SETH থেকে Orthogonal Vectors হয়ে edit distance পর্যন্ত reduction-এর শিকল, আর 3SUM ও APSP অনুমান
১ · একটি সংখ্যার বদলে দুটি — parameterized সমস্যা, XP আর FPT
বাজারঘর ঢাকায় নিজের delivery রাস্তার নকশা বানিয়েছে: প্রতিটি মোড় একটি vertex, দুটি মোড়ের মধ্যে রাস্তা একটি edge. নিরাপত্তা দল চায় প্রতিটি রাস্তা অন্তত এক প্রান্তের মোড় থেকে CCTV ক্যামেরায় দেখা যাক। প্রশ্ন: বড়জোর k-টি মোড়ে ক্যামেরা বসিয়ে কি সব রাস্তা ঢাকা যায়? এটি হুবহু vertex cover সমস্যা, যা পর্ব ৫৯-এ NP-complete প্রমাণিত হয়েছে। তাহলে কি হাল ছেড়ে দিতে হবে?
লক্ষ করুন একটি বাস্তব তথ্য: নকশায় হয়তো দশ হাজার মোড়, কিন্তু বাজেট বড়জোর ২০টি ক্যামেরার। অর্থাৎ input-এর আকার n বিশাল, কিন্তু খোঁজা উত্তরের আকার k ছোট। ক্লাসিক complexity (পর্ব ৫৭–৬৩) শুধু n দিয়ে সময় মাপে। Parameterized complexity একটি দ্বিতীয় সংখ্যা যোগ করে আর জিজ্ঞেস করে: সূচকীয় বিস্ফোরণটি কি শুধু k-এর ঘাড়ে চাপানো যায়?
পরীক্ষার হলে ৫০০ জন পরীক্ষার্থী, আর সন্দেহ আছে যে বড়জোর ৩ জন নকল করছে। প্রতিটি “৩ জনের দল” আলাদা করে পরীক্ষা করলে দল লাগে প্রায় ২ কোটি, যা nk-এর মতো বাড়ে। কিন্তু একজন অভিজ্ঞ পরিদর্শক জানেন, প্রতিটি সন্দেহজনক জোড়ার অন্তত একজন দোষী; তিনি জোড়া ধরে ধরে দুটি পথে ভাবেন, আর তিন ধাপ পরেই থামেন। কাজ বাড়ে মোটামুটি 23 × (হলের আকার)। দ্বিতীয় পদ্ধতিটিই FPT-এর মূল ভাবনা।
একটি parameterized problem হলো একটি language L ⊆ Σ∗ × ℕ; এর instance (x, k), যেখানে k হলো parameter. n = |x| লিখি।
L fixed-parameter tractable (FPT), যদি একটি computable function f, একটি ধ্রুবক c আর একটি algorithm থাকে, যা প্রতিটি (x, k)-এর উত্তর f(k) · nc সময়ে দেয়। এমন সব L-এর শ্রেণির নামও FPT.
L XP-তে, যদি computable f আর g থাকে, যাতে সময় f(k) · ng(k). অর্থাৎ প্রতিটি স্থির k-এ polynomial, কিন্তু polynomial-এর সূচক k-এর সঙ্গে বাড়ে।
সংজ্ঞা থেকেই FPT ⊆ XP (g(k) = c ধ্রুবক নিলেই হয়)। Downey আর Fellows-এর তত্ত্বে FPT ⊊ XP-ও প্রমাণিত, পর্ব ৬৭-এর hierarchy theorem-এর মতো diagonalization দিয়ে। k-CLIQUE (“G-এ k আকারের clique আছে?”) স্পষ্টতই XP-তে: সব (n choose k) ≤ nkটি উপসেট পরীক্ষা করলেই হয়। Vertex cover-ও এভাবে XP-তে, কিন্তু অংশ ২-এ দেখবেন সেটি আরও ভালো, FPT-তে।
পার্থক্যটি সংখ্যায় কতটা বড়? নিচের JavaScript ব্লক n = 10000-এর জন্য তিনটি খরচ পাশাপাশি রাখে: সব k-উপসেট পরীক্ষার nk, সহজ FPT-এর 2k · n, আর vertex cover-এর জানা সেরা algorithm-গুলোর মাপের 1.2738k · n. সংখ্যাগুলো দশের ঘাত হিসেবে, আর এক মিনিটে প্রতি সেকেন্ডে 109 ধাপ ধরে “ok” বা “--” লেখা।
// XP (n^k) vs FPT (2^k * n) step counts, shown as powers of ten
const n = 10000; // a city-sized road graph
const budget = Math.log10(1e9 * 60); // one minute at 10^9 steps per second
const fmt = x => ("10^" + x.toFixed(1)).padStart(10);
const ok = x => (x <= budget ? "ok" : "--");
console.log(`n = ${n}, one-minute budget = 10^${budget.toFixed(1)} steps`);
console.log(" k n^k 2^k*n 1.28^k*n");
for (const k of [2, 4, 8, 16, 32, 64]) {
const xp = k * Math.log10(n);
const fpt = k * Math.log10(2) + Math.log10(n);
const best = k * Math.log10(1.2738) + Math.log10(n);
console.log(String(k).padStart(3) + fmt(xp) + " " + ok(xp) +
fmt(fpt) + " " + ok(fpt) + fmt(best) + " " + ok(best));
}আসল আউটপুট (ব্রাউজারের JavaScript):
n = 10000, one-minute budget = 10^10.8 steps
k n^k 2^k*n 1.28^k*n
2 10^8.0 ok 10^4.6 ok 10^4.2 ok
4 10^16.0 -- 10^5.2 ok 10^4.4 ok
8 10^32.0 -- 10^6.4 ok 10^4.8 ok
16 10^64.0 -- 10^8.8 ok 10^5.7 ok
32 10^128.0 -- 10^13.6 -- 10^7.4 ok
64 10^256.0 -- 10^23.3 -- 10^10.7 ok
nk k = 4-এই এক মিনিটের সীমা ছাড়ায়, আর k = 8-এ 1032 ধাপ, যা মহাবিশ্বের বয়সেও শেষ হবে না। 2k · n k = 16 পর্যন্ত আরামে চলে, আর ভালো ভিত্তি 1.2738 নিলে k = 64-ও এক মিনিটের মধ্যে। মনে রাখুন, এখানে ধ্রুবক আর ছোট polynomial গুণক বাদ দেওয়া; হিসাবটি বৃদ্ধির ধরন দেখানোর জন্য, কোনো প্রমাণ নয়। মূল শিক্ষা: সূচকে n থাকা (XP) আর সূচকে শুধু k থাকা (FPT)-এর ফারাক, polynomial আর exponential-এর ফারাকের মতোই নাটকীয়।
২ · Bounded search tree — vertex cover O(2k · m) সময়ে
মূল পর্যবেক্ষণটি এক লাইনের, কিন্তু পুরো algorithm তার ওপর দাঁড়িয়ে।
G-এর যেকোনো vertex cover S আর যেকোনো edge {u, v}-এর জন্য u ∈ S অথবা v ∈ S. তাই (G, k) YES ⇔ (G − u, k − 1) YES অথবা (G − v, k − 1) YES. এখানে G − u মানে u আর তার সব edge মুছে ফেলা graph.
প্রমাণ:
- প্রথম অংশ সংজ্ঞা থেকে: S প্রতিটি edge-এর অন্তত এক প্রান্ত ছোঁয়, তাই {u, v}-এরও।
- (⇒) ধরুন S, |S| ≤ k, একটি cover, আর u ∈ S (ধাপ ১-এ দুটির একটি থাকবেই)। G − u-এর প্রতিটি edge G-এরও edge, আর u-কে ছোঁয় না, তাই S − {u} তাকে ঢাকে। |S − {u}| ≤ k − 1, অর্থাৎ (G − u, k − 1) YES.
- (⇐) ধরুন S′ হলো G − u-এর একটি cover, |S′| ≤ k − 1. তাহলে S′ ∪ {u} G-এর প্রতিটি edge ঢাকে: u-কে ছোঁয়া edge-গুলো u দিয়ে, বাকিগুলো S′ দিয়ে। আকার ≤ k. v-এর ক্ষেত্রেও একই। ∎
এই লেমা থেকে bounded search tree algorithm সরাসরি আসে: VC(G, k) = “G-এ কোনো edge না থাকলে YES; k = 0 হলে NO; নইলে যেকোনো edge {u, v} নিয়ে VC(G − u, k − 1) বা VC(G − v, k − 1)”. লেমা ২.১-এর ওপর k-তে induction দিলে সঠিকতা আসে।
Vertex cover (parameter k) O(2k · (n + m)) সময়ে সমাধান করা যায়; তাই এটি FPT.
প্রমাণ: প্রতিটি recursive call k এক কমায়, আর k = 0-তে থামে, তাই খোঁজার গাছের গভীরতা ≤ k. প্রতিটি node-এর বড়জোর দুটি সন্তান, তাই node-সংখ্যা ≤ 1 + 2 + … + 2k = 2k+1 − 1. প্রতিটি node-এ কাজ একটি edge বাছা আর একটি vertex মোছা, adjacency list-এ O(n + m). গুণ করলে O(2k · (n + m)). ∎
এখন একটি ছোট নকশায় চালানো যাক। মোড় 1–6, রাস্তা {1,2}, {1,3}, {2,3}, {3,4}, {4,5}, {4,6}, বাজেট k = 3. Algorithm সবসময় তালিকার প্রথম বাকি edge নেয়, আর আগে বাঁ প্রান্ত চেষ্টা করে।
1edge নেই? YES2k = 0? NO3প্রথম edge {u, v} নিন4VC(G − u, k−1) নয়তো VC(G − v, k−1)
| cover S | |
| বাকি k | |
| বাকি edge | |
| node গোনা |
- শিকড়। S ফাঁকা, k = 3, ছয়টি edge বাকি। প্রথম edge {1, 2}: লেমা ২.১ বলে যেকোনো cover-এ 1 বা 2 আছেই, তাই দুটি শাখা। আগে বাঁ শাখা: 1 নেওয়া।
- 1 নেওয়া হলো। {1,2} আর {1,3} ঢাকা পড়ল, k = 2. বাকি edge-গুলোর প্রথমটি {2, 3}; আবার দুটি শাখা, আগে 2.
- 2 নেওয়া হলো। {2,3} ঢাকা পড়ল, k = 1. বাকি {3,4}, {4,5}, {4,6}; প্রথমটি {3, 4}. আগে 3 চেষ্টা।
- 3: ব্যর্থ পাতা। {3,4} ঢাকা, কিন্তু {4,5} আর {4,6} বাকি, অথচ k = 0. এই শাখা NO; algorithm ফিরে গিয়ে একই node-এর ডান শাখা, 4, চেষ্টা করে।
- 4: সফল পাতা। 4 নিলে {3,4}, {4,5}, {4,6} তিনটিই ঢাকা পড়ে; কোনো edge বাকি নেই। উত্তর YES, cover {1, 2, 4}. মাত্র ৫টি node দেখা হলো, যেখানে সীমা 24 − 1 = 15. Scratch-এ brute force মিলিয়েছে: সবচেয়ে ছোট cover-এর আকারও ৩।
ছবি ৭২.১ — ছোট নকশা আর তার খোঁজার গাছ
ওপরে graph G; নিচে k = 3-এ algorithm-এর গাছ। ভরাট বাক্স দেখা হয়েছে, ড্যাশ দেওয়া বাক্স দেখার দরকার পড়েনি।
এবার বড় graph-এ গুনে দেখা যাক। নিচের ব্লক এমন random graph বানায় যার একটি 6 আকারের cover আছে (প্রতিটি edge একটি গোপন cover-vertex ছোঁয়), m = 3n. তারপর k = 6 (উত্তর YES) আর k = 5 (উত্তর NO) দুটির জন্যই গাছের node গোনে, আর পাশে লেখে brute force কতগুলো k-উপসেট পরীক্ষা করত।
# Bounded search tree for VERTEX-COVER vs trying all k-subsets
import random
from math import comb
random.seed(72)
def planted(n, k, m): # a graph whose vertex cover has size <= k
cover, E = random.sample(range(n), k), set()
while len(E) < m:
u, v = random.choice(cover), random.randrange(n)
if u != v: E.add((min(u, v), max(u, v)))
return sorted(E)
def vc(E, k, nodes): # True iff some cover of size <= k exists
nodes[0] += 1
if not E: return True
if k == 0: return False
u, v = E[0] # every cover contains u or v
return (vc([e for e in E if u not in e], k - 1, nodes) or
vc([e for e in E if v not in e], k - 1, nodes))
k = 6
print(f"k = {k}: tree bound 2^(k+1) - 1 = {2 ** (k + 1) - 1}")
print(" n m ask k answer tree nodes k-subsets C(n,k)")
for n in (20, 40, 80, 160, 320):
E = planted(n, k, 3 * n)
for ask in (k, k - 1):
nodes = [0]
ans = vc(E, ask, nodes)
print(f"{n:4} {len(E):4} {ask:6} {str(ans):6} {nodes[0]:10} {comb(n, ask):16}")আসল আউটপুট (ব্রাউজারের Python):
k = 6: tree bound 2^(k+1) - 1 = 127
n m ask k answer tree nodes k-subsets C(n,k)
20 60 6 True 126 38760
20 60 5 False 63 15504
40 120 6 True 64 3838380
40 120 5 False 63 658008
80 240 6 True 127 300500200
80 240 5 False 63 24040016
160 480 6 True 127 21193254160
160 480 5 False 63 820384032
320 960 6 True 127 1422630723360
320 960 5 False 63 27097728064
n ১৬ গুণ বাড়লেও (20 → 320) গাছের node কখনো 127 ছাড়ায়নি: এটিই 2k+1 − 1-এর সীমা। k = 5-এর NO-উত্তরে গাছটি পুরো খুঁজতে হয়, তবু ঠিক 63 = 26 − 1 node. অন্যদিকে সব k-উপসেট পরীক্ষা n = 320-এ ১.৪ লাখ কোটির বেশি। n-এর ভূমিকা এখন শুধু প্রতিটি node-এর edge-তালিকা ছাঁকায়, অর্থাৎ O(m). (একটি সূক্ষ্ম কথা: k = 6-এ graph-এ 6 আকারের cover লুকোনো আছে বলে উত্তর YES নিশ্চিত, কিন্তু k = 5-এ NO আসা এই নির্দিষ্ট random graph-গুলোর তথ্য, সাধারণ সত্য নয়।)
শাখার সংখ্যা কমিয়ে ভিত্তি 2 থেকে নামানো যায়। যেমন একটি vertex v-এর degree ≥ 3 হলে শাখা দুটি: “v নিন” (k − 1) অথবা “v-এর সব প্রতিবেশী নিন” (k − 3 বা কম); degree ≤ 2 হলে graph কয়েকটি path আর cycle, যা polynomial সময়ে সমাধান হয়। এতে recurrence T(k) ≤ T(k − 1) + T(k − 3), যার সমাধান প্রায় 1.4656k. বহু ধাপের এমন উন্নতির পর জানা সেরা ফলগুলোর একটি O(1.2738k + kn), যা Chen, Kanj আর Xia-র (২০১০) বলে উল্লেখ করা হয়। Algorithm-এর দিক থেকে এই কৌশল DSA কোর্সের পর্ব ৬৫-এও আছে; এখানে আমরা প্রমাণ আর শ্রেণির দিকে যাচ্ছি।
৩ · Kernelization — Buss-এর নিয়ম আর k2 আকারের kernel
দ্বিতীয় বড় কৌশলটি algorithm চালানোর আগের “ঝাড়পোঁছ”। বাজারঘরের নকশায় এমন মোড় আছে যেখান থেকে ৪০টি রাস্তা বের হয়েছে। বাজেট k = 8 হলে এই মোড়ে ক্যামেরা না বসালে ৪০টি রাস্তার প্রতিটির অন্য প্রান্তে আলাদা ক্যামেরা লাগত, অর্থাৎ ৪০টি; সেটা অসম্ভব। তাই এই মোড়টি বাধ্যতামূলক। এই ধরনের নিশ্চিত সিদ্ধান্তকে নিয়ম হিসেবে লিখলে আসে kernelization.
একটি parameterized problem L-এর kernel হলো একটি polynomial সময়ের algorithm, যা (x, k)-কে (x′, k′)-এ বদলায়, যাতে (১) (x, k) ∈ L ⇔ (x′, k′) ∈ L, আর (২) |x′| + k′ ≤ h(k), যেখানে h একটি computable function. h polynomial হলে বলে polynomial kernel.
Vertex cover-এর জন্য তিনটি নিয়ম, যা Jonathan Buss-এর নামে পরিচিত (Buss আর Judy Goldsmith-এর ১৯৯৩ সালের একটি প্রবন্ধ থেকে এসেছে বলে সাধারণত উল্লেখ করা হয়):
- নিয়ম ১ (একাকী vertex): degree 0-এর vertex মুছে ফেলুন; সে কোনো edge ঢাকে না।
- নিয়ম ২ (বড় degree): কোনো vertex v-এর degree > k হলে v-কে cover-এ নিন: G ← G − v, k ← k − 1. যতক্ষণ সম্ভব পুনরাবৃত্তি করুন।
- নিয়ম ৩ (আকারের পরীক্ষা): নিয়ম ১ আর ২ আর না খাটলে, যদি edge-সংখ্যা > k2 হয়, উত্তর NO.
নিয়ম ১–৩ polynomial সময়ে চলে আর একটি সমতুল্য instance (G′, k′) দেয়, যেখানে k′ ≤ k; উত্তর YES হলে G′-এ বড়জোর k′2টি edge আর k′2 + k′টি vertex. তাই vertex cover-এর বড়জোর k2টি edge আর k2 + k vertex-এর kernel আছে।
প্রমাণ:
- নিয়ম ১ নিরাপদ: একাকী vertex কোনো cover-এ দরকার নেই, তাই মুছলে উত্তর বদলায় না।
- নিয়ম ২ নিরাপদ: ধরুন S একটি cover, |S| ≤ k, আর v ∉ S. তাহলে v-এর প্রতিটি edge-এর অন্য প্রান্ত S-এ থাকতে হবে, অর্থাৎ |S| ≥ deg(v) > k, অসম্ভব। তাই k আকারের প্রতিটি cover-এ v আছে, আর লেমা ২.১-এর (⇒)/(⇐) যুক্তিতে (G, k) YES ⇔ (G − v, k − 1) YES.
- নিয়ম ৩ নিরাপদ: নিয়ম ২ না খাটলে প্রতিটি vertex-এর degree ≤ k′. k′ আকারের একটি cover S থাকলে প্রতিটি edge S-এর কোনো vertex ছোঁয়, তাই edge-সংখ্যা ≤ Σv∈S deg(v) ≤ k′ · k′ = k′2. বেশি হলে cover থাকতে পারে না।
- Vertex-সংখ্যা: নিয়ম ১-এর পর প্রতিটি vertex কোনো edge-এ আছে। প্রতিটি vertex হয় S-এ (বড়জোর k′টি), নয় S-এর কোনো vertex-এর প্রতিবেশী (বড়জোর k′ · k′টি)। মোট ≤ k′2 + k′.
- সময়: প্রতিবার নিয়ম ২ খাটলে k কমে, তাই বড়জোর k বার; প্রতিবার degree গোনা O(n + m). ∎
সীমাটি নিখুঁত: k-টি আলাদা তারা (star), প্রতিটির কেন্দ্রে k-টি পাতা, তাতে প্রতিটি degree ঠিক k, কোনো নিয়ম খাটে না, আর edge ঠিক k2, vertex ঠিক k2 + k. Scratch-এ k = 1 থেকে 5 পর্যন্ত এটি মিলিয়েছি, আর ৩০০০টি random ছোট graph-এ kernel-এর উত্তর brute force-এর সঙ্গে মিলেছে, প্রতিটি YES kernel-এ দুটি সীমাই খেটেছে। তাই “2k2 vertex” লেখা কিছু উৎস একটু ঢিলেঢালা সীমা দেয়; নিখুঁত সংখ্যা k2 + k.
1নিয়ম ২: deg(v) > k ⇒ v নিন, k − 12নিয়ম ১: একাকী vertex মুছুন3নিয়ম ৩: m > k² ⇒ NO4kernel-এ যেকোনো algorithm
| vertex | |
| edge | |
| k | |
| নেওয়া |
- শুরু। একটি বড় মোড় H, যার সঙ্গে ৫টি ছোট গলি p1–p5; একটি চার-মোড়ের চক্র a–b–c–d–a; আর একটি বিচ্ছিন্ন মোড় x. মোট ১১টি vertex, ৯টি edge, k = 3. H-এর degree 5 > 3, তাই নিয়ম ২ খাটে।
- নিয়ম ২: H নেওয়া হলো। H না নিলে ৫টি গলির অন্য প্রান্তে ৫টি ক্যামেরা লাগত, যা k = 3-এর বেশি। H মুছে k = 2; এখন প্রতিটি degree ≤ 2, তাই নিয়ম ২ আর খাটে না।
- নিয়ম ১: একাকীদের বিদায়। p1–p5 এখন কোনো edge-এ নেই, x শুরু থেকেই নেই। ছয়টি vertex মুছে গেল; বাকি শুধু 4-cycle: ৪টি vertex, ৪টি edge.
- নিয়ম ৩: আকার পরীক্ষা। edge-সংখ্যা 4 ≤ k2 = 4, তাই NO বলা যায় না। (G′, k′) = (4-cycle, 2) হলো kernel; vertex 4 ≤ k′2 + k′ = 6.
- Kernel সমাধান। ছোট kernel-এ অংশ ২-এর search tree বা brute force চালানো যায়: 4-cycle-এর cover {a, c}. মূল উত্তর YES, cover {H, a, c}, আকার 3. (Scratch-এ মূল graph-এ brute force-ও সবচেয়ে ছোট cover-এর আকার 3 দিয়েছে। শুরুতে k = 2 হলে H-এর পরে k = 1, তখন চক্রের প্রতিটি vertex-এর degree 2 > 1, তাই একটি জোর করে নেওয়া হয়, k = 0, অথচ edge বাকি: NO.)
বড় instance-এ kernel কতটা ছাঁটে, দেখা যাক। নিচের নকশায় ৪০০টি মোড়, চারটি বড় hub, প্রতিটি ৪০টি গলির সঙ্গে যুক্ত, আর আটটি দোকান একটি চক্রে, সঙ্গে একটি আড়াআড়ি রাস্তা।
# Buss kernel for VERTEX-COVER: shrink (G, k) to size bounded by k only
import random
def buss(E, k):
E, forced = set(E), []
while True:
deg = {}
for u, v in E:
deg[u] = deg.get(u, 0) + 1; deg[v] = deg.get(v, 0) + 1
big = [x for x in deg if deg[x] > k] # rule 2: degree > k
if not big or k <= 0: break
x = big[0]; forced.append(x); k -= 1
E = {e for e in E if x not in e}
too_big = k < 0 or len(E) > k * k # rule 3: too many edges
return (None if too_big else E), forced, k # rule 1: isolated gone
def vc(E, k):
if not E or k <= 0: return not E
u, v = next(iter(E))
return (vc({e for e in E if u not in e}, k - 1) or
vc({e for e in E if v not in e}, k - 1))
n, k = 400, 8; random.seed(7)
hubs, rest = range(4), list(range(4, n)) # 4 busy hubs
ring = random.sample(rest, 8) # 8 shops in a ring + 1 chord
E = {(min(h, x), max(h, x)) for h in hubs for x in random.sample(rest[8:], 40)}
E |= {(min(a, b), max(a, b)) for a, b in zip(ring, ring[1:] + ring[:1])}
E.add((min(ring[0], ring[4]), max(ring[0], ring[4])))
print(f"before: n = {n}, non-isolated = {len({x for e in E for x in e})}, m = {len(E)}, k = {k}")
K, forced, k2 = buss(E, k)
print(f"forced into cover: {len(forced)}, new k' = {k2}; kernel: "
f"{len({x for e in K for x in e})} vertices (bound {k2 * k2 + k2}), "
f"{len(K)} edges (bound {k2 * k2})")
print("answer on kernel:", vc(K, k2), "| answer on original:", vc(E, k))
for kk in (7, 6):
K, forced, k2 = buss(E, kk)
print(f"k = {kk}:", "kernel says NO" if K is None else f"kernel {len(K)} edges",
"| original:", vc(E, kk))আসল আউটপুট (ব্রাউজারের Python):
before: n = 400, non-isolated = 147, m = 169, k = 8
forced into cover: 4, new k' = 4; kernel: 8 vertices (bound 20), 9 edges (bound 16)
answer on kernel: True | answer on original: True
k = 7: kernel 9 edges | original: False
k = 6: kernel says NO | original: False
৪০০টি vertex (যার ১৪৭টি কোনো edge-এ আছে) আর ১৬৯টি edge থেকে kernel-এ রইল শুধু দোকানের চক্র: ৮টি vertex, ৯টি edge, দুটিই সীমার মধ্যে। চারটি hub নিয়ম ২-এ বাধ্যতামূলক হয়েছে। k = 7-এ kernel তৈরি হয় (9 ≤ 32), কিন্তু তাতে search tree NO বলে: আড়াআড়ি রাস্তাসহ আট-চক্রের cover-এ ৪টি vertex লাগে। অর্থাৎ নিয়ম ৩ সব NO ধরে না; kernel শুধু instance ছোট করে, বাকি কাজ পরের algorithm-এর। k = 6-এ নিয়ম ৩ নিজেই NO বলে, কারণ 9 > 22. প্রতিটি সারিতে kernel-এর উত্তর মূল graph-এর উত্তরের সঙ্গে মিলেছে।
একটি decidable parameterized problem FPT ⇔ তার একটি kernel আছে।
প্রমাণ: (⇐) Kernel polynomial সময়ে (x′, k′) দেয়, যার আকার ≤ h(k). যেকোনো decider সেটি কোনো g(h(k)) সময়ে সমাধান করে, যা শুধু k-এর function. মোট সময় poly(n) + g(h(k)) ≤ (1 + g(h(k))) · poly(n). (⇒) ধরুন algorithm A f(k) · nc সময়ে চলে। Kernel: A-কে nc+1 ধাপ চালান। থামলে উত্তর অনুযায়ী একটি স্থির ছোট YES বা NO instance লিখুন। না থামলে f(k) · nc > nc+1, অর্থাৎ n < f(k); তখন (x, k)-ই রেখে দিন, যার আকার এখন f(k)-এর মধ্যে বাঁধা। দুই ক্ষেত্রেই সময় polynomial আর আকার শুধু k দিয়ে বাঁধা। ∎
এই প্রমাণ দেখায় kernel-এর আকার f(k)-এর মতো বিশাল হতে পারে; তাই আসল প্রশ্ন হলো polynomial kernel আছে কি না। Vertex cover-এর জন্য আরও ছোট, 2k vertex-এর kernel জানা আছে (Nemhauser–Trotter-এর LP-ভিত্তিক ফল আর crown reduction থেকে)।
৪ · W-hierarchy — k-CLIQUE কেন আলাদা
পর্ব ৫৯-এ দেখেছেন, G-তে k আকারের vertex cover ⇔ G-তে n − k আকারের independent set ⇔ complement graph-এ n − k আকারের clique. Polynomial-time reduction-এর চোখে তিনটি সমস্যা সমান কঠিন। কিন্তু parameter-এর চোখে? k-INDEPENDENT-SET-এ k = 10 মানে “১০ জন পরস্পর-অপরিচিত মানুষ খুঁজুন”; তার জন্য vertex cover-টি n − 10 আকারের, আর 2n−10-এর গাছ কোনো কাজে আসে না। কয়েক দশকের চেষ্টাতেও k-CLIQUE বা k-INDEPENDENT-SET-এর FPT algorithm মেলেনি। এই পার্থক্য মাপার যন্ত্রটি নতুন ধরনের reduction.
A থেকে B-তে একটি parameterized reduction হলো একটি algorithm, যা (x, k)-কে f(k) · nc সময়ে (x′, k′)-এ বদলায়, যাতে (১) (x, k) ∈ A ⇔ (x′, k′) ∈ B, আর (২) k′ ≤ g(k), যেখানে g শুধু k-এর computable function. তাহলে B ∈ FPT ⇒ A ∈ FPT.
শর্ত (২) সবচেয়ে জরুরি। k-CLIQUE থেকে k-INDEPENDENT-SET-এ complement graph নেওয়া একটি parameterized reduction: k′ = k. কিন্তু INDEPENDENT-SET থেকে VERTEX-COVER-এ নেওয়া রূপান্তরটিতে k′ = n − k, যা n-এর ওপর নির্ভর করে, তাই এটি parameterized reduction নয়। এ কারণেই vertex cover FPT হলেও clique-কে টেনে নামায় না।
এই reduction দিয়ে Downey আর Fellows ১৯৯০-এর দশকে একটি শ্রেণির ধারা সাজান, যার নাম W-hierarchy:
FPT ⊆ W[1] ⊆ W[2] ⊆ … ⊆ XP
W[1]-এর একটি স্বাভাবিক বর্ণনা: “একটি nondeterministic Turing machine কি k ধাপের মধ্যে গ্রহণ করে?” (parameter k), এই সমস্যা আর তার দিকে parameterized reduction হওয়া সবকিছু। k-CLIQUE W[1]-complete বলে পরিচিত (Downey–Fellows, ১৯৯৫), তাই W[1]-এর “SAT”-এর ভূমিকায়। k আকারের dominating set (প্রতিটি মোড় হয় সেটে, নয় সেটের কোনো মোড়ের পাশে) W[2]-complete বলে পরিচিত।
প্রমাণিত আর অনুমান আলাদা রাখুন। FPT ⊊ XP প্রমাণিত। কিন্তু FPT ≠ W[1] একটি অনুমান, P ≠ NP-এর parameterized আত্মীয়। তাই “k-CLIQUE FPT নয়” লেখা ভুল; সঠিক লেখা: “k-CLIQUE W[1]-hard, তাই FPT ≠ W[1] সত্য হলে এটি FPT নয়।” অংশ ৫-এ দেখবেন, ETH সত্য হলে FPT ≠ W[1]-ও সত্য।
সব parameterized সমস্যা search tree বা kernel দিয়ে আসে না। একটি সুন্দর randomized কৌশল color coding (Alon, Yuster আর Zwick, ১৯৯৫): k দৈর্ঘ্যের একটি simple path খুঁজতে প্রতিটি vertex-কে k রঙের একটি random রং দিন, তারপর DP দিয়ে শুধু “সব রং আলাদা” path খুঁজুন; রং-এর উপসেট ধরে DP 2k · poly(n) সময় নেয়। একটি নির্দিষ্ট path-এর সব রং আলাদা হওয়ার সম্ভাবনা k!/kk ≥ e−k, তাই প্রায় ek বার পুনরাবৃত্তি করলে ভুলের সম্ভাবনা ধ্রুবকের নিচে নামে (পর্ব ৬৯-এর amplification). ফল: k-PATH 2O(k) · poly(n) সময়ে, FPT. লক্ষ করুন, k = n হলে এটি Hamiltonian path, যা NP-complete; তাই এখানেও কঠিনতা পুরোটাই k-তে।
৫ · ETH আর SETH — সূচকের মাপে কঠিনতা
P ≠ NP শুধু বলে “polynomial নয়”। কিন্তু 2n/100 বা nlog n-ও polynomial নয়, অথচ বাস্তবে অনেক ভালো। আরও সূক্ষ্ম প্রশ্নের জন্য পর্ব ৬৩-এ দুটি অনুমান এসেছিল; Russell Impagliazzo আর Ramamohan Paturi এদের ২০০১ সালে স্পষ্ট করেন।
ETH: এমন ধ্রুবক δ > 0 আছে, যাতে n চলকের 3SAT-এর কোনো algorithm 2δn সময়ের কমে চলে না।
SETH: প্রতিটি ε > 0-এর জন্য এমন k আছে, যাতে k-SAT O(2(1 − ε)n) সময়ে সমাধান করা যায় না।
ETH বলে সূচকীয় সময় লাগবেই, কিন্তু ভিত্তিটি 2 হতে হবে না: 1.3n ETH-এর সঙ্গে মেলে। SETH আরও শক্ত: clause-এর দৈর্ঘ্য k বাড়লে সেরা ভিত্তি 2-এর দিকে যায়, অর্থাৎ বড় k-তে brute force প্রায় সেরা। জানা আছে SETH ⇒ ETH ⇒ P ≠ NP; কোনোটিই প্রমাণিত নয়, আর SETH নিয়ে কিছু গবেষকের সন্দেহও আছে। তাই এদের থেকে পাওয়া প্রতিটি ফল একটি conditional lower bound: “অনুমান সত্য হলে এর চেয়ে দ্রুত সম্ভব নয়।”
একটি প্রযুক্তিগত বাধা আছে। 3SAT থেকে অন্য সমস্যায় reduction সাধারণত instance-এর আকার m (clause-সংখ্যা) দিয়ে মাপে, অথচ ETH n (চলক-সংখ্যা) দিয়ে লেখা, আর m n3 পর্যন্ত হতে পারে। Sparsification lemma (Impagliazzo, Paturi আর Zane, ২০০১) এই ফাঁক বন্ধ করে: প্রতিটি ε > 0-এর জন্য একটি k-CNF-কে 2εnটি k-CNF-এর OR হিসেবে লেখা যায়, যাদের প্রতিটিতে clause O(n). ফলে ETH ⇔ “3SAT 2o(n + m) সময়ে নয়”। এখান থেকে কয়েকটি সূক্ষ্ম পরিণাম:
- Vertex cover: পর্ব ৬১-এর 3SAT → VERTEX-COVER reduction রৈখিক আকারের, তাই ETH ⇒ vertex cover 2o(n) সময়ে নয়, আর k ≤ n বলে 2o(k) · nO(1) সময়েও নয়। অর্থাৎ অংশ ২-এর ck ধরনের algorithm-ই সেরা ধরন; শুধু ভিত্তি c কমানোর লড়াই।
- k-CLIQUE: ETH ⇒ k-CLIQUE f(k) · no(k) সময়ে নয় (Chen ও সহকর্মীদের ফল বলে পরিচিত)। তাই nk-এর brute force সূচকের দিক থেকে প্রায় সেরা, আর বিশেষত ETH ⇒ FPT ≠ W[1].
- Graph সমস্যা: ETH ⇒ 3-COLOR, HAMPATH-এর মতো বহু সমস্যা 2o(n) সময়ে নয়। এটি P ≠ NP-এর চেয়ে অনেক বেশি তথ্য দেয়।
৬ · Fine-grained complexity — SETH থেকে OV থেকে edit distance
এবার polynomial জগতে নামা যাক। বাজারঘরের সার্চ বক্সে কেউ “পেঁয়াজ” লিখতে গিয়ে ভুল বানান লিখলে সিস্টেম ক্যাটালগের নামের সঙ্গে edit distance মাপে: সবচেয়ে কম কয়টি অক্ষর যোগ, বাদ বা বদল লাগে। দৈর্ঘ্য n-এর দুটি string-এর জন্য পরিচিত dynamic programming টেবিল n × n, অর্থাৎ O(n2) (DSA কোর্সের পর্ব ৫৪)। প্রায় অর্ধশতাব্দীর চেষ্টাতেও কেউ O(n1.99) পাননি; শুধু log-গুণকের উন্নতি জানা (Masek আর Paterson, ১৯৮০)। কেন?
P বনাম NP এখানে কিছু বলে না: সমস্যাটি তো P-তে। Fine-grained complexity NP-completeness-এর কৌশল ধার করে polynomial সূচকের জন্য: একটি “কেন্দ্রীয়” অনুমান, আর সূচক রক্ষা করা fine-grained reduction. কেন্দ্রের সবচেয়ে কাজের সমস্যাটি:
Input: দুটি সেট A, B, প্রতিটিতে N-টি vector, প্রতিটি {0, 1}d-এ। প্রশ্ন: এমন a ∈ A, b ∈ B আছে কি, যাতে a · b = Σj a[j] · b[j] = 0, অর্থাৎ কোনো স্থানে দুটিতেই 1 নেই? Brute force O(N2 d). OV অনুমান: প্রতিটি ε > 0-এর জন্য এমন c আছে, যাতে d = c log N-এ OV O(N2−ε) সময়ে সমাধান করা যায় না।
SETH সত্য হলে OV অনুমানও সত্য। সমতুল্যভাবে: কোনো ε > 0-এর জন্য OV O(N2−ε · poly(d)) সময়ে সমাধান করা গেলে SETH মিথ্যা।
প্রমাণ:
- একটি k-CNF φ নিন, n চলক, m clause. Sparsification lemma দিয়ে m = O(n) ধরা যায় (কয়েকটি সূত্রের OR-এ ভাঙা, প্রতিটিতে আলাদা করে কাজ)।
- চলকগুলো দুই ভাগে ভাগ করুন: X1 (প্রথম n/2) আর X2 (বাকি n/2).
- X1-এর প্রতিটি মান-বসানো α-এর জন্য একটি vector aα ∈ {0, 1}m: aα[j] = 0 যদি α একাই clause Cj-কে সত্য করে, নইলে 1. একইভাবে X2-এর প্রতিটি β থেকে bβ. দুই সেটেই N = 2n/2টি vector, d = m.
- aα · bβ = 0 ⇔ প্রতিটি j-এ aα[j] = 0 অথবা bβ[j] = 0 ⇔ প্রতিটি clause α বা β-র কোনো একটি সত্য করে ⇔ পুরো মান-বসানো (α, β) φ-কে সত্য করে। তাই orthogonal জোড়া আছে ⇔ φ satisfiable.
- vector বানাতে সময় O(N · m · k). OV-কে O(N2−ε · poly(d)) সময়ে সমাধান করলে মোট সময় 2(n/2)(2−ε) · poly(n) = 2(1 − ε/2)n · poly(n), আর এটি প্রতিটি k-এর জন্য খাটে। SETH ε/2-এর চেয়ে একটু ছোট সংখ্যার জন্য এটি নিষেধ করে। ∎
একটি ছোট সূত্রে নির্মাণটি চালানো যাক: φ = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x3 ∨ ¬x4) ∧ (¬x2 ∨ ¬x3 ∨ x4). X1 = {x1, x2}, X2 = {x3, x4}; vector-এর তিনটি স্থান তিনটি clause.
1চলক দুই ভাগে: X1, X22bit j = 1 ⇔ clause j এখনো মিথ্যা3a · b = 0 ⇔ সব clause সত্য4N = 2^(n/2), d = m
| A (x1 x2) | |
| B (x3 x4) | |
| a · b |
- ভাগ। চারটি চলক দুই ভাগে। প্রতিটি ভাগে 22 = 4টি মান-বসানো, তাই প্রতিটি সেটে N = 4টি vector, প্রতিটির দৈর্ঘ্য d = 3 (clause-সংখ্যা)।
- সেট A. x1x2 = 00: C1-এ x1 আর x2 দুটিই মিথ্যা, তাই C1 বাকি (bit 1); C2 ¬x1 দিয়ে আর C3 ¬x2 দিয়ে সত্য (bit 0). Vector 100. একইভাবে 01 → 001, 10 → 010, 11 → 011.
- সেট B. x3x4-এর জন্য: 00 → 100 (C2, C3 সত্য: ¬x4, ¬x3), 01 → 110 (শুধু C3), 10 → 001 (C1, C2), 11 → 000 (তিনটিই)।
- একটি orthogonal জোড়া। a(00) = 100 আর b(10) = 001: কোনো স্থানে দুটিতেই 1 নেই, গুণফল 0. মিলিত মান x = 0010: C1 x3 দিয়ে, C2 ¬x1 দিয়ে, C3 ¬x2 দিয়ে সত্য।
- একটি অ-orthogonal জোড়া। a(00) = 100 আর b(00) = 100: প্রথম স্থানে দুটিতেই 1, গুণফল 1. অর্থ: কোনো অর্ধেকই C1 সত্য করে না, আর সত্যিই x = 0000-এ C1 = মিথ্যা।
- পুরো হিসাব। ১৬টি জোড়ার ১০টি orthogonal, আর φ-এর ঠিক ১০টি satisfying মান-বসানো আছে; scratch-এ দুটি তালিকা হুবহু মিলেছে। n চলকে N = 2n/2, তাই OV-এর N2 brute force ঠিক SAT-এর 2n brute force.
নিচের ব্লক একই নির্মাণ ২০০টি random 3-CNF-এ (n = 10) চালিয়ে brute-force SAT-এর সঙ্গে মেলায়, তারপর OV-এর N2 brute force-এর সময় দেখায়, এমন instance-এ যেখানে কোনো orthogonal জোড়া নেই (তাই সব জোড়া দেখতে হয়)।
# SAT -> Orthogonal Vectors (Williams 2005), checked by brute force
import random, time
from itertools import product
random.seed(2015)
def rand_cnf(n, m, w=3):
return [[v if random.random() < 0.5 else -v
for v in random.sample(range(1, n + 1), w)] for _ in range(m)]
def sat(cnf, n):
return any(all(any(a[abs(l) - 1] == (l > 0) for l in c) for c in cnf)
for a in product((0, 1), repeat=n))
def half_vectors(cnf, vars_): # bit j = 1 <=> clause j NOT yet satisfied
out = []
for a in product((0, 1), repeat=len(vars_)):
val = dict(zip(vars_, a))
out.append(sum(1 << j for j, c in enumerate(cnf)
if not any(abs(l) in val and val[abs(l)] == (l > 0) for l in c)))
return out
def has_orthogonal(A, B): # the O(N^2 d) brute force
return any(a & b == 0 for a in A for b in B)
n, agree, yes = 10, 0, 0
for t in range(200):
cnf = rand_cnf(n, random.randint(30, 50))
A = half_vectors(cnf, range(1, 6)); B = half_vectors(cnf, range(6, 11))
s = sat(cnf, n); yes += s
agree += (s == has_orthogonal(A, B))
print(f"200 random 3-CNF (n = 10): {len(A)} + {len(B)} vectors each; "
f"satisfiable {yes}; SAT == OV in {agree}/200")
for N in (500, 1000, 2000): # all pairs, no orthogonal pair planted
A = [random.getrandbits(40) | 1 for _ in range(N)]
t0 = time.perf_counter(); has_orthogonal(A, A)
print(f"N = {N:4}: {N * N:>8} pairs, {1000 * (time.perf_counter() - t0):6.0f} ms")আসল আউটপুট (ব্রাউজারের Python; শেষ তিন লাইনের মিলিসেকেন্ড আপনার যন্ত্রে আলাদা হবে):
200 random 3-CNF (n = 10): 32 + 32 vectors each; satisfiable 160; SAT == OV in 200/200
N = 500: 250000 pairs, 16 ms
N = 1000: 1000000 pairs, 63 ms
N = 2000: 4000000 pairs, 404 ms
২০০টি সূত্রের প্রতিটিতে “orthogonal জোড়া আছে” আর “সূত্র satisfiable” একই উত্তর দিয়েছে, satisfiable আর unsatisfiable দুই ধরনেই। প্রতিটি vector-এর bit 0-তে 1 বসানো, তাই শেষ পরীক্ষায় কোনো জোড়া orthogonal নয় আর সব N2 জোড়া দেখতে হয়: N দ্বিগুণ হলে জোড়া চারগুণ, আর সময়ও দ্রুত বাড়ে (এই run-এ 16 → 63 → 404 ms; শেষ ধাপে চারগুণের বেশি, যা ব্রাউজার আর memory-র প্রভাব)। সময়ের সংখ্যা একটি দৃষ্টান্ত মাত্র; নিম্নসীমার যুক্তি আসে উপপাদ্য ৬.২ থেকে, কোনো মাপা সময় থেকে নয়।
OV থেকে আরও অনেক সমস্যায় fine-grained reduction আছে। সবচেয়ে বিখ্যাত:
কোনো δ > 0-এর জন্য দৈর্ঘ্য n-এর দুটি string-এর edit distance O(n2−δ) সময়ে হিসাব করা গেলে SETH মিথ্যা।
প্রমাণের মূল ভাবনা (পূর্ণ প্রমাণ মূল প্রবন্ধে): প্রতিটি vector-কে একটি ছোট “gadget” string-এ লেখা হয়, যাতে দুটি vector-gadget-এর edit distance একটি মান নেয় যদি তারা orthogonal হয়, আর একটু বড় মান নেয় যদি না হয়। A-এর সব gadget পাশাপাশি জুড়ে একটি লম্বা string, B-এর সব gadget জুড়ে আরেকটি, আর মাঝে এমন “পাহারাদার” অংশ, যাতে সেরা alignment কোনো একটি জোড়া মেলাতে বাধ্য হয়। মোট দৈর্ঘ্য N · poly(d), তাই edit distance-এর n2−δ algorithm OV-কে N2−δ · poly(d) সময়ে সমাধান করত, আর উপপাদ্য ৬.২ দিয়ে SETH ভাঙত। একই বছরে longest common subsequence (LCS)-এর জন্যও একই ধরনের ফল আসে (Abboud, Backurs আর Vassilevska Williams; আর আলাদাভাবে Bringmann আর Künnemann).
1অনুমান: SETH2k-SAT ≤ OV, N = 2^(n/2)3OV ≤ edit distance, n = N · poly(d)4উল্টো দিকে পড়ুন: দ্রুত ⇒ SETH ভাঙে
| সমস্যা | |
| বিশ্বাস করা সময় | |
| অবস্থা |
- ভিত্তি অনুমান। SETH: বড় k-তে k-SAT-এর জন্য 2n-এর brute force থেকে সূচকে একটি ধ্রুবক ভগ্নাংশও বাঁচানো যায় না। এটি প্রমাণিত নয়; পুরো শিকল এর ওপর দাঁড়িয়ে।
- প্রথম কড়া। উপপাদ্য ৬.২: চলকের দুই অর্ধেক থেকে দুই সেট vector. এটি একটি প্রমাণিত, শর্তহীন reduction; শর্ত আসে শুধু SETH থেকে।
- OV-এর অবস্থা। OV-এর N2−ε algorithm থাকলে SAT 2(1−ε/2)n সময়ে হতো। তাই “SETH ⇒ OV অনুমান”। OV এখন অনেক quadratic সমস্যার মাপকাঠি।
- দ্বিতীয় কড়া। Backurs–Indyk: প্রতিটি vector একটি gadget string; দৈর্ঘ্য N · poly(d). এটিও প্রমাণিত reduction, সূচক রক্ষা করে (fine-grained).
- শেষ সিদ্ধান্ত, উল্টো দিক থেকে। কেউ edit distance-এর n1.99 algorithm দিলে শিকল বেয়ে SAT-এর 2(1−ε)n algorithm আসত, অর্থাৎ SETH মিথ্যা। তাই n2−δ খোঁজা মানে, পরোক্ষে, SAT-এর একটি যুগান্তকারী algorithm খোঁজা।
SETH একমাত্র কেন্দ্র নয়। আরও দুটি বহুল ব্যবহৃত অনুমান আছে, আর এদের পরস্পরের সম্পর্ক জানা নেই:
- 3SUM অনুমান: n-টি পূর্ণসংখ্যা থেকে যোগফল 0 হয় এমন তিনটি বের করতে কোনো ε > 0-এর জন্য O(n2−ε) সময় যথেষ্ট নয়। Sort আর two pointer-এর O(n2) সমাধান DSA কোর্সের পর্ব ১৬-এ। Gajentaan আর Overmars (১৯৯৫) দেখান, “সমতলে কোনো তিনটি বিন্দু এক রেখায়?”-এর মতো বহু জ্যামিতিক সমস্যা 3SUM-hard. Grønlund আর Pettie (২০১৪) log-গুণকে সামান্য দ্রুত algorithm দেন, কিন্তু n2−ε নয়।
- APSP অনুমান: n vertex আর polynomial আকারের integer weight-এর graph-এ সব জোড়ার shortest path O(n3−ε) সময়ে নয়। Vassilevska Williams আর Williams (২০১০) দেখান, “negative weight-এর একটি ত্রিভুজ আছে?” আর আরও কয়েকটি সমস্যা APSP-এর সঙ্গে subcubic-সমতুল্য: একটির n3−ε algorithm থাকলে সবগুলোর আছে।
ছবি ৭২.২ — Fine-grained জগতের তিনটি কেন্দ্র
প্রতিটি তীর একটি প্রমাণিত fine-grained reduction; বাঁয়ের বাক্সগুলো প্রমাণিত নয়, অনুমান।
৭ · Engineer-এর চোখে — parameter বাছাই আর quadratic-এর দেয়াল
এই তত্ত্ব বাস্তবে কী শেখায়? প্রথম শিক্ষা: একটি NP-hard সমস্যা পেলে জিজ্ঞেস করুন, কোন সংখ্যাটি আমার ডেটায় ছোট? উত্তরের আকার (ক্যামেরা-সংখ্যা), graph কতটা গাছের মতো (treewidth), কয়টি ভিন্ন ধরনের অর্ডার, কয়টি ব্যতিক্রম। সঠিক parameter বাছলে একই সমস্যা অচল থেকে দ্রুত হয়ে যায়। Courcelle-এর একটি বিখ্যাত উপপাদ্য (১৯৯০) বলে, একটি নির্দিষ্ট logic-এ লেখা যায় এমন graph-ধর্ম bounded treewidth-এ রৈখিক সময়ে পরীক্ষা করা যায়, যদিও ধ্রুবক প্রায়ই বিশাল।
দ্বিতীয় শিক্ষা: আগে kernel. বাস্তবের অনেক instance-এ নিশ্চিত নিয়মগুলোই সমস্যাকে ছোট করে দেয়, যেমন buss_kernel.py-তে ৪০০ থেকে ৮টি vertex. তৃতীয় শিক্ষা: একটি quadratic algorithm-কে subquadratic বানানোর আগে দেখুন সমস্যাটি OV, 3SUM বা APSP-hard কি না। হলে সাধারণ ক্ষেত্রে বড় সূচক-উন্নতি আশা করা বৃথা; তার বদলে খুঁজুন ধ্রুবক-গুণক, approximation, বা একটি parameter. Edit distance-এ সেই parameter হলো দূরত্ব নিজেই: দূরত্ব বড়জোর k হলে কেবল মূল কর্ণের চারপাশের 2k + 1 চওড়া পট্টি হিসাব করলেই হয়, সময় O(n · k) (Ukkonen-এর ১৯৮৫ সালের কৌশল বলে পরিচিত)।
একটি সত্যিকারের run. uv দিয়ে বানানো একটি ছোট প্রকল্পে rapidfuzz (MIT licence; ভেতরের C++ কোড bit-parallel কৌশলে একসঙ্গে 64টি cell হিসাব করে) আর হাতে লেখা DP দিয়ে random string-এর edit distance মাপা হলো। প্রশ্ন: কৌশলী বাস্তবায়নেও কি quadratic বৃদ্ধি থাকে? প্রতিটি DP-ফল rapidfuzz-এর সঙ্গে মেলানো (assert), আর rapidfuzz-এ তিনবার চালিয়ে সবচেয়ে কম সময়। লাইব্রেরিতে কোনো network বা usage-reporting কোড নেই (প্যাকেজ ফাইলে খোঁজা হয়েছে)।
from rapidfuzz.distance import Levenshtein
# dp(a, b): the textbook O(n*n) table, two rows; rand(n): random "acgt" string
for n in (500, 1000, 2000):
a, b = rand(n), rand(n)
assert dp(a, b) == Levenshtein.distance(a, b)
for n in (10000, 20000, 40000, 80000):
a, b = rand(n), rand(n)
d, t = best_of(lambda: Levenshtein.distance(a, b)) # min of 3 runsসত্যিকারের run (ডেস্কটপ, rapidfuzz 3.14.6, Python 3.12.13):
~/bazarghar-toc$ uv run python edit_timing.py
python 3.12.13 | rapidfuzz 3.14.6
pure-Python DP (n x n table)
n = 500 distance 264 32.2 ms
n = 1000 distance 536 142.8 ms
n = 2000 distance 1048 588.3 ms
rapidfuzz Levenshtein.distance (bit-parallel C++)
n = 10000 distance 5173 65.7 ms
n = 20000 distance 10356 235.0 ms x3.6
n = 40000 distance 20721 849.5 ms x3.6
n = 80000 distance 41375 3465.1 ms x4.1
হাতে লেখা DP-তে n দ্বিগুণ হলে সময় প্রায় চারগুণ (32 → 143 → 588 ms). rapidfuzz অনেক দ্রুত: n = 10000-এ মাত্র 66 ms, কারণ একটি 64-bit শব্দে একসঙ্গে ৬৪টি cell. কিন্তু বৃদ্ধির ধরন বদলায়নি: প্রতি দ্বিগুণে ৩.৬ থেকে ৪.১ গুণ। Bit-parallelism n2-কে প্রায় n2/64-এ নামায়, যা একটি ধ্রুবক-গুণক, সূচক নয়; Backurs–Indyk-এর ফলের সঙ্গে এটি পুরোপুরি মেলে। random “acgt” string-এ দূরত্ব প্রায় 0.52n, অর্থাৎ বড়, তাই O(n · k) কৌশলও এখানে সাহায্য করত না; বানান-সংশোধনে k ছোট বলে সেখানে করে। এই সময়গুলো একটি যন্ত্রের মাপ, কোনো প্রমাণ নয়।
আরও গভীরে: Kernel-এর আকারের নিম্নসীমাও আছে, শর্তসাপেক্ষে। Bodlaender, Downey, Fellows আর Hermelin (২০০৯) আর Fortnow ও Santhanam-এর কাজ থেকে জানা, NP ⊄ coNP/poly হলে k-PATH-এর কোনো polynomial kernel নেই; Dell আর van Melkebeek (২০১০) দেখান, একই অনুমানে vertex cover-এর O(k2−ε) edge-এর kernel নেই, অর্থাৎ Buss-এর k2 edge সূচকের দিক থেকে প্রায় সেরা। Fine-grained দিকে SETH-কে সন্দেহ করার কারণও আলোচিত: Ryan Williams বিভিন্ন লেখায় বলেছেন SETH মিথ্যা হতে পারে, আর “nondeterministic SETH”-এর মতো রূপ নিয়ে গবেষণা চলছে। Parameterized আর fine-grained দুই তত্ত্বই এখনো দ্রুত বদলাচ্ছে; Cygan ও সহকর্মীদের Parameterized Algorithms (২০১৫) এই বিষয়ের পরিচিত পাঠ্যবই।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন আসতে পারে:
- FPT আর XP-এর পার্থক্য লিখুন। FPT: f(k) · nc, c ধ্রুবক; XP: f(k) · ng(k), সূচক k-এর সঙ্গে বাড়ে। FPT ⊊ XP.
- Vertex cover O(2k · m)-এ সমাধান করুন। প্রতিটি edge-এর এক প্রান্ত cover-এ থাকবেই; দুই শাখা, গভীরতা ≤ k.
- Buss kernel-এর আকার কত? degree > k-এর vertex বাধ্যতামূলক; তারপর edge > k2 হলে NO; kernel-এ ≤ k2 edge, ≤ k2 + k vertex.
- Independent set থেকে vertex cover-এর reduction কি parameterized? না, k′ = n − k শুধু k-এর function নয়।
- Edit distance-এ O(n1.9) কেন আশা কম? Backurs–Indyk: থাকলে SETH মিথ্যা; শর্তসাপেক্ষ, প্রমাণিত নিম্নসীমা নয়।
৮ · AI-এর যুগে parameterized আর fine-grained complexity
এই বিষয়ে AI assistant-এর ভুলগুলো সূক্ষ্ম, কারণ প্রতিটি দাবি একটি শর্তের ওপর দাঁড়িয়ে। কয়েকটি ভুল বারবার দেখা যায়: “k-CLIQUE FPT নয়” বা “edit distance-এর quadratic নিম্নসীমা প্রমাণিত” বলে শর্ত বাদ দেওয়া; nk-এর algorithm-কে FPT বলা; independent set থেকে vertex cover-এর reduction-কে parameterized ধরে নেওয়া; Buss kernel-এর সীমা ভুল বলা (যেমন নিয়ম ২-এ “degree ≥ k”); ETH আর SETH-এর বক্তব্যে quantifier উল্টে ফেলা; আর বানানো সাল বা প্রবন্ধের নাম। এমনকি একটি সঠিক search tree code লিখে তার node-সংখ্যার সীমা ভুল হিসাব করাও সাধারণ।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “সব k-উপসেট পরীক্ষা, তাই k-CLIQUE FPT” | সময় nk: সূচকে k, তাই শুধু XP |
| “Vertex cover FPT, তাই independent set-ও FPT” | k′ = n − k; parameterized reduction নয় |
| “k-CLIQUE FPT নয় (প্রমাণিত)” | W[1]-hard; FPT ≠ W[1] অনুমান মাত্র |
| “Edit distance-এ Ω(n2) প্রমাণিত” | শুধু SETH সত্য হলে; শর্তটি লিখতেই হবে |
| নিয়ম ২-এ “degree ≥ k”, বা kernel “≤ k vertex” | নিয়ম: degree > k; সীমা k2 edge, k2 + k vertex; তারা-graph দিয়ে পরীক্ষা |
| SETH: “কোনো k-এর জন্য 2(1−ε)n নয়” | quantifier: প্রতিটি ε-এর জন্য এমন k আছে |
AI-কে কাজে লাগানোর ভালো উপায়: algorithm-এর সঙ্গে সময়ের সীমা আর তার প্রমাণ চাওয়া, প্রতিটি নিম্নসীমার পাশে তার অনুমান লিখতে বলা, আর দেওয়া code ছোট graph-এ brute force-এর সঙ্গে মেলানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Vertex cover আর clique দুটিই NP-complete, তবু parameter-এর জগতে একটি FPT আর অন্যটি W[1]-hard. এই পার্থক্য থেকে NP-completeness সম্পর্কে কী শিখি?
NP-completeness একটি মোটা দাগের শ্রেণিবিভাগ। Karp-এর ১৯৭২ সালের তালিকার সমস্যাগুলো polynomial-time reduction-এ পরস্পরের সমান, তাই “P-তে আছে কি না” প্রশ্নে সবগুলো একসাথে ওঠে বা পড়ে। কিন্তু এই reduction instance-এর ভেতরের গঠন, বিশেষ করে উত্তরের আকার, রক্ষা করে না। Independent set থেকে vertex cover-এ যেতে k হয়ে যায় n − k; ছোট একটি সংখ্যা বড় হয়ে যায়।
১৯৮০-এর দশকের শেষ আর ১৯৯০-এর দশকের শুরুতে Rodney Downey আর Michael Fellows এই ফাঁকটিকে তত্ত্বে রূপ দেন। তাঁদের প্রশ্ন ছিল: যদি বাস্তবে k ছোট হয়, কোন সমস্যা সত্যিই সহজ? উত্তর দিতে তাঁরা parameterized reduction সংজ্ঞায়িত করেন, যেখানে নতুন parameter শুধু পুরোনো parameter-এর function. এই কঠোর reduction-এ NP-complete সমস্যাগুলো আর একটি দলে থাকে না, বরং একটি পুরো সিঁড়িতে ছড়িয়ে পড়ে: vertex cover, k-PATH আর feedback vertex set FPT; k-CLIQUE আর k-INDEPENDENT-SET W[1]-complete; k-DOMINATING-SET W[2]-complete; আরও ওপরে আরও কঠিন শ্রেণি। তাঁদের বই Parameterized Complexity ১৯৯৯ সালে প্রকাশিত হয়।
W[1]-কঠিনতার পেছনের অনুভূতিটিও শিক্ষণীয়। W[1]-এর একটি সম্পূর্ণ সমস্যা “একটি nondeterministic যন্ত্র k ধাপে গ্রহণ করে কি না”। k ধাপে যন্ত্রটি k বার অনুমান করে, আর প্রতিটি অনুমানে n বিকল্প; তাই অনুভূতিতে nk-এর মতো খোঁজা অনিবার্য মনে হয়। Clique-ও তাই: k-টি vertex অনুমান করুন আর জোড়ায় জোড়ায় মেলান। Vertex cover-এ উল্টো, প্রতিটি সিদ্ধান্ত দুটি বিকল্পে সীমিত, কারণ একটি নির্দিষ্ট edge-এর দুই প্রান্তের একটি নিতেই হবে। এই “বাধ্যতামূলক ছোট বিকল্প” কাঠামোটিই FPT-এর উৎস।
এখান থেকে একটি বড় শিক্ষা: একটি সমস্যা NP-complete জানলে অনুসন্ধান থামানো উচিত নয়, বরং প্রশ্ন বদলানো উচিত। কোন parameter ছোট, আর সেই parameter-এ সমস্যাটি সিঁড়ির কোথায়? আরেকটি সতর্কতা: W[1]-hard মানেও “অসম্ভব প্রমাণিত” নয়; FPT ≠ W[1] একটি অনুমান, যদিও ETH থেকে আসে।
মূল উপলব্ধি: NP-completeness সমস্যাগুলোকে এক বস্তায় ভরে, কিন্তু parameterized reduction সেই বস্তা খুলে দেখায় যে ছোট উত্তরের ক্ষেত্রে vertex cover আর clique মৌলিকভাবে আলাদা; পার্থক্যটি শর্তসাপেক্ষ (FPT ≠ W[1]), প্রমাণিত নয়।
প্র ০২“Kernel থাকা ⇔ FPT” প্রমাণ হলে polynomial kernel নিয়ে আলাদা গবেষণা কেন? বাস্তবের solver-এর সঙ্গে kernel-এর সম্পর্ক কী?
উপপাদ্য ৩.৩-এর প্রমাণটি একটু প্রতারণার মতো: FPT algorithm থেকে বানানো kernel-এর আকার f(k), যা 2k বা আরও বিশাল হতে পারে। এমন kernel তাত্ত্বিকভাবে সঠিক, কিন্তু কোনো কাজে আসে না, কারণ k = 40-এ 240 আকারের “ছোট” instance মূলটির চেয়েও বড় হতে পারে। তাই আসল প্রশ্ন হলো: h(k) কত ছোট করা যায়? Polynomial kernel মানে instance-কে শুধু k-এর polynomial আকারে নামানো, যেমন vertex cover-এ k2 edge.
২০০০-এর দশকের শেষে একটি বড় অগ্রগতি আসে: শুধু kernel বানানো নয়, kernel না থাকার প্রমাণ। Bodlaender, Downey, Fellows আর Hermelin (২০০৯) দেখান, “composition” নামের একটি গুণ থাকলে polynomial kernel থাকা NP ⊆ coNP/poly-এর মতো অসম্ভাব্য পরিণাম আনত; এর মূল lemma Fortnow আর Santhanam-এর কাজ। এভাবে k-PATH-এর মতো FPT সমস্যারও polynomial kernel নেই বলে শর্তসাপেক্ষে জানা গেল। Dell আর van Melkebeek আরও সূক্ষ্মভাবে দেখান, vertex cover-এর O(k2−ε) edge-এর kernel একই শর্তে নেই। অর্থাৎ ১৯৯০-এর দশকের সরল Buss নিয়মটি সূচকের দিক থেকে প্রায় সেরা, যা তত্ত্বের একটি সুন্দর মুহূর্ত।
বাস্তবের সঙ্গে সম্পর্ক সরাসরি। SAT solver আর ILP solver চালানোর আগে “preprocessing” ধাপ চলে: একক clause ছড়ানো, অপ্রয়োজনীয় চলক বাদ দেওয়া, বাধ্যতামূলক সিদ্ধান্ত আগে নেওয়া। এগুলো আসলে নিরাপদ reduction rule, kernelization-এর আত্মীয়। পার্থক্য হলো, solver-এর preprocessing সাধারণত কোনো আকারের নিশ্চয়তা দেয় না, আর kernel দেয়। বাজারঘরের মতো একটি সংস্থার জন্য পরামর্শ: প্রথমে নিরাপদ নিয়ম দিয়ে instance ছোট করুন, প্রতিটি নিয়মের সঠিকতা ছোট ক্ষেত্রে brute force দিয়ে মিলিয়ে নিন (এই পর্বে ৩০০০টি random graph-এ যেমন করা হয়েছে), তারপর ছোট instance-এ exact algorithm চালান।
আরেকটি সূক্ষ্ম কথা: kernel-এর ভাবনা একটি “তত্ত্ব-মাপা preprocessing”, যা NP-hard সমস্যার polynomial সময়ের অংশটুকু ঠিক কতটা কাজ করতে পারে, তার একটি নিখুঁত প্রশ্ন তোলে। Polynomial সময়ে সব instance-কে এক bit-ও ছোট করা গেলে বারবার করে P = NP পাওয়া যেত; kernel সেই অসম্ভবের ঠিক পাশের সম্ভব কাজটি মাপে।
মূল উপলব্ধি: যেকোনো FPT সমস্যার kernel আছে, কিন্তু কাজের প্রশ্ন kernel-এর আকার; polynomial kernel-এর অস্তিত্ব আর অনস্তিত্ব (শর্তসাপেক্ষ) দুটিই এখন প্রমাণ করা যায়, আর solver-এর preprocessing এই ভাবনারই ব্যবহারিক রূপ।
প্র ০৩SETH কতটা বিশ্বাসযোগ্য? যদি এটি মিথ্যা হয়, fine-grained complexity-র কী থাকবে?
Impagliazzo আর Paturi ২০০১ সালে ETH আর SETH স্পষ্ট করেন একটি পর্যবেক্ষণ থেকে: k-SAT-এর জানা সেরা algorithm-গুলো, যেমন PPSZ আর Schöning-এর random walk, প্রতিটি স্থির k-এ 2(1−c/k)n ধরনের সময় নেয়, যেখানে c একটি ধ্রুবক। k বাড়লে সঞ্চয় c/k শূন্যের দিকে যায়। SETH বলে এই প্রবণতা অনিবার্য। অর্থাৎ SETH মূলত বলে: “আমাদের জানা সেরা algorithm-গুলোর ধরন সঠিক।”
বিশ্বাসের পক্ষে যুক্তি: বহু দশকের চেষ্টায় CNF-SAT-এর জন্য 2(1−ε)n algorithm মেলেনি, আর এটি সম্ভব হলে বহু আপাত-অসম্পর্কিত সমস্যায় একসাথে চমক আসত, যেমন edit distance, LCS, graph-এর diameter আর OV. পক্ষে আরেকটি যুক্তি হলো, বিশেষ সীমিত মডেলে (যেমন কিছু ধরনের resolution proof) SETH-এর মতো নিম্নসীমা প্রমাণিত। বিপক্ষে: Ryan Williams প্রকাশ্যে বলেছেন যে তিনি SETH মিথ্যা হওয়ার সম্ভাবনা গুরুত্ব দিয়ে দেখেন, আর circuit-সংক্রান্ত কিছু ফল দেখায় SETH সত্য হলে কিছু circuit lower bound-এর পথ কঠিন হয়। “Nondeterministic SETH” নামের একটি রূপ নিয়েও গবেষণা চলছে, যা আরও শক্ত দাবি।
SETH মিথ্যা হলে কী থাকবে? প্রথমত, শিকলের reduction-গুলো শর্তহীন, প্রমাণিত সত্য; সেগুলো থাকবে। তখন সেগুলো উল্টো দিকে কাজে লাগবে: SAT-এর দ্রুত algorithm থেকে OV-এর, আর OV থেকে অন্যদের দ্রুত algorithm আসবে কি না, তা আলাদা প্রশ্ন, কারণ reduction শুধু এক দিকে। দ্বিতীয়ত, 3SUM আর APSP অনুমান SETH-এর থেকে স্বাধীন বলে মনে করা হয় (পারস্পরিক reduction জানা নেই), তাই সেগুলোর ওপর দাঁড়ানো ফল টিকে থাকবে। তৃতীয়ত, গবেষকেরা কিছু ফল একাধিক অনুমান থেকে প্রমাণ করেন, যাতে একটির পতনে সব না ভাঙে।
দার্শনিক দিক থেকে fine-grained complexity একটি সৎ দর কষাকষি: P বনাম NP-এর মতো প্রশ্নে শর্তহীন প্রমাণ নাগালের বাইরে, তাই আমরা কয়েকটি পরিষ্কার অনুমান বেছে নিয়ে তাদের পরিণামগুলো নিখুঁতভাবে মানচিত্রে আঁকি। কোন অনুমান ভাঙলে কোন অংশ ভাঙবে, সেই মানচিত্রটিই মূল্যবান জ্ঞান।
মূল উপলব্ধি: SETH আমাদের জানা সেরা SAT algorithm-গুলোর প্রবণতাকে অনুমানে রূপ দেয়; এটি মিথ্যা হতে পারে, কিন্তু reduction-গুলো প্রমাণিত থাকে আর 3SUM ও APSP-এর মতো স্বাধীন কেন্দ্র তত্ত্বকে টিকিয়ে রাখে।
প্র ০৪Backurs–Indyk-এর ফল সত্ত্বেও বাস্তবে বড় DNA বা লেখার তুলনা কীভাবে হয়? নিম্নসীমা কোন ফাঁকগুলো খোলা রাখে?
শর্তসাপেক্ষ নিম্নসীমা একটি খুব নির্দিষ্ট দাবি: সবচেয়ে খারাপ ক্ষেত্রে, নিখুঁত উত্তর, দুটি সাধারণ string-এর জন্য n2−δ সময় সম্ভব নয় (SETH সত্য হলে)। প্রতিটি বিশেষণ একটি ফাঁক খোলে, আর বাস্তবের কৌশলগুলো ঠিক সেই ফাঁক দিয়ে ঢোকে।
প্রথম ফাঁক: ছোট দূরত্ব। দুটি string প্রায় এক হলে, অর্থাৎ দূরত্ব k ছোট, DP টেবিলের মূল কর্ণের চারপাশের সরু পট্টিই যথেষ্ট; Ukkonen-এর ১৯৮৫ সালের কৌশল O(n · k), আর Landau ও Vishkin-এর কৌশল প্রায় O(n + k2) বলে পরিচিত। এটি আসলে একটি parameterized algorithm, parameter দূরত্ব নিজেই। বানান-সংশোধন বা একই ফাইলের দুটি সংস্করণ তুলনায় k সাধারণত ছোট।
দ্বিতীয় ফাঁক: ধ্রুবক-গুণক। এই পর্বের সত্যিকারের run-এ rapidfuzz bit-parallel কৌশলে (Myers-এর ১৯৯৯ সালের কৌশলের ধারা) একসঙ্গে ৬৪টি cell হিসাব করে হাতে লেখা Python DP-র চেয়ে বহু গুণ দ্রুত, অথচ বৃদ্ধি এখনো quadratic. GPU বা SIMD আরও ধ্রুবক দেয়। Masek আর Paterson-এর “Four Russians” কৌশল একটি log-গুণক দেয়।
তৃতীয় ফাঁক: আসন্ন মান। নিম্নসীমা নিখুঁত উত্তরের জন্য। গত এক দশকে edit distance-এর ধ্রুবক-গুণক approximation প্রায়-রৈখিক সময়ে সম্ভব বলে দেখানো হয়েছে (Chakraborty ও সহকর্মীদের ২০১৮ সালের কাজ থেকে শুরু, পরে আরও উন্নতি)। চতুর্থ ফাঁক: heuristic আর index. DNA-র বড় তুলনায় BLAST-ধাঁচের সরঞ্জাম আগে ছোট মিলে যাওয়া টুকরো (seed) খোঁজে, তারপর শুধু সম্ভাবনাময় অঞ্চলে পূর্ণ DP চালায়; এরা নিখুঁত উত্তরের নিশ্চয়তা দেয় না, কিন্তু বাস্তবে খুব কাজের।
তাই একজন engineer-এর জন্য নিম্নসীমাটি একটি দিকনির্দেশক: “সাধারণ নিখুঁত সমাধান দ্রুত করার চেষ্টায় সময় নষ্ট করবেন না; বরং ঠিক করুন আপনার ডেটার কোন গুণটি (ছোট দূরত্ব, আসন্ন মান যথেষ্ট, বিশেষ গঠন) কাজে লাগানো যায়।”
মূল উপলব্ধি: Backurs–Indyk শুধু সাধারণ, নিখুঁত, সবচেয়ে খারাপ ক্ষেত্রের subquadratic algorithm নিষেধ করে (SETH-এর শর্তে); ছোট দূরত্বে parameterized algorithm, ধ্রুবক-গুণক, approximation আর heuristic সেই ফাঁকগুলো দিয়েই বাস্তবের কাজ চালায়।
প্র ০৫একই সমস্যার জন্য “উত্তরের আকার” ছাড়া আর কোন parameter বাছা যায়? বাজারঘরের delivery নকশায় treewidth-এর মতো গঠনগত parameter কেন কাজের হতে পারে?
উত্তরের আকার k সবচেয়ে স্বাভাবিক parameter, কিন্তু প্রায়ই সবচেয়ে কাজেরটি নয়। বাজারঘরের নকশায় ক্যামেরার বাজেট ৫০০ হলে 1.27500 অচল। তখন প্রশ্ন বদলাতে হয়: ডেটার কোন গঠন ছোট? এই ধরনের parameter-কে গঠনগত (structural) parameter বলে।
সবচেয়ে বিখ্যাত গঠনগত parameter treewidth. একটি গাছের treewidth 1, আর একটি graph যত গাছের মতো, তার treewidth তত ছোট। ১৯৮০-এর দশকে Robertson আর Seymour তাঁদের graph minor তত্ত্বে এই ধারণা কেন্দ্রে আনেন (এর আগে ও সমান্তরালে অন্য নামেও এটি ব্যবহৃত হয়েছে বলে জানা)। Treewidth w-এর একটি tree decomposition হাতে থাকলে vertex cover, independent set, 3-COLOR-এর মতো বহু NP-hard সমস্যা 2O(w) · n ধরনের সময়ে DP দিয়ে সমাধান হয়: প্রতিটি “থলি”তে বড়জোর w + 1টি vertex, আর DP থলির সব উপসেট বা রং-বিন্যাস ধরে এগোয়। Courcelle-এর ১৯৯০ সালের উপপাদ্য এটিকে সাধারণ করে: monadic second-order logic-এ লেখা যায় এমন যেকোনো graph-ধর্ম bounded treewidth-এ রৈখিক সময়ে, যদিও ধ্রুবক অকল্পনীয় বড় হতে পারে।
বাস্তবের রাস্তা-নকশা কি ছোট treewidth-এর? পুরো শহরের গ্রিড-সদৃশ নকশায় treewidth সাধারণত √n-এর মতো বাড়ে, তাই ছোট নয়। কিন্তু অনেক বাস্তব নেটওয়ার্ক, যেমন গ্রামীণ এলাকার প্রায়-গাছের মতো রাস্তা, একটি প্রধান সড়ক থেকে শাখা-প্রশাখা, বা একটি সংস্থার শ্রেণিবদ্ধ বিভাগ-কাঠামো, ছোট treewidth-এর কাছাকাছি। তখন একই NP-hard সমস্যা হঠাৎ দ্রুত হয়ে যায়। আরও কিছু গঠনগত parameter: feedback vertex set-এর আকার (কয়টি vertex মুছলে graph গাছ হয়), vertex cover number নিজেই অন্য সমস্যার parameter হিসেবে, বা “কয়টি ভিন্ন ধরনের অর্ডার”।
একটি সূক্ষ্ম কথা: ETH থেকে treewidth DP-র জন্যও নিম্নসীমা আসে, যেমন অনেক সমস্যায় 2o(w) · poly(n) সম্ভব নয়, আর SETH থেকে কিছু ক্ষেত্রে ভিত্তি পর্যন্ত নিখুঁত সীমা (Lokshtanov, Marx আর Saurabh-এর কাজ বলে পরিচিত)। এভাবে parameterized আর fine-grained দুই তত্ত্ব এক বিন্দুতে মেলে।
মূল উপলব্ধি: Parameter বাছাই নিজেই একটি নকশার সিদ্ধান্ত; উত্তরের আকার বড় হলেও treewidth-এর মতো গঠনগত parameter ছোট হতে পারে, আর তখন NP-hard সমস্যাও দ্রুত হয়, যার সীমা আবার ETH ও SETH দিয়ে মাপা যায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের graph বা সূত্র বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা (FPT algorithm): TRIANGLE-DELETION: graph G আর k দেওয়া; বড়জোর k-টি vertex মুছে G-কে ত্রিভুজমুক্ত করা যায় কি? (বাজারঘরের ভাষায়: তিনটি গুদাম পরস্পর সরাসরি যুক্ত থাকলে একটি “চক্রাকার ঝুঁকি”; বড়জোর k-টি গুদাম বন্ধ করে সব ঝুঁকি দূর করা যায়?) একটি bounded search tree algorithm নকশা করুন, সঠিকতা যুক্তিসহ, আর সময় বের করুন।
Algorithm TD(G, k): “G-এ কোনো ত্রিভুজ না থাকলে YES. k = 0 হলে NO. নইলে একটি ত্রিভুজ {u, v, w} খুঁজে TD(G − u, k − 1) বা TD(G − v, k − 1) বা TD(G − w, k − 1).” সঠিকতা: যেকোনো সমাধান-সেট S এই ত্রিভুজের অন্তত একটি vertex ধারণ করে, নইলে ত্রিভুজটি থেকে যেত; লেমা ২.১-এর মতো (⇒) আর (⇐) দুই দিকই চলে। গভীরতা ≤ k, শাখা ৩, তাই node ≤ (3k+1 − 1)/2 = O(3k). প্রতিটি node-এ একটি ত্রিভুজ খোঁজা সরলভাবে O(n3). মোট O(3k · n3), তাই সমস্যাটি FPT. (সাধারণীকরণ: d আকারের সেটে hitting set O(dk · poly) সময়ে।)
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: k-INDEPENDENT-SET FPT. প্রমাণ: G-তে k আকারের independent set ⇔ G-তে n − k আকারের vertex cover. Vertex cover O(2k · m) সময়ে সমাধান হয়। তাই independent set-ও O(2k · m) সময়ে। ∎” ভুলটি কোথায়, আর সঠিক সময় কত দাঁড়ায়?
সমতুল্যতাটি ঠিক, কিন্তু vertex cover-এর parameter এখন k′ = n − k. Search tree-র সময় O(2k′ · m) = O(2n−k · m), যা k ছোট হলে প্রায় 2n, মোটেই FPT নয়। ভুলটি হলো parameter বদলে যাওয়া উপেক্ষা করা: রূপান্তরটি polynomial-time reduction, কিন্তু parameterized reduction নয়, কারণ k′ শুধু k-এর function নয় (সংজ্ঞা ৪.১-এর শর্ত ২ ভাঙে)। আসলে k-INDEPENDENT-SET W[1]-complete বলে পরিচিত, তাই FPT ≠ W[1] সত্য হলে এর কোনো FPT algorithm নেই।
-
Trace (আউটপুট অনুমান): Graph: vertex 1–5, edge {1,2}, {2,3}, {3,4}, {4,5}, {5,1} (পাঁচ-চক্র)। (ক) অংশ ২-এর search tree k = 2-এ চালালে (প্রথম বাকি edge, আগে বাঁ প্রান্ত) উত্তর কী, আর কয়টি node? (খ) k = 3-এ উত্তর কী, কোন cover পাওয়া যায়, কয়টি node? (গ) Buss-এর নিয়ম k = 2-এ কী করে?
(ক) পাঁচ-চক্রের সবচেয়ে ছোট cover-এর আকার 3, তাই k = 2-এ NO. NO-উত্তরে গাছ পুরো খুঁজতে হয় কি না দেখুন: শিকড় (k = 2) → {1,2}-এ 1 নিলে বাকি {2,3}, {3,4}, {4,5} (k = 1) → 2 নিলে বাকি {3,4}, {4,5}, k = 0: NO; 3 নিলে বাকি {4,5}: NO. তারপর শিকড়ের ডান শাখা 2: বাকি {3,4}, {4,5}, {5,1} → 3 নিলে {4,5}, {5,1}: NO; 4 নিলে {5,1}: NO. মোট ৭টি node = 23 − 1.
(খ) k = 3: শিকড় → 1 → 2 → {3,4}-এ 3 নিলে বাকি {4,5}, k = 0: NO; 4 নিলে কোনো edge বাকি নেই: YES, cover {1, 2, 4}. দেখা node: শিকড়, {1}, {1,2}, {1,2,3}, {1,2,4} = ৫টি। (গ) প্রতিটি degree 2, যা k = 2-এর বেশি নয়, তাই নিয়ম ২ খাটে না; একাকী vertex নেই; edge 5 > k2 = 4, তাই নিয়ম ৩ সঙ্গে সঙ্গে NO বলে, search ছাড়াই। (সব সংখ্যা scratch-এ একই code দিয়ে মেলানো।)
-
হিসাব (SETH): ধরুন কেউ OV-এর একটি algorithm দাবি করলেন, যা N-টি করে vector আর d মাত্রায় O(N1.9 · d3) সময়ে চলে। উপপাদ্য ৬.২-এর reduction দিয়ে n চলক আর m = 10n clause-এর k-SAT কত সময়ে সমাধান হতো? এটি কি SETH-এর সঙ্গে সাংঘর্ষিক? আর এটি কি P = NP প্রমাণ করত?
N = 2n/2, d = m = 10n. সময় (2n/2)1.9 · (10n)3 = 20.95n · 1000n3, যোগ vector বানানোর O(2n/2 · nk). যেকোনো ε < 0.05-এর জন্য, যেমন ε = 0.04, এটি O(2(1−ε)n), কারণ 20.95n · n3 শেষ পর্যন্ত 20.96n-এর চেয়ে ছোট। আর এটি প্রতিটি k-এ খাটে (sparsification-এ m = O(n) ধরা যায়)। তাই SETH-এর সঙ্গে সরাসরি সাংঘর্ষিক: দাবি সত্য হলে SETH মিথ্যা।
কিন্তু P = NP প্রমাণ হতো না: 20.95n এখনো সূচকীয়। এমনকি ETH-ও ভাঙত না, কারণ ETH শুধু বলে কোনো δ > 0-এর জন্য 2δn-এর কমে নয়, আর 0.95 একটি ধনাত্মক δ. অর্থাৎ SETH, ETH আর P ≠ NP-এর মধ্যে SETH সবচেয়ে ভঙ্গুর; একটি OV algorithm শুধু সবচেয়ে শক্ত অনুমানটিকেই ভাঙে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রম“OV-এর N2−ε algorithm থাকলে SETH মিথ্যা” প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Sparsification দিয়ে k-CNF-এ clause-সংখ্যা m = O(n) ধরা
- চলকগুলো দুই অর্ধেকে ভাগ করা
- প্রতিটি অর্ধ-মান-বসানো থেকে m-মাত্রার vector: bit j = 1 যদি clause j এখনো মিথ্যা
- Orthogonal জোড়া আছে ⇔ সূত্রটি satisfiable
- N = 2n/2 বসিয়ে SAT-এর সময় 2(1−ε/2)n · poly(n), যা SETH নিষেধ করে
একটি parameterized problem-এর জন্য নিচের কোন সময়-সীমা তাকে FPT প্রমাণ করে (n = input-এর আকার, k = parameter)?
- O(nk)
- O(nlog k)
- O(3k · n2)
- O(2n · k)
Vertex cover-এর Buss kernel-এ নিয়ম ২ (degree > k হলে vertex নেওয়া) আর নিয়ম ১ (একাকী vertex মোছা) আর না খাটলে, কোন শর্তে উত্তর নিশ্চিত NO?
- vertex-সংখ্যা > k হলে
- edge-সংখ্যা > k2 হলে
- edge-সংখ্যা > k হলে
- কোনো vertex-এর degree ঠিক k হলে
G-তে k আকারের independent set ⇔ G-তে n − k আকারের vertex cover. এই রূপান্তর সম্পর্কে কোনটি সঠিক?
- এটি দেখায় k-INDEPENDENT-SET FPT
- এটি polynomial-time reduction-ও নয়
- এটি দেখায় vertex cover W[1]-hard
- এটি polynomial-time reduction, কিন্তু parameterized reduction নয়
k-CLIQUE-এর অবস্থা সম্পর্কে কোন বক্তব্যটি সঠিক?
- এটি XP-তে আর W[1]-complete; FPT ≠ W[1] সত্য হলে FPT নয়
- এটি FPT নয়, শর্তহীনভাবে প্রমাণিত
- এর O(2k · n2) algorithm জানা আছে
- এটি XP-তেও নেই
SETH (Strong Exponential Time Hypothesis)-এর সঠিক বক্তব্য কোনটি?
- 3SAT-এর জন্য কোনো 2o(n) algorithm নেই
- একটি নির্দিষ্ট k = 3-এর জন্য 2(1−ε)n সম্ভব নয়
- প্রতিটি ε > 0-এর জন্য এমন k আছে, যাতে k-SAT O(2(1−ε)n) সময়ে সমাধান করা যায় না; এটি অপ্রমাণিত
- SETH ২০০১ সালে প্রমাণিত একটি উপপাদ্য
বাজারঘরের একজন developer বললেন: “আমি edit distance-এর একটি সঠিক O(n1.8) algorithm পেয়েছি, যেকোনো দুটি string-এর জন্য।” দাবিটি সত্য হলে কী প্রমাণ হতো?
- P = NP
- SETH মিথ্যা
- 3SUM অনুমান মিথ্যা
- কিছুই না, কারণ edit distance-এর নিম্নসীমা নিয়ে কিছু জানা নেই
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Parameterized problem: instance (x, k). FPT = f(k) · nc সময়; XP = f(k) · ng(k). FPT ⊊ XP প্রমাণিত।
- Vertex cover: প্রতিটি edge-এর এক প্রান্ত নিতেই হয়, তাই search tree-র গভীরতা ≤ k আর সময় O(2k · (n + m)); জানা সেরা প্রায় 1.2738k.
- Buss kernel: degree > k ⇒ নিন; একাকী মুছুন; edge > k2 ⇒ NO. kernel-এ ≤ k2 edge, ≤ k2 + k vertex (নিখুঁত)। Decidable সমস্যায় kernel আছে ⇔ FPT.
- Parameterized reduction-এ k′ শুধু k-এর function. k-CLIQUE W[1]-complete; FPT ≠ W[1] অনুমান, ETH থেকে আসে।
- ETH, SETH, OV, 3SUM, APSP সবই অপ্রমাণিত অনুমান। SETH ⇒ OV-এ N2−ε নয় (Williams) ⇒ edit distance-এ n2−δ নয় (Backurs–Indyk); reduction প্রমাণিত, নিম্নসীমা শর্তসাপেক্ষ।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৩ · P বনাম NP — প্রশ্ন, তাৎপর্য আর বাধাফিরে দেখুনETH আর SETH-এর প্রথম পরিচয়, আর NP-complete সমস্যার সঙ্গে বাস্তবে কাজের চার পথ।
- পর্ব ৬১ · NP-complete সমস্যার পরিবারফিরে দেখুন3SAT থেকে vertex cover আর clique-এর reduction, যার রৈখিক আকার ETH-এর ফলে কাজে লাগে।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৭৩-এ SAT solver আর ILP.
- DSA · পর্ব ৬৫ — NP-hard সমস্যা বাস্তবেপাশের ট্র্যাকFPT search tree, local search আর solver, algorithm আর code-এর দিক থেকে।
- DSA · পর্ব ৫৪ — LCS, edit distance আর matrix chainপাশের ট্র্যাকযে quadratic DP-কে SETH সম্ভবত সেরা বলে, তার পূর্ণ বাস্তবায়ন।