এই পর্বে যা শিখবেন
- Polynomial-time computable function আর ≤p-এর সুনির্দিষ্ট সংজ্ঞা, দিকের নিয়ম আর transitivity-র প্রমাণ
- NP-hard আর NP-complete-এর সংজ্ঞা, আর “একটি NP-complete সমস্যা P-তে হলে P = NP”-এর প্রমাণ
- CLIQUE, INDEPENDENT-SET আর VERTEX-COVER-এর পারস্পরিক reduction, ছোট সব graph-এ brute force-এ যাচাইসহ
- 3SAT ≤p CLIQUE-এর নির্মাণ আর দুই দিকের পূর্ণ প্রমাণ, Python আর সত্যিকারের SAT solver দিয়ে মিলিয়ে দেখা
- NP-completeness প্রমাণের চার ধাপের ছাঁচ, আর উল্টো দিক, exponential আকার আর একমুখী “⇔”-এর মতো ভুল ধরার উপায়
১ · কেন অনুবাদকে দ্রুত হতে হয়
পর্ব ৫২ “Reduction দিয়ে undecidability”-তে mapping reduction দেখেছেন: একটি computable function f, যা সমস্যা A-এর প্রতিটি প্রশ্নকে সমস্যা B-এর প্রশ্নে অনুবাদ করে, উত্তর না বদলে। সেখানে প্রশ্ন ছিল “সমাধান আছে কি”, তাই f-এর একমাত্র শর্ত ছিল সব input-এ থামা। এই মডিউলের প্রশ্ন ভিন্ন: “দ্রুত সমাধান আছে কি?” পর্ব ৫৭ “Time complexity আর class P” আর পর্ব ৫৮ “NP — verifier আর nondeterministic polynomial time” এই দুই শ্রেণি দাঁড় করিয়েছে: P (polynomial সময়ে সমাধান করা যায়) আর NP (polynomial সময়ে যাচাই করা যায়)। এবার দুটি সমস্যার তুলনামূলক কঠিনতা মাপার যন্ত্র চাই।
ধরুন একটি সরকারি অফিসে দুটি কাউন্টার। কাউন্টার B-তে একজন দক্ষ কর্মকর্তা বসেন, যিনি “ফর্ম-খ” খুব দ্রুত নিষ্পত্তি করেন। আপনার হাতে “ফর্ম-ক”. পাশে একজন করণিক আছেন, যিনি যেকোনো ফর্ম-ক দেখে কয়েক মিনিটে একটি সমতুল্য ফর্ম-খ পূরণ করে দেন। তাহলে ফর্ম-ক নিষ্পত্তিও দ্রুত। কিন্তু করণিক যদি প্রতিটি ফর্ম অনুবাদ করতে কয়েক বছর নেন, তাহলে কাউন্টার B যত দ্রুতই হোক, আপনার কোনো লাভ নেই। আরও খারাপ: এত সময় পেলে করণিক হয়তো নিজেই ফর্ম-ক নিষ্পত্তি করে ফেলতেন, তখন কাউন্টার B-এর কোনো ভূমিকাই থাকে না। Reduction-এর f হলো করণিক; সে দ্রুত না হলে তুলনাটি অর্থহীন।
বাজারঘরের একটি বাস্তব ধাঁচের পরিস্থিতি দিয়ে শুরু করি। মার্কেটিং দল ঈদের “কম্বো প্যাক” বানাবে: k টি পণ্য, যাদের কোনো দুটি “বিরোধী” নয় (একই সরবরাহকারীর স্টক নিয়ে টানাটানি হয়, এমন জোড়াকে বিরোধী ধরা হয়েছে)। পণ্যকে vertex আর বিরোধকে edge ধরলে প্রশ্নটি হলো: এই graph-এ কি k আকারের independent set আছে? এদিকে IT দলের কাছে আগে কেনা একটি প্রোগ্রাম আছে, যা শুধু একটি প্রশ্নের উত্তর দেয়: “এই graph-এ কি k আকারের clique (সবাই সবার সঙ্গে যুক্ত, এমন দল) আছে?” নতুন প্রোগ্রাম কেনার আগে একটি সহজ কৌশল আছে: graph-এর প্রতিটি edge মুছে দিন আর প্রতিটি অনুপস্থিত জোড়ায় edge বসান। নতুন graph-এ k-clique থাকবে ঠিক তখন, যখন পুরনোটিতে k আকারের independent set ছিল (অংশ ৪-এ প্রমাণ)। এই রূপান্তর n টি পণ্যে প্রায় n2/2 টি জোড়া দেখে, তাই দ্রুত। এটিই একটি polynomial-time reduction.
ইতিহাস: Stephen Cook ১৯৭১ সালের প্রবন্ধে দেখান যে NP-এর প্রতিটি সমস্যা polynomial সময়ে SAT-এ নেওয়া যায়; তাঁর ব্যবহৃত reduction আজকের ভাষায় polynomial-time Turing reduction-এর কাছাকাছি (oracle-কে একাধিকবার প্রশ্ন করা যায়)। পরের বছর, ১৯৭২ সালে, Richard Karp “Reducibility among combinatorial problems” প্রবন্ধে একবার-প্রশ্নের, mapping ধরনের polynomial reduction দিয়ে ২১টি পরিচিত সমস্যাকে একই পরিবারে আনেন; CLIQUE, VERTEX-COVER আর 3SAT-ধাঁচের সমস্যা সেই তালিকায় ছিল। তাই ≤p-কে অনেক বইয়ে Karp reduction বলা হয়। Leonid Levin আলাদাভাবে, সোভিয়েত ইউনিয়নে, কাছাকাছি ফল ১৯৭৩ সালে প্রকাশ করেন। প্রকাশের সাল নিয়ে কিছু সূত্রে সামান্য ভিন্নতা দেখা যায়।
২ · সংজ্ঞা, দিকের নিয়ম আর transitivity
একটি function f: Σ∗ → Σ∗ polynomial-time computable, যদি একটি polynomial-time Turing machine থাকে, যা প্রতিটি input w-এ থামে আর থামার সময় tape-এ শুধু f(w) রেখে যায়। এমন f-কে বলা হয় polynomial-time computable function.
Language A polynomial-time reducible B-তে, লেখা হয় A ≤p B, যদি এমন একটি polynomial-time computable function f থাকে যে প্রতিটি w ∈ Σ∗-এর জন্য
w ∈ A ⇔ f(w) ∈ B
এই f-কে বলা হয় A থেকে B-তে polynomial-time reduction. ছোট “p” মানে polynomial.
এখানে “polynomial সময়” মাপা হয় input-এর দৈর্ঘ্য n দিয়ে, আর দৈর্ঘ্য নির্ভর করে encoding-এর ওপর (পর্ব ০৫)। Graph লেখা হয় adjacency list বা matrix-এ, সংখ্যা binary-তে। সংখ্যা unary-তে লিখলে input কৃত্রিমভাবে বিশাল হয়, আর তখন অনেক ধীর algorithm-ও “polynomial” দেখায়; এই ফাঁদের নাম pseudo-polynomial, যা পর্ব ৬১-এ subset sum-এ ফিরবে।
ধরুন A ≤p B. তাহলে:
১. B ∈ P হলে A ∈ P.
২. B ∈ NP হলে A ∈ NP.
অনুসিদ্ধান্ত (contrapositive): A ∉ P হলে B ∉ P.
প্রমাণ (অংশ ১):
- ধরুন f-কে হিসাব করে যন্ত্র F, যা দৈর্ঘ্য n-এর input-এ সর্বোচ্চ p(n) ধাপ নেয়; আর B-এর decider MB দৈর্ঘ্য m-এর input-এ সর্বোচ্চ q(m) ধাপ নেয়। p আর q polynomial. — অনুমান
- F প্রতি ধাপে tape-এ সর্বোচ্চ একটি চিহ্ন লেখে, তাই tape-এ শেষে থাকা f(w)-এর দৈর্ঘ্য সর্বোচ্চ n + p(n), যা আবার polynomial; সুবিধার জন্য একেও p(n) লিখি। — output-এর আকার সময়ের চেয়ে বড় হতে পারে না
- নতুন যন্ত্র N = “input w-এর ওপর: F দিয়ে f(w) হিসাব করুন; তারপর MB-কে f(w)-এর ওপর চালান আর তার রায়ই দিন।” — নির্মাণ
- N-এর মোট সময় সর্বোচ্চ p(n) + q(p(n)). দুটি polynomial-এর যোগ আর composition আবার polynomial, যেমন n2 ধাপের পর (n2)3 = n6. — polynomial-এর closure
- N w গ্রহণ করে ⇔ f(w) ∈ B ⇔ w ∈ A. তাই N polynomial সময়ে A decide করে: A ∈ P. ∎
অংশ ২-এর প্রমাণ একই: MB-এর জায়গায় B-এর polynomial-time verifier বা nondeterministic যন্ত্র বসান; ধাপ ২-এর আকারের সীমার জন্যই certificate-এর দৈর্ঘ্য আর সময় polynomial থাকে। অনুসিদ্ধান্তটি সরাসরি contrapositive.
ধাপ ২ আর ৪-ই পুরো তত্ত্বের হৃদয়। f যদি exponential সময় নিত, তাহলে |f(w)| exponential হতে পারত, আর q(|f(w)|) আর polynomial থাকত না। আবার f-এর হাতে exponential সময় থাকলে f নিজেই A সমাধান করে উত্তর অনুযায়ী একটি নির্দিষ্ট “হ্যাঁ” বা “না” instance লিখে দিতে পারত; তখন যেকোনো সমস্যা যেকোনো অ-তুচ্ছ সমস্যায় “reduce” হতো, আর তুলনার কোনো অর্থ থাকত না।
A ≤p B আর B ≤p C হলে A ≤p C.
প্রমাণ: ১. f আর g যথাক্রমে A → B আর B → C-এর reduction, সময় p(n) আর q(m). ২. h = g ∘ f নিন: প্রথমে f(w), তারপর তার ওপর g. ৩. |f(w)| ≤ p(n), তাই মোট সময় p(n) + q(p(n)), যা polynomial. ৪. w ∈ A ⇔ f(w) ∈ B ⇔ g(f(w)) ∈ C. ∎ এর ফলে reduction শিকলের মতো জোড়া যায়: SAT → 3SAT → CLIQUE → INDEPENDENT-SET → VERTEX-COVER, আর শিকলের প্রথম সমস্যার কঠিনতা শেষ পর্যন্ত পৌঁছায়।
৩ · NP-hard আর NP-complete
Language B NP-hard, যদি প্রতিটি L ∈ NP-এর জন্য L ≤p B.
B NP-complete, যদি (১) B ∈ NP, আর (২) B NP-hard.
লক্ষ করুন, NP-hard হতে NP-এর ভেতরে থাকা লাগে না। Halting problem NP-hard (পর্ব ৬২-এ প্রমাণ), অথচ সেটি decidable-ই নয়। NP-complete সমস্যাগুলো হলো NP-এর “সবচেয়ে কঠিন” সদস্য: NP-এর প্রতিটি সমস্যা এদের যেকোনো একটিতে দ্রুত অনুবাদ করা যায়।
যদি কোনো NP-complete সমস্যা B ∈ P হয়, তাহলে P = NP.
প্রমাণ:
- P ⊆ NP আগেই জানা (পর্ব ৫৮): polynomial সময়ে সমাধান করা গেলে certificate ছাড়াই যাচাই করা যায়। — এক দিক
- যেকোনো L ∈ NP নিন। B NP-hard, তাই L ≤p B. — সংজ্ঞা ৩.১
- B ∈ P, তাই উপপাদ্য ২.৩-এর অংশ ১ অনুযায়ী L ∈ P. — দিকের নিয়ম
- L ছিল NP-এর যেকোনো সদস্য, তাই NP ⊆ P. দুই দিক মিলিয়ে P = NP. ∎
উল্টো দিকে পড়লে: P ≠ NP হলে কোনো NP-complete সমস্যারই polynomial-time algorithm নেই। P বনাম NP প্রশ্নটি খোলা; P ≠ NP বলে বেশিরভাগ গবেষক মনে করেন, কিন্তু প্রমাণিত নয় (পর্ব ৬৩)। তাই কোনো সমস্যা NP-complete প্রমাণ করা মানে “দ্রুত algorithm নেই” প্রমাণ নয়; মানে হলো, দ্রুত algorithm পাওয়া গেলে তা কম্পিউটার বিজ্ঞানের সবচেয়ে বড় খোলা প্রশ্নের সমাধান করে দেবে।
B NP-complete, B ≤p C, আর C ∈ NP হলে C NP-complete.
প্রমাণ: C ∈ NP দেওয়া আছে। যেকোনো L ∈ NP-এর জন্য L ≤p B (B NP-hard), আর B ≤p C; transitivity (উপপাদ্য ২.৪) থেকে L ≤p C. তাই C NP-hard, আর NP-এ আছে: NP-complete. ∎
এই উপপাদ্যের শক্তি বিশাল: প্রতিটি নতুন সমস্যার জন্য NP-এর সব সমস্যা বিবেচনা করতে হয় না; একটি জানা NP-complete সমস্যা থেকে একটি reduction-ই যথেষ্ট। কিন্তু প্রথম NP-complete সমস্যাটি কোথা থেকে এল? সেটি Cook–Levin theorem: SAT NP-complete, যার প্রমাণ সরাসরি NP-এর সংজ্ঞা আর Turing machine-এর গণনা দিয়ে, কোনো reduction-এর সাহায্য ছাড়া। সেই প্রমাণ আর SAT ≤p 3SAT পর্ব ৬০ “Cook–Levin theorem”-এ। এই পর্বে আমরা ধরে নেব যে 3SAT NP-complete, আর সেখান থেকে শিকল বাড়াব।
Reduction-এর শিকল: কঠিনতা তীরের দিকে নামে
প্রতিটি তীর একটি ≤p. ওপরের সমস্যা NP-hard হলে তীর ধরে নিচের প্রতিটিও NP-hard.
৪ · CLIQUE, INDEPENDENT-SET আর VERTEX-COVER — এক সমস্যার তিন চেহারা
তিনটি decision problem, সবগুলোতে input একটি undirected graph G = (V, E), |V| = n, আর একটি সংখ্যা k:
- CLIQUE = {⟨G, k⟩ : G-তে k টি vertex আছে, যাদের প্রতিটি জোড়া edge দিয়ে যুক্ত}।
- INDEPENDENT-SET = {⟨G, k⟩ : G-তে k টি vertex আছে, যাদের কোনো জোড়ায় edge নেই}।
- VERTEX-COVER = {⟨G, k⟩ : G-তে k টি vertex আছে, যারা প্রতিটি edge-এর অন্তত এক প্রান্ত ছোঁয়}। এমন সেটকে বলে vertex cover.
তিনটিই NP-তে: certificate হলো k টি vertex-এর তালিকা, আর যাচাই O(n2) জোড়া বা O(|E|) edge দেখা। প্রথম দুটির সম্পর্ক এক লাইনে। G-এর complement graph Ḡ = (V, Ē), যেখানে Ē-তে ঠিক সেই জোড়াগুলো আছে, যারা E-তে নেই।
যেকোনো S ⊆ V-এর জন্য: (ক) S G-তে independent ⇔ S Ḡ-তে clique. (খ) S G-তে independent ⇔ V ∖ S G-এর vertex cover.
প্রমাণ: (ক) S independent ⇔ S-এর কোনো জোড়া {u, v} E-তে নেই ⇔ S-এর প্রতিটি জোড়া Ē-তে আছে ⇔ S Ḡ-তে clique. (খ) “⇒”: যেকোনো edge {u, v} নিন। দুই প্রান্তই S-এ থাকলে S independent হতো না, তাই অন্তত একটি প্রান্ত V ∖ S-এ। “⇐”: S-এর দুটি vertex u, v-এর মধ্যে edge থাকলে সেই edge-এর কোনো প্রান্ত V ∖ S-এ নেই, তাই V ∖ S cover নয়; contrapositive-এ “⇐” প্রমাণিত। ∎
INDEPENDENT-SET ≤p CLIQUE (f(⟨G, k⟩) = ⟨Ḡ, k⟩), CLIQUE ≤p INDEPENDENT-SET (একই f), INDEPENDENT-SET ≤p VERTEX-COVER (g(⟨G, k⟩) = ⟨G, n − k⟩), আর VERTEX-COVER ≤p INDEPENDENT-SET (একই g).
প্রমাণ: লেমা ৪.১(ক) থেকে G-তে k আকারের independent set আছে ⇔ Ḡ-তে k আকারের clique আছে; Ḡ-এর complement আবার G, তাই একই f উল্টো দিকেও কাজ করে। লেমা (খ) থেকে, S-এর আকার k হলে V ∖ S-এর আকার n − k, তাই k আকারের independent set ⇔ n − k আকারের vertex cover. Ḡ বানাতে n(n − 1)/2 টি জোড়া দেখা লাগে, আর n − k হিসাব একটি বিয়োগ: দুটিই polynomial. অবৈধ string (কোনো graph-এর encoding নয়) এলে f আর g একটি নির্দিষ্ট “না” instance লেখে, যেমন ⟨এক vertex-এর graph, 2⟩. ∎
প্রমাণ কাগজে আছে; এবার সব ছোট graph-এ brute force দিয়ে মিলিয়ে দেখি। নিচের কোড n = 1 থেকে ৫ পর্যন্ত প্রতিটি labelled graph আর প্রতিটি k-এর জন্য তিনটি প্রশ্ন আলাদাভাবে, কোনো সম্পর্ক না ধরে, সব subset পরীক্ষা করে উত্তর দেয়, আর মেলায়।
from itertools import combinations, product
def graphs(n): # every labelled graph on vertices 0..n-1
pairs = list(combinations(range(n), 2))
for bits in product([0, 1], repeat=len(pairs)):
yield n, {p for p, b in zip(pairs, bits) if b}
def has_k(n, E, k, good): # brute force: try every k-subset
return any(good(S, E) for S in combinations(range(n), k))
clique = lambda S, E: all(p in E for p in combinations(S, 2))
indep = lambda S, E: not any(p in E for p in combinations(S, 2))
def has_vc(n, E, k): # k vertices touching every edge
return any(all(u in S or v in S for u, v in E)
for S in map(set, combinations(range(n), k)))
def complement(n, E): # f for IS -> CLIQUE: flip every pair
return {p for p in combinations(range(n), 2) if p not in E}
checked = bad = 0
for n in range(1, 6):
for _, E in graphs(n):
for k in range(n + 1):
a = has_k(n, E, k, indep) # <G, k> in IS ?
b = has_k(n, complement(n, E), k, clique) # <G-bar, k> in CLIQUE ?
c = has_vc(n, E, n - k) # <G, n-k> in VC ?
checked += 1
bad += not (a == b == c)
print("instances (G, k) checked:", checked, " mismatches:", bad)
n, E = 4, {(0, 1), (1, 2), (2, 3)} # path a-b-c-d
print("path P4, complement edges:", sorted(complement(n, E)))
print("IS of size 2:", [S for S in combinations(range(n), 2) if indep(S, E)])আসল আউটপুট (ব্রাউজারের Python):
instances (G, k) checked: 6504 mismatches: 0
path P4, complement edges: [(0, 2), (0, 3), (1, 3)]
IS of size 2: [(0, 2), (0, 3), (1, 3)]
৫টি পর্যন্ত vertex-এর graph গোনা যায়: ১ + ২ + ৮ + ৬৪ + ১০২৪ = ১০৯৯টি, আর প্রতিটিতে k = 0 থেকে n: মোট ৬৫০৪টি instance, একটিতেও তিন উত্তরের অমিল নেই। শেষ দুই লাইন একটি ছোট উদাহরণ: পথ a–b–c–d-এর complement-এ ঠিক তিনটি edge, আর সেগুলোই মূল graph-এর ২ আকারের independent set. এই brute force উপপাদ্যের প্রমাণ নয় (n = 6-এ কী হয়, তা বলে না); প্রমাণ ওপরে। কিন্তু উল্টো দিকে ভুল reduction ধরতে এটি অসাধারণ: অনুশীলন ২-এর ভুল “n − k-এর বদলে k” এই কোডে সঙ্গে সঙ্গে অমিল দেখায়।
বাজারঘরের কম্বো প্যাকে ফিরি। কম্বো সমস্যাটি হুবহু INDEPENDENT-SET, তাই আগে কেনা CLIQUE প্রোগ্রাম দিয়ে উত্তর পাওয়া যায়। কিন্তু এর উল্টো একটি শিক্ষাও আছে: অংশ ৫-এর পর জানবেন CLIQUE NP-complete, তাই সেই প্রোগ্রামটি বড় graph-এ সবসময় দ্রুত হতে পারে, এমন আশা করার ভিত্তি নেই (যদি না P = NP). আর একই সমস্যা “পাহারা” চেহারায়ও আসে: বাজারঘরের গুদাম-এলাকার প্রতিটি রাস্তার অন্তত এক মাথায় নিরাপত্তাকর্মী বসাতে হবে, k জনে হবে কি? এটি VERTEX-COVER, আর n − k আকারের independent set খোঁজার সমান কঠিন।
৫ · 3SAT ≤p CLIQUE — clause-এর ত্রয়ী
এবার এমন একটি reduction, যেখানে উৎস আর লক্ষ্য দেখতে একেবারেই আলাদা: একটি যুক্তি-সূত্র থেকে একটি graph. আগে শব্দগুলো। একটি literal হলো একটি Boolean চলক x বা তার উল্টো ¬x. একটি clause কয়েকটি literal-এর ∨ (OR). CNF সূত্র কয়েকটি clause-এর ∧ (AND). প্রতিটি clause-এ ঠিক তিনটি literal থাকলে সূত্রটি 3CNF, আর
3SAT = {⟨φ⟩ : φ একটি satisfiable 3CNF সূত্র}।
“Satisfiable” মানে চলকগুলোতে সত্য/মিথ্যা এমনভাবে বসানো যায় যে প্রতিটি clause-এ অন্তত একটি literal সত্য। এই পর্বের উদাহরণ সূত্র:
φ = (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z)
তিনটি clause-কে বলব C1, C2, C3. সব ৮টি মান বসিয়ে দেখা যায়, ঠিক ৫টি মান φ-কে সত্য করে।
f(⟨φ⟩) = ⟨G, k⟩, যেখানে φ-এর clause সংখ্যা k, আর G এভাবে:
১. Node: প্রতিটি clause-এর প্রতিটি literal-এর জন্য একটি node; একই clause-এর তিনটি node একটি “ত্রয়ী”। মোট 3k node.
২. Edge: দুটি node-এর মধ্যে edge থাকবে, যদি না (ক) তারা একই ত্রয়ীতে, অথবা (খ) তাদের literal পরস্পরবিরোধী (যেমন x আর ¬x).
প্রতিটি clause-এর ত্রয়ী একটি gadget: উৎস সমস্যার একটি টুকরোকে লক্ষ্য সমস্যার ভাষায় লেখার ছোট কাঠামো। নিচের ছবিতে φ-এর graph, আর সবুজে একটি 3-clique.
φ-এর CLIQUE graph: ৯টি node, ২১টি edge, k = 3
ওপরে C1 = (x ∨ y ∨ z), বাঁয়ে C2 = (¬x ∨ ¬y ∨ z), ডানে C3 = (x ∨ ¬y ∨ ¬z).
1φ = C1 ∧ C2 ∧ C3, k = 32C1 → x, y, z3C2 → ¬x, ¬y, z4C3 → x, ¬y, ¬z5নিয়ম ক: ত্রয়ীর ভেতরে edge নেই6নিয়ম খ: x–¬x ধরনে edge নেই7output ⟨G, 3⟩
| node | |
| প্রার্থী জোড়া | |
| edge |
- Input পড়া। f পায় ⟨φ⟩: তিনটি clause, প্রতিটিতে তিনটি literal. লক্ষ্য k হবে clause-এর সংখ্যা, এখানে 3. f φ-কে কোনো মান বসিয়ে পরীক্ষা করে না; শুধু লেখা পড়ে।
- প্রথম ত্রয়ী। C1 = (x ∨ y ∨ z)-এর তিনটি literal থেকে তিনটি node: C1:x, C1:y, C1:z. একই চলক দুই clause-এ থাকলে দুটি আলাদা node হয়।
- সব ত্রয়ী। C2 থেকে ¬x, ¬y, z; C3 থেকে x, ¬y, ¬z. মোট 3k = ৯টি node, আর মোট জোড়া ৯ × ৮ / ২ = ৩৬টি।
- নিয়ম ক। একই ত্রয়ীর ভেতরের জোড়ায় edge নেই: প্রতিটি ত্রয়ীতে ৩টি, মোট ৯টি জোড়া বাদ। বাকি ২৭টি জোড়া ভিন্ন ত্রয়ীর, তারা edge-এর প্রার্থী।
- নিয়ম খ। প্রার্থীদের মধ্যে ৬টি পরস্পরবিরোধী: C1:x–C2:¬x, C1:y–C2:¬y, C1:y–C3:¬y, C1:z–C3:¬z, C2:¬x–C3:x, C2:z–C3:¬z. এগুলো বাদে ২১টি edge.
- Output. f লেখে ⟨G, 3⟩. সাধারণভাবে node 3k, edge সর্বোচ্চ 9k(k − 1)/2, আর প্রতিটি জোড়ার সিদ্ধান্ত স্থির সময়ে: পুরো f O(k2), অর্থাৎ input-এর দৈর্ঘ্যের polynomial.
3SAT ≤p CLIQUE. তাই (3SAT NP-complete ধরে নিয়ে) CLIQUE NP-complete.
প্রমাণ (“⇒”: φ satisfiable হলে G-তে k-clique আছে):
- একটি satisfying মান নিন। প্রতিটি clause-এ অন্তত একটি literal সত্য; প্রতিটি ত্রয়ী থেকে এমন একটি সত্য literal-এর node বাছুন। মোট k টি node. — বাছাই
- বাছা দুটি node সবসময় ভিন্ন ত্রয়ীর, কারণ প্রতিটি ত্রয়ী থেকে একটিই। — নিয়ম ক পার
- দুটি node পরস্পরবিরোধী হতে পারে না: x আর ¬x একই মানে একসঙ্গে সত্য হয় না, অথচ বাছা সব literal সত্য। — নিয়ম খ পার
- তাই প্রতিটি জোড়ার মধ্যে edge আছে: k টি node একটি clique. — “⇒”
প্রমাণ (“⇐”: G-তে k-clique থাকলে φ satisfiable):
- ত্রয়ীর ভেতরে edge নেই, তাই clique-এর দুটি node একই ত্রয়ীতে থাকতে পারে না; k টি node আর k টি ত্রয়ী, তাই প্রতিটি ত্রয়ী থেকে ঠিক একটি। — pigeonhole
- Clique-এর প্রতিটি literal-কে সত্য করুন: x হলে x = 1, ¬x হলে x = 0. পরস্পরবিরোধী literal-এর মধ্যে edge নেই, তাই একই চলককে দুই মান দিতে হয় না: মানটি সুসংগত। Clique-এ নেই এমন চলকের মান যেকোনো। — মান নির্মাণ
- প্রতিটি clause-এর ত্রয়ী থেকে একটি node clique-এ, আর তার literal সত্য: প্রতিটি clause সত্য, φ সত্য। — “⇐”
- f O(k2) সময়ে চলে; অবৈধ input (3CNF নয়) এলে f একটি স্থির “না” instance দেয়। তাই 3SAT ≤p CLIQUE. CLIQUE ∈ NP (অংশ ৪), তাই উপপাদ্য ৩.৩ অনুযায়ী CLIQUE NP-complete. ∎
অনুসিদ্ধান্ত: উপপাদ্য ৪.২ আর transitivity থেকে INDEPENDENT-SET আর VERTEX-COVER-ও NP-complete. পর্ব ৬১ “NP-complete সমস্যার পরিবার”-এ এই শিকল আরও লম্বা হবে: HAMPATH, SUBSET-SUM, 3-COLOR. DSA কোর্সের পর্ব ৬৪-এ একই পরিবারের একটি ভিন্ন reduction (3-SAT থেকে independent set) algorithm-এর দৃষ্টিতে আছে; এখানে আমরা Turing machine-ভিত্তিক সংজ্ঞা আর পূর্ণ প্রমাণ দেখলাম।
1মান: x=1, y=0, z=02প্রতি clause-এ একটি সত্য literal3৩টি জোড়ায় edge আছে?4উল্টো: clique {C1:y, C2:¬x, C3:¬z}5literal সত্য করুন6φ যাচাই
| C1 | |
| C2 | |
| C3 |
- একটি satisfying মান। x = 1, y = 0, z = 0. C1-এ x সত্য; C2-এ ¬y সত্য; C3-এ তিনটি literal-ই সত্য। তাই φ সত্য।
- প্রতিটি ত্রয়ী থেকে একটি। C1 থেকে x, C2 থেকে ¬y, C3 থেকে ¬z বাছা হলো (C3-এ x বা ¬y বাছলেও চলত; ভিন্ন বাছাই ভিন্ন clique দেয়)।
- Clique কি না। তিনটি জোড়া: x–¬y, x–¬z, ¬y–¬z. প্রতিটি ভিন্ন ত্রয়ীর, আর কোনোটি x–¬x ধরনের নয়, তাই তিনটিতেই edge আছে। ছবি ৫৯.২-এর সবুজ ত্রিভুজ ঠিক এটিই।
- উল্টো দিক। এবার শুধু graph-এর একটি clique দেওয়া হলো: {C1:y, C2:¬x, C3:¬z}. ত্রয়ীর ভেতরে edge নেই বলে প্রতিটি ত্রয়ী থেকে ঠিক একটি node এসেছে।
- মান বানানো। প্রতিটি literal সত্য করুন: y = 1, x = 0, z = 0. বিরোধী জোড়ায় edge নেই, তাই কোনো চলককে দুই মান দিতে হলো না। Clique {C1:x, C2:z, C3:x}-এর মতো ক্ষেত্রে y-এর উল্লেখই নেই; তখন y যেকোনো মান নিতে পারে।
- যাচাই। C1-এ y, C2-এ ¬x, C3-এ ¬z সত্য: φ সত্য। দুই দিকের রূপান্তরই দেখাল, ⟨φ⟩ ∈ 3SAT ⇔ ⟨G, 3⟩ ∈ CLIQUE. একটি সতর্কতা: সংখ্যা মেলে না। এই φ-এর satisfying মান ৫টি, কিন্তু G-তে 3-clique ১২টি।
এবার f-কে কোডে লিখে সব ছোট সূত্রে “⇔” মেলাই। to_clique হুবহু নির্মাণের দুই নিয়ম; has_clique একটি সাধারণ clique-খোঁজা, যা φ সম্পর্কে কিছুই জানে না; আর satisfiable সব 23 মান বসিয়ে দেখে। Literal লেখা হয়েছে সংখ্যায়: 2 মানে x2, −2 মানে ¬x2.
from itertools import combinations, combinations_with_replacement as cwr, product
import random
def to_clique(phi): # 3SAT -> CLIQUE: phi = list of 3-literal clauses
nodes = [(i, lit) for i, c in enumerate(phi) for lit in c] # lit: +v or -v
edges = {(a, b) for a, b in combinations(range(len(nodes)), 2)
if nodes[a][0] != nodes[b][0] # different triples
and nodes[a][1] != -nodes[b][1]} # not x and not-x
return len(nodes), edges, len(phi) # <G, k>
def satisfiable(phi, nvars): # brute force 2^n
return any(all(any((l > 0) == a[abs(l) - 1] for l in c) for c in phi)
for a in product([False, True], repeat=nvars))
def has_clique(n, E, k): # exhaustive search; knows nothing about phi
nb = {v: {u for u in range(n) if (min(u, v), max(u, v)) in E} for v in range(n)}
def grow(size, cand):
return size == k or any(grow(size + 1, {u for u in cand & nb[v] if u > v})
for v in cand)
return grow(0, set(range(n)))
clauses = list(cwr([1, -1, 2, -2, 3, -3], 3)) # all 56 clauses on x1..x3
tests = [[c, d] for c in clauses for d in clauses] # all 3136 with k = 2
rng = random.Random(59)
for k in range(3, 9): # 500 random for each k
tests += [rng.choices(clauses, k=k) for _ in range(500)]
yes = bad = 0
for phi in tests:
s = satisfiable(phi, 3)
yes += s
bad += s != has_clique(*to_clique(phi))
print("formulas:", len(tests), " satisfiable:", yes, " mismatches:", bad)
for k in (1, 10, 100, 200): # size of <G, k>
n, E, _ = to_clique(rng.choices(clauses, k=k))
print(f"k = {k:3}: nodes = {n:3}, edges = {len(E):6}, 9k(k-1)/2 = {9*k*(k-1)//2}")আসল আউটপুট (ব্রাউজারের Python):
formulas: 6136 satisfiable: 5880 mismatches: 0
k = 1: nodes = 3, edges = 0, 9k(k-1)/2 = 0
k = 10: nodes = 30, edges = 355, 9k(k-1)/2 = 405
k = 100: nodes = 300, edges = 37130, 9k(k-1)/2 = 44550
k = 200: nodes = 600, edges = 148927, 9k(k-1)/2 = 179100
তিন চলকের ওপর ৫৬টি সম্ভাব্য clause (একই literal-এর পুনরাবৃত্তিসহ) থেকে দুই clause-এর সব ৩১৩৬টি সূত্র, আর k = 3 থেকে 8-এর প্রতিটির জন্য seed 59-এ ৫০০টি এলোমেলো সূত্র: মোট ৬১৩৬টি। এর ২৫৬টি unsatisfiable, তাই “না” দিকও ভালোভাবে পরীক্ষিত; একটিতেও অমিল নেই। নিচের চার লাইন আকার দেখায়: node ঠিক 3k, আর edge সবসময় 9k(k − 1)/2-এর নিচে, অর্থাৎ k-এর দ্বিঘাত। k দ্বিগুণ হলে (100 → 200) edge প্রায় চারগুণ। লক্ষ করুন, has_clique নিজে exponential হতে পারে; reduction-কে polynomial হতে হয়, লক্ষ্য সমস্যার সমাধানকে নয়।
৬ · সত্যিকারের SAT solver আর graph library দিয়ে যাচাই
ব্রাউজারের brute force ছোট সূত্রে সীমিত। একই reduction দুটি স্বাধীন, বহুল ব্যবহৃত tool দিয়ে মিলিয়ে দেখা হয়েছে: z3-solver (Microsoft Research-এর Z3 SMT solver-এর Python binding, MIT licence) সূত্রের satisfiability বলে, আর networkx (BSD-3-Clause licence) reduction-এর graph-এ সবচেয়ে বড় clique-এর আকার খোঁজে। চার চলকের ওপর প্রতিটি k-এর জন্য ২০টি এলোমেলো 3CNF (seed 59). যেখানে z3 satisfying মান দেয়, script সেই মান থেকে অংশ ৫-এর মতো k টি node বেছে নিশ্চিত করে যে তারা সত্যিই clique. চালানোর আগে দেখা হয়েছে: uv-এর environment variable-এর নথিতে কোনো telemetry নেই, আর এই দুই library-র কোডে কোনো usage-reporting নেই।
~/bazarghar-toc$ uv add z3-solver networkx
+ networkx==3.7
+ z3-solver==5.4.1.0
~/bazarghar-toc$ uv run python sat_vs_clique.py
z3 5.4.1 | networkx 3.7
k nodes sat/20 agree/20 z3_s clique_s
6 18 20 20 0.03 0.00
12 36 20 20 0.03 0.04
18 54 19 20 0.04 0.41
24 72 9 20 0.04 5.74
30 90 5 20 0.05 163.60সত্যিকারের run (Python 3.14, z3-solver 5.4.1.0, networkx 3.7). ১০০টি সূত্রের প্রতিটিতে দুই tool-এর উত্তর মিলেছে (agree কলাম), ৭৩টি satisfiable আর ২৭টি নয়। শেষ দুই কলাম মোট সেকেন্ড, শুধু উদাহরণ হিসেবে, প্রমাণ হিসেবে নয়: z3 প্রতিটি সারিতে প্রায় একই সময় নেয়, কিন্তু networkx-এর সাধারণ সবচেয়ে-বড়-clique algorithm (max_weight_clique) ৯০ node-এ প্রায় তিন মিনিট নেয়। শিক্ষাটি সূক্ষ্ম: 3SAT ≤p CLIQUE দেখায় CLIQUE অন্তত 3SAT-এর মতো কঠিন, কিন্তু এর মানে এই নয় যে 3SAT-কে CLIQUE-এ নিয়ে সমাধান করা বুদ্ধিমানের কাজ। বিশেষায়িত SAT solver-এর কৌশল (পর্ব ৭৩ “বাস্তবে NP-hard সমস্যা”) graph-এ গেলে হারিয়ে যায়। আর এখানে চলক মাত্র ৪টি; বড় কঠিন সূত্রে SAT solver-ও exponential আচরণ দেখাতে পারে।
৭ · NP-completeness প্রমাণের ছাঁচ আর সাধারণ ভুল
নতুন সমস্যা X NP-complete প্রমাণ করতে বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই চার ধাপের কাঠামো নিরাপদ:
- X ∈ NP: certificate কী, আর তার দৈর্ঘ্য কেন polynomial; verifier কী মেলায়, আর কেন polynomial সময়ে।
- উৎস বাছুন: একটি জানা NP-complete A (3SAT, CLIQUE, VERTEX-COVER, …)। লিখুন: “দেখাব A ≤p X.” জানা-কঠিন সমস্যা বাঁয়ে।
- f বর্ণনা করুন আর সময় দেখান: A-এর instance থেকে X-এর instance কীভাবে, আর output-এর আকার ও f-এর সময় কেন polynomial.
- “⇔” দুই দিকে: A-এর “হ্যাঁ” instance থেকে X-এর সমাধান বানান; আর X-এর যেকোনো সমাধান থেকে A-এর সমাধান ফেরত আনুন (শুধু আপনার বানানো সমাধান থেকে নয়)।
সবচেয়ে পরিচিত ভুলটি দিক নিয়ে। নিচের stepper বাজারঘরের কম্বো সমস্যায় একটি ভুল “প্রমাণ” আর তার সংশোধন দেখায়।
1দাবি: COMBO NP-complete2“প্রমাণ”: COMBO ≤p SAT3আসলে কী জানা গেল?4পরীক্ষা: ALLYES ≤p SAT5সংশোধন: IND-SET ≤p COMBO6NP-তে আছে + ⇔
| reduction | |
| যা পাওয়া যায় |
- দাবি। COMBO = {⟨পণ্যের তালিকা, বিরোধী জোড়ার তালিকা, k⟩ : k টি পণ্য আছে, যাদের কোনো দুটি বিরোধী নয়}। দাবি: COMBO NP-complete.
- “প্রমাণ”। একজন লিখলেন: “প্রতিটি পণ্যের জন্য একটি চলক, প্রতিটি বিরোধী জোড়ার জন্য (¬p ∨ ¬q), আর ‘অন্তত k টি সত্য’ শর্ত CNF-এ লিখলাম। তাই COMBO ≤p SAT, আর SAT NP-complete, তাই COMBO NP-complete.” Encoding ঠিক হতে পারে, কিন্তু দিক উল্টো।
- আসলে কী জানা গেল? উপপাদ্য ২.৩: SAT ∈ NP, তাই COMBO ∈ NP. আর কাজের কথা: COMBO SAT solver দিয়ে সমাধান করা যায়। কিন্তু কঠিনতা ≤p-এর বাঁ থেকে ডানে যায়; COMBO বাঁয়ে, তাই তার কঠিনতা সম্পর্কে কিছুই নয়।
- পরীক্ষা। একই যুক্তি একটি তুচ্ছ সমস্যায় চালান: ALLYES = Σ∗ (প্রতিটি string-এর উত্তর “হ্যাঁ”)। f(w) = ⟨x⟩ (সবসময় একটি satisfiable সূত্র) দিয়ে ALLYES ≤p SAT. ভুল যুক্তিটি তাহলে ALLYES-কে NP-hard বলত। কিন্তু তা নিশ্চিতভাবে মিথ্যা: SAT ≤p ALLYES হলে একটি unsatisfiable সূত্রকে ALLYES-এর বাইরে পাঠাতে হতো, অথচ বাইরে কোনো string-ই নেই।
- সংশোধন। জানা-কঠিন থেকে নতুনের দিকে: f(⟨G, k⟩) = ⟨V-কে পণ্য, E-কে বিরোধী জোড়া, k⟩. G-তে k আকারের independent set ⇔ k টি পারস্পরিক বিরোধহীন পণ্য। f শুধু নাম বদলায়, তাই রৈখিক সময়। INDEPENDENT-SET ≤p COMBO, তাই COMBO NP-hard.
- NP-তে আছে, ⇔ দুই দিকে। Certificate: k টি পণ্যের তালিকা; verifier সব k(k − 1)/2 জোড়া বিরোধী তালিকায় খোঁজে, polynomial. “⇔”-এর দুই দিক ধাপ ৫-এ, কারণ f একটি হুবহু নাম-বদল। চার ধাপ পূর্ণ: COMBO NP-complete. ∎
নিচের JavaScript সাহায্যকারী দিকের নিয়ম যান্ত্রিকভাবে প্রয়োগ করে: জানা তথ্য আর একটি দাবি করা reduction দিলে শুধু বৈধ সিদ্ধান্তগুলো টানে। NEWPROB মানে যে নতুন সমস্যার কিছুই জানা নেই।
// What may you conclude from "A <=p B"? Known facts in, valid conclusions out.
const known = { // inP: in P; inNP: in NP; hard: NP-hard (proven)
"2SAT": { inP: true, inNP: true }, PATH: { inP: true, inNP: true },
"3SAT": { inNP: true, hard: true }, CLIQUE: { inNP: true, hard: true },
NEWPROB: {}, // nothing known yet
};
function conclude(A, B) { // the only valid moves
const a = known[A], b = known[B], out = [];
if (b.inP) out.push(`${A} in P`); // B easy => A easy
if (b.inNP) out.push(`${A} in NP`);
if (a.hard) out.push(`${B} NP-hard`); // A hard => B hard
if (a.hard && b.inP) out.push("P = NP (!)");
return out;
}
function check(A, B, claim) {
const out = conclude(A, B);
let v = out.includes(claim) ? "valid" : "does NOT follow";
if (out.includes("P = NP (!)")) v += " [such f would settle P vs NP]";
console.log(`${A} <=p ${B} => "${claim}" : ${v}`);
}
check("3SAT", "NEWPROB", "NEWPROB NP-hard"); // right direction
check("NEWPROB", "3SAT", "NEWPROB NP-hard"); // classic mistake
check("NEWPROB", "3SAT", "NEWPROB in NP"); // what it does give
check("2SAT", "NEWPROB", "NEWPROB NP-hard"); // source is easy: nothing
check("NEWPROB", "PATH", "NEWPROB in P"); // easy side: in P
check("3SAT", "2SAT", "2SAT NP-hard"); // nobody knows such an fআসল আউটপুট (ব্রাউজারের JavaScript):
3SAT <=p NEWPROB => "NEWPROB NP-hard" : valid
NEWPROB <=p 3SAT => "NEWPROB NP-hard" : does NOT follow
NEWPROB <=p 3SAT => "NEWPROB in NP" : valid
2SAT <=p NEWPROB => "NEWPROB NP-hard" : does NOT follow
NEWPROB <=p PATH => "NEWPROB in P" : valid
3SAT <=p 2SAT => "2SAT NP-hard" : valid [such f would settle P vs NP]
প্রথম দুই লাইন একই সিদ্ধান্ত চায়, কিন্তু শুধু প্রথমটি বৈধ। তৃতীয় লাইন দেখায় উল্টো দিকের reduction আসলে কী দেয়: NP-তে থাকা। চতুর্থ লাইন আরেকটি ভুল: 2SAT P-তে আছে, তাই 2SAT থেকে reduce করে কোনো কঠিনতা আসে না, যত চতুর gadget-ই হোক। পঞ্চম লাইন সহজতার দিক: P-এর সমস্যায় reduce হলে নতুন সমস্যা P-তে। শেষ লাইনটি সতর্কবার্তা: 3SAT ≤p 2SAT সত্যিই পাওয়া গেলে 3SAT ∈ P, অর্থাৎ P = NP হতো। কেউ এমন f দেখালে প্রায় নিশ্চিতভাবে তার f polynomial নয় বা “⇔” ভাঙা; তবে এমন f যে নেই, তা প্রমাণিত নয়, কারণ সেটি P ≠ NP প্রমাণের সমান।
| ভুল | কেমন দেখায় | কীভাবে ধরবেন |
|---|---|---|
| উল্টো দিক | X ≤p SAT দেখিয়ে “X NP-hard” | যুক্তিটি ALLYES-এ চালান; তাকেও NP-hard বললে যুক্তি ভুল |
| P-এর সমস্যা থেকে reduce | 2SAT ≤p X বা PATH ≤p X দিয়ে “X কঠিন” | উৎস সত্যিই NP-complete কি না দেখুন |
| Exponential আকার | f প্রতিটি সম্ভাব্য মানের জন্য একটি করে অংশ লেখে, বা CNF-কে DNF-এ খোলে | Output-এর আকার input-এর দৈর্ঘ্যের কোন function, হিসাব করুন |
| “⇔”-এর এক দিক | শুধু “φ satisfiable হলে clique আছে” দেখানো | লক্ষ্যের যেকোনো সমাধান থেকে উৎসের সমাধান ফেরত আনুন |
| “X ∈ NP” বাদ | শুধু reduction দিয়ে “NP-complete” | Reduction শুধু NP-hard দেয়; certificate আর verifier আলাদা করে লিখুন |
| Optimisation আর decision গুলিয়ে ফেলা | “সবচেয়ে বড় clique খোঁজা NP-complete” | NP-complete শুধু language বা decision problem; bound k-সহ রূপ লিখুন |
তৃতীয় সারির একটি উদাহরণ দেখুন। (x1 ∨ y1) ∧ (x2 ∨ y2) ∧ … ∧ (xn ∨ yn)-কে DNF-এ (ORs of ANDs) খুললে 2n টি পদ হয়। তাই “CNF-কে DNF-এ খুলে DNF-এর satisfiability পরীক্ষা” কোনো polynomial reduction নয়, যদিও DNF-এর satisfiability সহজ। ভুল সময়-বিশ্লেষণ এভাবে “P = NP প্রমাণ” তৈরি করে।
আরও গভীরে: পরিচিত প্রায় সব NP-complete সমস্যা আরও দুর্বল reduction-এও (যেমন logarithmic space-এ চলা f) পরস্পরের সঙ্গে যুক্ত, যা পর্ব ৬৬-এর বিষয়ের সঙ্গে মেলে। ১৯৭৭ সালে Berman আর Hartmanis অনুমান করেন যে সব NP-complete সমস্যা আসলে polynomial-time isomorphic, অর্থাৎ একই সমস্যার ভিন্ন “নাম”; এই isomorphism conjecture আজও খোলা, আর এটি সত্য হলে P ≠ NP হতো। আবার P ≠ NP হলে NP-তে এমন সমস্যাও আছে যা P-তে নেই, NP-complete-ও নয় (Ladner ১৯৭৫), যা পর্ব ৬৩-এ।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- A ≤p B-এর সংজ্ঞা দিন। Polynomial-time computable f, যাতে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B.
- NP-hard আর NP-complete-এর পার্থক্য? NP-complete = NP-hard এবং NP-তে; NP-hard সমস্যা NP-এর বাইরেও হতে পারে।
- একটি NP-complete সমস্যা P-তে হলে কী হয়? P = NP, কারণ NP-এর প্রতিটি সমস্যা তাতে ≤p হয়।
- 3SAT ≤p CLIQUE-এর গঠন? প্রতিটি clause-এ তিনটি node, একই ত্রয়ী আর বিরোধী literal ছাড়া সব জোড়ায় edge, k = clause-এর সংখ্যা।
- Independent set আর vertex cover-এর সম্পর্ক? S independent ⇔ V ∖ S vertex cover, তাই k ↔ n − k.
৮ · AI-এর যুগে NP-completeness প্রমাণ যাচাই
AI assistant-কে “X NP-complete প্রমাণ করুন” বললে প্রায়ই সুন্দর গোছানো উত্তর আসে, যার ভেতরে অংশ ৭-এর ভুলগুলো লুকিয়ে থাকে। সবচেয়ে সাধারণ: উল্টো দিকে reduce করা (“X-কে SAT-এ encode করা যায়, তাই NP-hard”), “⇔”-এর শুধু একটি দিক, gadget-এর আকার না গুনে polynomial দাবি, X ∈ NP অংশ বাদ, optimisation আর decision গুলিয়ে ফেলা, আর “P = NP প্রমাণিত” বা “NP মানে non-polynomial” ধরনের ভুল তথ্য। কখনো কখনো ভুল সাল বা বানানো রেফারেন্সও আসে।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “X ≤p 3SAT, তাই X NP-hard” | প্রতিটি ≤p-এ জিজ্ঞেস করুন: জানা-কঠিন সমস্যা বাঁয়ে তো? Direction drill-এ চালান |
| শুধু “হ্যাঁ ⇒ হ্যাঁ” দেখানো | লক্ষ্যের যেকোনো সমাধান থেকে উৎসের সমাধান ফেরত আনতে বলুন; ছোট instance-এ brute force-এ দুই দিক মেলান |
| “f polynomial” কোনো হিসাব ছাড়া | Node, edge বা সংখ্যার আকার input-এর দৈর্ঘ্যে গুনুন; সংখ্যা binary-তে লেখা কি না দেখুন |
| “সবচেয়ে বড় clique NP-complete” | Decision রূপ (bound k-সহ) লিখতে বলুন; optimisation রূপ NP-hard, NP-complete নয় |
| বানানো রেফারেন্স বা ভুল সাল | Sipser (NP-completeness অধ্যায়), Garey–Johnson বা Arora–Barak-এ নিজে মিলিয়ে নিন |
AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণের কাঠামো নিজে ঠিক করে দিন, আর প্রতিটি ধাপ আলাদা করে লিখতে বলুন, যাতে আপনি একটি একটি করে যাচাই করতে পারেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১পর্ব ৫২-এ reduction-এর f-কে শুধু computable হতে হতো। এখানে polynomial-time কেন? f-কে আরও দুর্বল, বা আরও শক্তিশালী হতে দিলে কী ঘটে?
Reduction-এর কাজ দুটি সমস্যার তুলনা, আর তুলনা অর্থবহ হয় শুধু তখন, যখন অনুবাদের খরচ যে সম্পদ মাপা হচ্ছে তার তুলনায় নগণ্য। Computability-র জগতে মাপা হয় “আদৌ সমাধান আছে কি না”, তাই যেকোনো থামা f চলে। Complexity-র জগতে মাপা হয় “polynomial সময়ে সমাধান আছে কি না”, তাই f-কে polynomial সময়ে চলতে হয়; নইলে f নিজেই সব কাজ সেরে ফেলতে পারে।
চরম উদাহরণ: f-কে exponential সময় দিলে SAT ≤ {1} সত্য হয়ে যায়: f সব 2n মান বসিয়ে φ satisfiable হলে “1”, নইলে “0” লেখে। তখন দিকের নিয়ম বলত, {1} ∈ P বলে SAT ∈ P, যা একটি অর্থহীন সিদ্ধান্ত, কারণ কঠিন কাজটি f-এর ভেতরে লুকিয়ে আছে। সাধারণভাবে, যে শ্রেণি নিয়ে কথা হচ্ছে, f-এর ক্ষমতা তার চেয়ে বেশি হলে সেই শ্রেণির প্রায় প্রতিটি অ-তুচ্ছ সমস্যা “complete” হয়ে যায়, আর completeness ধারণাটি কোনো তথ্য বহন করে না।
আরও দুর্বল f-এর প্রয়োজনও আছে। P-এর ভেতরের সূক্ষ্ম পার্থক্য নিয়ে কথা বলতে polynomial-time reduction কাজে আসে না: P-এর যেকোনো দুটি অ-তুচ্ছ সমস্যা polynomial সময়ে পরস্পরে reduce হয়, কারণ f নিজেই উৎস সমস্যা সমাধান করতে পারে। তাই “P-complete” সমস্যার জন্য (সমান্তরালে দ্রুত করা কঠিন বলে মনে করা হয় এমন সমস্যা) logarithmic space-এ চলা reduction ব্যবহার হয়, আর NL-এর জন্যও একই। পর্ব ৬৬-এ এই logspace reduction দেখবেন।
মজার ব্যাপার হলো, polynomial শর্তটি খুব স্বাভাবিকভাবে বসে যায়, কারণ polynomial-এর composition আবার polynomial. তাই reduction-এর শিকল যত লম্বাই হোক, তা polynomial থাকে, আর transitivity বিনা খরচে পাওয়া যায়। n2 বা n3-এর বদলে যদি “n log n সময়” শর্ত দেওয়া হতো, তাহলে composition-এ তা ভেঙে যেত; শ্রেণির এই স্থিতিশীলতাই P-কে একটি স্বাভাবিক শ্রেণি বানায়।
মূল উপলব্ধি: f-এর ক্ষমতা মাপা সম্পদের সমান বা কম হতে হয়; polynomial-time reduction NP-এর জন্য ঠিক মাপের, আর এর composition-বন্ধতাই reduction-এর শিকলকে বৈধ রাখে।
প্র ০২Cook ১৯৭১ সালে oracle-ধরনের (Turing) reduction ব্যবহার করেন, আর Karp ১৯৭২ সালে mapping reduction. NP-completeness-এর সংজ্ঞায় কোনটি নেওয়া হলো, তাতে কী এসে যায়?
Polynomial-time Turing reduction (A ≤Tp B) মানে: B-এর একটি oracle থাকলে A polynomial সময়ে সমাধান করা যায়, আর oracle-কে যতবার খুশি প্রশ্ন করা ও উত্তর উল্টানো চলে। Mapping (Karp) reduction এর একটি বিশেষ রূপ: oracle-কে ঠিক একবার প্রশ্ন, আর তার উত্তরই হুবহু চূড়ান্ত উত্তর। প্রশ্ন হলো, কোনটি দিয়ে “NP-complete” সংজ্ঞায়িত হবে।
পার্থক্যটি সবচেয়ে স্পষ্ট হয় complement-এ। UNSAT = unsatisfiable সূত্রের language. Turing reduction-এ UNSAT ≤Tp SAT তুচ্ছ: SAT oracle-কে জিজ্ঞেস করুন আর উত্তর উল্টে দিন। তাই Turing reduction-এর ভাষায় SAT আর UNSAT “সমান কঠিন”, আর UNSAT-ও “NP-hard”. কিন্তু UNSAT NP-তে আছে কি না জানা নেই; বেশিরভাগ গবেষক মনে করেন নেই, কারণ তা হলে NP = coNP হতো (পর্ব ৬২)। Mapping reduction এই পার্থক্য রক্ষা করে: A ≤p B আর B ∈ NP হলে A ∈ NP (উপপাদ্য ২.৩). তাই Karp-এর সংজ্ঞায় NP-complete সমস্যা সবসময় NP-এর ভেতরে, আর NP ও coNP আলাদা থাকে।
এর একটি ঐতিহাসিক মজা আছে। Cook-এর প্রবন্ধের মূল ফল আজকের ভাষায় বলা হয় Turing reduction দিয়ে, তবু তাঁর প্রমাণ (পর্ব ৬০-এর tableau) আসলে একটি mapping reduction দেয়: প্রতিটি input থেকে একটি সূত্র, যা satisfiable ঠিক তখন, যখন input গ্রহণযোগ্য। Karp-এর প্রবন্ধ দেখায় যে mapping reduction-ই এত সমস্যাকে এক সুতোয় গাঁথার জন্য যথেষ্ট। পরে এটি মানক হয়ে যায়, কারণ এটি দুর্বল (তাই প্রমাণ বেশি তথ্য বহন করে) আর গঠনে সহজ।
ব্যবহারিক পরামর্শ: শুধু “polynomial algorithm নেই, যদি না P = NP” বলতে হলে Turing reduction যথেষ্ট, আর প্রায়ই সহজ (যেমন optimisation সমস্যার কঠিনতা)। কিন্তু “NP-complete” শব্দটি ব্যবহার করলে Karp reduction দেখান। পর্ব ৬২-এ search-to-decision reduction দেখবেন, যা স্বভাবতই Turing ধরনের।
মূল উপলব্ধি: Karp reduction NP-এর সদস্যপদ রক্ষা করে আর NP ও coNP-এর পার্থক্য মুছে দেয় না; তাই NP-completeness-এর মানক সংজ্ঞা mapping reduction দিয়ে।
প্র ০৩3SAT ≤p CLIQUE হ্যাঁ/না রক্ষা করে, কিন্তু উদাহরণ φ-তে satisfying মান ৫টি আর 3-clique ১২টি। সমাধানের সংখ্যা রক্ষা না হওয়া কি সমস্যা? কোথায় এটি জরুরি হয়ে ওঠে?
NP-completeness-এর জন্য সমস্যা নয়। সংজ্ঞা শুধু চায় w ∈ A ⇔ f(w) ∈ B, অর্থাৎ “অন্তত একটি সমাধান আছে” রক্ষা পেলেই যথেষ্ট। সংখ্যা কেন মেলে না, তা নির্মাণ থেকেই বোঝা যায়। এক দিকে, একটি satisfying মানে কোনো clause-এ একাধিক literal সত্য হলে আমরা যেকোনোটি বাছতে পারি: x = 1, y = 0, z = 0-এ C3-এর তিনটি literal-ই সত্য, তাই এক মান থেকেই তিনটি ভিন্ন clique. অন্য দিকে, যে চলক clique-এ উল্লেখ নেই, তার মান মুক্ত: clique {C1:x, C2:z, C3:x} থেকে y = 0 বা 1, দুটি মান। তাই মান আর clique-এর মধ্যে সম্পর্ক অনেক-থেকে-অনেক।
সংখ্যা জরুরি হয় গণনার সমস্যায়: “কতগুলো সমাধান আছে?” Leslie Valiant ১৯৭৯ সালে #P নামে গণনা-সমস্যার শ্রেণি দেন, আর দেখান যে bipartite graph-এ perfect matching গোনাও #P-complete, যদিও একটি perfect matching খুঁজে পাওয়া polynomial সময়ে হয়। এখানে কঠিনতা স্থানান্তরের জন্য এমন reduction লাগে, যা সমাধানের সংখ্যা হুবহু রক্ষা করে, যার নাম parsimonious reduction, অথবা অন্তত সংখ্যাকে নিয়ন্ত্রিতভাবে বদলায় (যেমন সবসময় একটি জানা গুণক দিয়ে)।
Cook–Levin-এর tableau-ভিত্তিক reduction-কে সামান্য যত্নে parsimonious করা যায়, আর SAT থেকে 3SAT-ও। কিন্তু Sipser-এর 3SAT → CLIQUE, যেমন ওপরের brute force দেখিয়েছে, তা নয়। তাই কেউ যদি বলেন “#CLIQUE কঠিন, কারণ 3SAT → CLIQUE আছে”, তাঁর যুক্তি অসম্পূর্ণ; আলাদা নির্মাণ লাগে।
আরেকটি ক্ষেত্র: randomized algorithm আর cryptography-তে “ঠিক একটি সমাধান আছে” এমন instance-এর কঠিনতা জরুরি। Valiant আর Vazirani ১৯৮৬ সালে দেখান, এলোমেলো শর্ত যোগ করে SAT-কে এমনভাবে বদলানো যায় যে অনেক সময় ঠিক একটি সমাধান থাকে। এগুলো সবই দেখায়, reduction কী রক্ষা করে, তা প্রতিটি প্রয়োগে আলাদা করে প্রশ্ন করতে হয়।
মূল উপলব্ধি: সাধারণ ≤p শুধু হ্যাঁ/না রক্ষা করে; সমাধানের সংখ্যা, গঠন বা আনুমানিক মান রক্ষার দাবি করতে হলে reduction-কে সেই বাড়তি শর্তও আলাদা করে প্রমাণ করতে হয়।
প্র ০৪INDEPENDENT-SET আর VERTEX-COVER-এর reduction হুবহু উত্তর রক্ষা করে। তবু বাস্তবে vertex cover-এর ভালো আনুমানিক সমাধান সহজ, অথচ clique বা independent set-এর নয়। এটি কীভাবে সম্ভব?
Decision রূপে তিন সমস্যা সমান কঠিন: অংশ ৪-এর f আর g প্রতিটি “হ্যাঁ/না” প্রশ্ন হুবহু অনুবাদ করে। কিন্তু আনুমানিক সমাধানের (approximation) প্রশ্নে মাপকাঠি ভিন্ন। Vertex cover-এর জন্য খুব সরল একটি algorithm আছে: একটি edge নিন, তার দুই প্রান্তই cover-এ রাখুন, সেই দুই vertex ছোঁয়া সব edge মুছে দিন, আবার করুন। এভাবে পাওয়া cover সবচেয়ে ছোট cover-এর সর্বোচ্চ দ্বিগুণ, কারণ বাছা edge-গুলোর কোনো দুটি একই vertex ছোঁয় না, আর যেকোনো cover-কে প্রতিটি বাছা edge-এর অন্তত এক প্রান্ত নিতে হয়।
এখন এই ফলকে independent set-এ নিতে চেষ্টা করুন। ধরুন n = 1000, আর সবচেয়ে ছোট cover-এর আকার 600; তাহলে সবচেয়ে বড় independent set 400. দ্বিগুণ-algorithm সর্বোচ্চ 1000 আকারের cover দিতে পারে, যার পরিপূরক independent set-এর আকার 0. অর্থাৎ cover-এ “দ্বিগুণের মধ্যে” থাকা independent set-এ কোনো নিশ্চয়তাই দেয় না। কারণ n − k রূপান্তর হুবহু উত্তর রাখে, কিন্তু অনুপাত রাখে না।
তত্ত্ব আরও এগিয়েছে। PCP theorem (১৯৯০-এর দশকের শুরু) থেকে আসা ফল অনুযায়ী, P ≠ NP ধরে নিলে clique-এর আকার n1−ε গুণকের ভেতরে আনুমান করাও polynomial সময়ে অসম্ভব, যেকোনো স্থির ε > 0-এর জন্য; Håstad (১৯৯৯) এটি একটু শক্ত একটি অনুমানে দেখান, আর Zuckerman (২০০৭) শুধু P ≠ NP অনুমানে নামিয়ে আনেন। অথচ vertex cover-এ ২ গুণক সহজ। আর ২-এর চেয়ে ভালো গুণক সম্ভব কি না, তা Unique Games Conjecture নামের একটি খোলা অনুমানের সঙ্গে জড়িত, তাই হেজ করে বলা দরকার।
শিক্ষা: “NP-complete” একটি মোটা লেবেল। একই লেবেলের সমস্যা বাস্তবে খুব ভিন্ন আচরণ করতে পারে: কোনোটির ভালো আনুমানিক সমাধান সহজ, কোনোটির ছোট parameter-এ দ্রুত algorithm আছে (vertex cover k ছোট হলে), কোনোটি দুটোতেই কঠিন। এসবের জন্য আলাদা ধরনের reduction লাগে, যেমন approximation-preserving বা parameterized reduction, যা পর্ব ৭১ আর ৭২-এ আসবে। DSA কোর্সের পর্ব ৬৫-এ ব্যবহারিক দিক আছে।
মূল উপলব্ধি: ≤p হ্যাঁ/না-র কঠিনতা স্থানান্তর করে, আনুমানিকতার নয়; সমান-কঠিন decision সমস্যার optimisation রূপ বাস্তবে খুব আলাদা হতে পারে।
প্র ০৫একটি সমস্যা NP-complete প্রমাণ হওয়ার পর একজন প্রকৌশলীর কী করা উচিত? “এটা অসম্ভব” বলে থেমে যাওয়া কি ঠিক?
না। NP-completeness বলে না যে প্রতিটি instance কঠিন, বা ছোট instance-এ সমাধান করা যায় না। এটি বলে: সব instance-এ সবসময় সঠিক উত্তর দেয় আর worst case-এ polynomial সময়ে চলে, এমন algorithm পেলে P = NP হতো। বাস্তবের বাজারঘর-এর ৩০টি জেলার ডেলিভারি রুট বা ২০০ পণ্যের কম্বো প্রশ্ন প্রায়ই ভালো পদ্ধতিতে সমাধান করা যায়।
Michael Garey আর David Johnson-এর ১৯৭৯ সালের বই “Computers and Intractability” এই দৃষ্টিভঙ্গি জনপ্রিয় করে। বইয়ের শুরুর একটি কার্টুনে এক কর্মী বসকে বলেন, ধরনটা এমন: “আমি দ্রুত algorithm পাইনি, কিন্তু এই বিখ্যাত মানুষেরাও পাননি।” মূল কথা: NP-completeness প্রমাণ একটি তথ্য, যা খোঁজার দিক বদলে দেয়, হাল ছেড়ে দেওয়ার অনুমতি নয়।
এরপর বিকল্পগুলো: (১) বিশেষ ক্ষেত্র খুঁজুন। আপনার graph কি tree, bipartite বা planar? অনেক NP-complete সমস্যা এসব ক্ষেত্রে P-তে; যেমন 2SAT P-তে, যদিও 3SAT নয়। (২) Parameter ছোট কি না দেখুন: vertex cover-এ k ছোট হলে মোটামুটি 2k × input-এর আকার ধাপে সমাধান হয় (পর্ব ৭২)। (৩) Approximation: ভালো-যথেষ্ট উত্তর, নিশ্চিত গুণকসহ (পর্ব ৭১)। (৪) SAT বা ILP solver: বাস্তবের অনেক বড় instance এরা দ্রুত সমাধান করে, যদিও worst case-এ exponential (পর্ব ৭৩)। (৫) Heuristic, কিন্তু সৎ লেবেলে।
এখানে একটি নৈতিক দায়ও আছে। কোনো heuristic-কে “NP-complete সমস্যার polynomial algorithm” বলে বিক্রি করা ভুল। আবার উল্টোটিও ভুল: ছোট instance-এ brute force যথেষ্ট হলেও “NP-complete, তাই অসম্ভব” বলে কাজ ফেলে রাখা। পর্ব ৬১-এ দেখবেন কীভাবে বাস্তবের scheduling বা routing সমস্যার ভেতরে লুকানো NP-complete কাঠামো চেনা যায়, আর DSA কোর্সের পর্ব ৬৫-এ এর ব্যবহারিক কৌশল।
মূল উপলব্ধি: NP-completeness প্রমাণ বলে “সাধারণ, সবসময়-দ্রুত, সবসময়-সঠিক algorithm আশা করবেন না”; এরপর বিশেষ ক্ষেত্র, parameter, approximation আর solver-এর দিকে যাওয়াই প্রকৌশলীর কাজ।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। is_clique_vc.py আর sat_to_clique.py ব্লকে নিজের graph বা সূত্র দিয়ে উত্তর যাচাইও করতে পারেন।
-
নির্মাণ: HALF-CLIQUE = {⟨G⟩ : G-এর vertex সংখ্যা n জোড়, আর G-তে n/2 আকারের clique আছে}। CLIQUE ≤p HALF-CLIQUE-এর একটি reduction নকশা করুন, “⇔” প্রমাণ করুন, আর দেখান HALF-CLIQUE NP-complete.
ধারণা (padding): লক্ষ্য k-কে নতুন graph-এর অর্ধেক বানাতে vertex যোগ করুন। ⟨G, k⟩, |V| = n, 1 ≤ k ≤ n হলে (k > n হলে উত্তর “না”, তাই f একটি স্থির “না” instance দেয়, যেমন ৪টি বিচ্ছিন্ন vertex-এর graph, যেখানে 2-clique নেই; k = 0 হলে উত্তর “হ্যাঁ”, তাই একটি স্থির “হ্যাঁ” instance, যেমন ২টি বিচ্ছিন্ন vertex-এর graph):
(ক) 2k ≥ n: 2k − n টি বিচ্ছিন্ন vertex যোগ করুন; নতুন n′ = 2k. বিচ্ছিন্ন vertex কোনো ২-বা-বড় clique-এ ঢোকে না, তাই G′-তে k-clique ⇔ G-তে k-clique. (k = 1-এ উভয় দিকেই উত্তর “হ্যাঁ”।)
(খ) 2k < n: n − 2k টি নতুন vertex যোগ করুন, যারা পরস্পরের সঙ্গে আর G-এর সবার সঙ্গে যুক্ত; n′ = 2n − 2k, লক্ষ্য n′/2 = n − k. “⇒”: G-এর k-clique আর নতুন n − 2k টি মিলে n − k আকারের clique. “⇐”: G′-এর n − k আকারের clique থেকে নতুন vertex (সর্বোচ্চ n − 2k টি) বাদ দিলে G-এর অন্তত k টি vertex থাকে, যারা clique.
f O(n2) সময়ে চলে। HALF-CLIQUE ∈ NP (certificate: n/2 টি vertex). উপপাদ্য ৩.৩ অনুযায়ী HALF-CLIQUE NP-complete. ∎ ৫টি পর্যন্ত vertex-এর সব graph আর 1 ≤ k ≤ n-এর ৫৪০৫টি instance-এ scratch-এ brute force চালিয়ে কোনো অমিল পাওয়া যায়নি।
-
প্রমাণ (ভুল খুঁজুন): একজন লিখেছেন: “VERTEX-COVER ≤p CLIQUE: f(⟨G, k⟩) = ⟨Ḡ, k⟩. লেমা ৪.১ অনুযায়ী cover আর clique complement graph-এ মেলে।” ভুলটি কোথায়? একটি ছোট counterexample দিন আর সংশোধন করুন।
ভুল: লেমা ৪.১(ক) independent set আর clique-কে মেলায়, cover-কে নয়। k আকারের cover-এর পরিপূরক n − k আকারের independent set, তাই লক্ষ্য হওয়া উচিত n − k.
Counterexample: G = ত্রিভুজ (n = 3), k = 2. যেকোনো দুটি vertex সব edge ছোঁয়: ⟨G, 2⟩ ∈ VERTEX-COVER. Ḡ-তে কোনো edge নেই, তাই 2-clique নেই: ⟨Ḡ, 2⟩ ∉ CLIQUE. “⇔” ভাঙল।
সংশোধন: f(⟨G, k⟩) = ⟨Ḡ, n − k⟩. ত্রিভুজে n − k = 1, আর Ḡ-তে 1-clique আছে: মিলল। সাধারণ প্রমাণ: k আকারের cover C ⇔ V ∖ C independent (n − k আকার) ⇔ V ∖ C Ḡ-তে clique. Scratch-এ n ≤ 3-এর সব graph-এ ভুল f ১০টি instance-এ অমিল দেখায়, আর সংশোধিত f n ≤ 5-এ কোনো অমিল দেখায় না।
-
ফল অনুমান: φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z). 3SAT → CLIQUE reduction-এ (ক) node কয়টি, k কত? (খ) edge কয়টি, আর কোন জোড়াগুলো বাদ? (গ) G-তে 2-clique কয়টি, আর φ-এর satisfying মান কয়টি? (ঘ) দুটি সংখ্যা সমান হলে কি তা কোনো নিয়ম?
(ক) 3k = 6 টি node, k = 2.
(খ) ভিন্ন ত্রয়ীর জোড়া ৩ × ৩ = ৯টি; পরস্পরবিরোধী x–¬x, y–¬y, ¬z–z, এই ৩টি বাদ: ৬টি edge.
(গ) 2-clique মানে একটি edge, তাই ৬টি। Satisfying মান: প্রথম clause শুধু x = 0, y = 0, z = 1-এ মিথ্যা; দ্বিতীয়টি শুধু x = 1, y = 1, z = 0-এ মিথ্যা; তাই ৮ − ২ = ৬টি। Scratch-এ চালিয়ে ঠিক এই সংখ্যাগুলো পাওয়া গেছে।
(ঘ) না, এটি কাকতালীয়। অংশ ৫-এর φ-তে ৫টি মান কিন্তু ১২টি 3-clique. Reduction শুধু “অন্তত একটি আছে” রক্ষা করে (ভাবনার প্রশ্ন ৩)।
-
প্রমাণ: ধরুন P = NP. প্রমাণ করুন, তাহলে ∅ আর Σ∗ ছাড়া NP-এর প্রতিটি language NP-complete. আর ব্যাখ্যা করুন, কেন ∅ আর Σ∗ কখনোই NP-complete নয়।
প্রমাণ: ১. B ∈ NP নিন, B ≠ ∅, B ≠ Σ∗; একটি yin ∈ B আর একটি yout ∉ B ঠিক করে রাখুন (স্থির string). ২. যেকোনো L ∈ NP নিন; P = NP বলে L-এর একটি polynomial-time decider D আছে। ৩. f(w) = “D-কে w-এ চালান; গ্রহণ করলে yin, নইলে yout লিখুন।” f polynomial সময়ে চলে। ৪. w ∈ L ⇔ f(w) = yin ⇔ f(w) ∈ B. তাই L ≤p B, আর B NP-hard; B ∈ NP, তাই NP-complete. ∎
∅ আর Σ∗: SAT ≤p ∅ হলে একটি satisfiable সূত্রকে ∅-এর ভেতরে পাঠাতে হতো, যা অসম্ভব; SAT ≤p Σ∗ হলে একটি unsatisfiable সূত্রকে বাইরে পাঠাতে হতো, তাও অসম্ভব। এই যুক্তি P = NP হোক বা না হোক, সবসময় খাটে। লক্ষ করুন, ধাপ ৩-এর f নিজেই L সমাধান করছে: P = NP হলে polynomial f-এর হাতে এত ক্ষমতা আসে, যা ভাবনার প্রশ্ন ১-এর সতর্কবার্তার একটি রূপ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমনতুন সমস্যা X NP-complete প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- X ∈ NP দেখানো: certificate আর polynomial-time verifier
- একটি জানা NP-complete সমস্যা A বাছা, যেমন 3SAT
- A-এর instance থেকে X-এর instance বানানোর f বর্ণনা করা
- f-এর সময় আর output-এর আকার polynomial, তা দেখানো
- “⇔”-এর দুই দিক প্রমাণ করে উপসংহার: X NP-complete
A ≤p B (polynomial-time mapping reduction) জানা আছে। কোন সিদ্ধান্তটি সবসময় বৈধ?
- B NP-hard হলে A NP-hard
- B ∈ P হলে A ∈ P
- A ∈ P হলে B ∈ P
- A ∈ NP হলে B ∈ NP
একটি language B-কে NP-complete বলা হয় কখন?
- B-এর প্রতিটি “হ্যাঁ” instance-এর polynomial-time যাচাইযোগ্য certificate আছে
- NP-এর প্রতিটি language B-তে ≤p
- B-এর কোনো polynomial-time algorithm নেই বলে প্রমাণিত
- B ∈ NP, আর NP-এর প্রতিটি language B-তে ≤p
Sipser-এর 3SAT → CLIQUE reduction-এ 8 টি clause-এর একটি 3CNF সূত্র থেকে graph G আর লক্ষ্য k পাওয়া যায়। G-এর node সংখ্যা আর k কত?
- node = চলকের সংখ্যা, k = 8
- node = 24, k = 3
- node = 24, k = 8
- node = 8, k = 8
G-তে 9 টি vertex আছে, আর G-তে 4 আকারের একটি independent set আছে। নিচের কোনটি অবশ্যই সত্য?
- G-তে 5 আকারের একটি vertex cover আছে
- G-তে 4 আকারের একটি vertex cover আছে
- G-তে 4 আকারের একটি clique আছে
- Ḡ-তে 5 আকারের একটি clique আছে
একজন লিখলেন: “বাজারঘরের ডেলিভারি-স্লট সমস্যা X-কে SAT-এ polynomial সময়ে encode করেছি, অর্থাৎ X ≤p SAT. তাই X NP-hard.” এই যুক্তির সঠিক মূল্যায়ন কোনটি?
- সঠিক, কারণ SAT NP-complete
- ভুল, কারণ এটি আসলে দেখায় X ∈ P
- ভুল দিক: এতে শুধু X ∈ NP জানা যায়, NP-hardness নয়
- সঠিক, যদি reduction-টি Turing reduction হয়
একটি প্রস্তাবিত “3SAT ≤p X” reduction n চলকের সূত্রের জন্য প্রতিটি সম্ভাব্য সত্য/মিথ্যা মানের জন্য X-এর instance-এ একটি করে অংশ লেখে। এই reduction সম্পর্কে কোনটি সঠিক?
- “⇔” ঠিক থাকলে এটি বৈধ polynomial reduction
- এটি বৈধ নয়, কারণ output-এর আকার 2n-এর মতো বাড়ে
- X ∈ NP হলে আকার কোনো সমস্যা নয়
- এটি P = NP প্রমাণ করে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- A ≤p B মানে polynomial-time computable f, যাতে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B; |f(w)|-ও polynomial.
- দিকের নিয়ম: B ∈ P (বা NP) হলে A ∈ P (বা NP); A NP-hard হলে B NP-hard. জানা-কঠিন সমস্যা সবসময় বাঁয়ে; ≤p transitive.
- NP-complete = NP-তে আছে + NP-hard. এর একটি P-তে হলে P = NP; P বনাম NP খোলা।
- S independent ⇔ S Ḡ-তে clique ⇔ V ∖ S vertex cover: তিন সমস্যা পরস্পরে ≤p.
- 3SAT ≤p CLIQUE: clause-প্রতি তিন node, ত্রয়ীর ভেতরে আর বিরোধী literal-এ edge নেই, k = clause সংখ্যা; প্রমাণে “⇔”-এর দুই দিক।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৫২ · Reduction দিয়ে undecidability — mapping reductionফিরে দেখুনMapping reduction, দিকের নিয়ম আর তার computability-র সংস্করণ।
- পর্ব ০৫ · সমস্যাকে language হিসেবে দেখা — encoding আর decision problemপটভূমিEncoding আর input-এর দৈর্ঘ্য, যার ওপর “polynomial” নির্ভর করে।
- পর্ব ৫৮ · NP — verifier আর nondeterministic polynomial timeফিরে দেখুনCertificate, verifier আর P ⊆ NP: এই পর্বের প্রতিটি “X ∈ NP” ধাপের ভিত্তি।
- পর্ব ৪৬ · Nondeterministic Turing machine আর deterministic simulationপটভূমি“অনুমান করুন, তারপর যাচাই করুন”: NP-এর যন্ত্র-ভিত্তিক মূল।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৬০ Cook–Levin theorem.
- DSA · পর্ব ৬৪ — P বনাম NPপাশের ট্র্যাকএকই পরিবার algorithm আর কোডের দৃষ্টিতে, 3-SAT থেকে independent set.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৭ — SAT, SMT আর verificationপাশের ট্র্যাকCNF, SAT solver আর বাস্তবে satisfiability-র ব্যবহার।