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

NP-complete সমস্যার পরিবার — 3SAT, clique, vertex cover, Hamiltonian, subset sum

A Family of NP-Complete Problems — Gadget Reductions from 3SAT to Vertex Cover, Subset Sum, Hamiltonian Path, TSP and 3-Colouring

Taught in Bangla, this lesson grows the family tree of NP-complete problems from 3SAT. It gives full proofs of 3SAT ≤p VERTEX-COVER and 3SAT ≤p SUBSET-SUM, the diamond gadget for HAMPATH with the chain to UHAMPATH and TSP, and an outline of the 3-COLOR gadget. It contrasts easy look-alikes such as 2SAT and explains strong versus weak NP-completeness. In-page Python (Pyodide) runs the reductions and a 2SAT solver, and a real desktop run with pycosat (PicoSAT) and networkx solves encoded instances.

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

  • NP-completeness-এর পরিবারগাছ, আর একটি নতুন সমস্যাকে NP-complete প্রমাণ করার চার ধাপের ছক
  • 3SAT ≤p VERTEX-COVER আর 3SAT ≤p SUBSET-SUM-এর পূর্ণ প্রমাণ, ছোট সূত্রে ধাপে ধাপে
  • HAMPATH-এর diamond gadget, UHAMPATH আর TSP পর্যন্ত শিকল, আর 3-COLOR-এর gadget (প্রমাণের রূপরেখা)
  • ছদ্মবেশে NP-complete সমস্যা চেনা, আর 2SAT, 2-COLOR, matching-এর মতো পাশের সহজ সমস্যা থেকে আলাদা করা
  • Strong বনাম weak NP-completeness, আর সত্যিকারের SAT solver দিয়ে reduction যাচাই

১ · এক থেকে অনেক — NP-complete সমস্যার পরিবারগাছ

বাজারঘরের operations দলের টেবিলে চারটি প্রশ্ন জমেছে। এক, একটি ভ্যান কি প্রতিটি জেলায় ঠিক একবার গিয়ে শেষ জেলায় থামতে পারে? দুই, একটি ট্রাকে ঠিক t কেজি পার্সেল ভরা যায় কি? তিন, পরস্পর-বিরোধী অর্ডারগুলোকে তিনটি delivery slot-এ বসানো যায় কি, যাতে বিরোধী দুটি অর্ডার একই slot না পায়? চার, শহরের রাস্তার মোড়গুলোর মধ্যে k-টিতে পাহারাদার বসিয়ে কি প্রতিটি রাস্তা নজরে রাখা যায়? প্রতিটি প্রশ্নের জন্য আলাদা দল বছরের পর বছর দ্রুত algorithm খুঁজতে পারে। কিন্তু এই পর্বের মূল কথা: চারটি প্রশ্নই একই পরিবারের সদস্য। একটির জন্য polynomial algorithm পেলে চারটিরই, আসলে NP-এর সবগুলোরই, polynomial algorithm পাওয়া যেত।

একটি তালার কথা ভাবুন, যার চাবি কেউ বানাতে পারেনি। এখন কেউ দেখাল: “যেকোনো নতুন তালা X-এর ভেতরে আমি পুরোনো তালাটিকে লুকিয়ে বসাতে পারি; X খুলতে পারলে পুরোনোটিও খুলে যাবে।” তাহলে X-এর চাবি বানানো অন্তত পুরোনো তালার চাবি বানানোর মতোই কঠিন। reduction ঠিক এই কাজ করে: পুরোনো কঠিন সমস্যাকে নতুন সমস্যার ভেতরে লুকিয়ে বসায়। লুকানোর জন্য যে ছোট ছোট যন্ত্রাংশ বানানো হয়, তাদের নাম gadget.

পর্ব ৫৯-এ (Polynomial-time reduction আর NP-completeness) polynomial-time reduction A ≤p B-এর সংজ্ঞা আর দিকের নিয়ম এসেছে: f polynomial সময়ে গণনাযোগ্য, আর প্রতিটি w-এর জন্য w ∈ A ⇔ f(w) ∈ B. B ∈ P হলে A ∈ P; A NP-hard হলে B-ও NP-hard. পর্ব ৬০-এ (Cook–Levin theorem) প্রমাণ হয়েছে যে SAT NP-complete, আর SAT ≤p 3SAT. এই পর্বে আমরা সেখান থেকে শুরু করে পরিবারটি বড় করব। পুরো কাজের পেছনে একটি ছোট উপপাদ্য।

উপপাদ্য ১.১ (নতুন NP-complete সমস্যা)

যদি A NP-complete হয়, B ∈ NP হয়, আর A ≤p B হয়, তাহলে B NP-complete.

প্রমাণ:

  1. ধরুন L ∈ NP যেকোনো language. A NP-complete বলে L ≤p A, একটি polynomial-time f দিয়ে। — NP-hard-এর সংজ্ঞা
  2. A ≤p B একটি polynomial-time g দিয়ে। g ∘ f (আগে f, তারপর g) polynomial সময়ে চলে: |f(w)| ≤ p(|w|), আর g-এর সময় q(p(|w|)), যা polynomial-এর polynomial, তাই polynomial. — polynomial-এর composition
  3. w ∈ L ⇔ f(w) ∈ A ⇔ g(f(w)) ∈ B. তাই L ≤p B. — দুটি ⇔ জোড়া
  4. L যেকোনো ছিল, তাই B NP-hard; সঙ্গে B ∈ NP, তাই B NP-complete. ∎

এ থেকে NP-completeness প্রমাণের চার ধাপের ছক আসে, যা এই পর্বের প্রতিটি অংশে মানা হবে: (ক) B ∈ NP দেখানো (certificate আর verifier, পর্ব ৫৮ NP — verifier); (খ) একটি পরিচিত NP-complete A বাছাই, সাধারণত 3SAT; (গ) f বানানো আর তার সময় polynomial দেখানো; (ঘ) দুই দিকের প্রমাণ, w ∈ A ⇒ f(w) ∈ B আর f(w) ∈ B ⇒ w ∈ A. দিকটি মনে রাখুন: পরিচিত কঠিন সমস্যা থেকে নতুন সমস্যায়, উল্টো নয়।

NP-complete সমস্যার পরিবারগাছ

প্রতিটি তীর একটি polynomial-time reduction, কঠিনতা তীরের দিকে বয়ে যায়। বন্ধনীতে লেখা আছে কোথায় প্রমাণ।

Family tree of NP-complete problems rooted at SAT SAT · পর্ব ৬০ 3SAT · পর্ব ৬০ CLIQUE, IS, VC · ৫৯ VERTEX-COVER · অংশ ২ SUBSET-SUM · অংশ ৩ 3-COLOR · অংশ ৫ HAMPATH · অংশ ৪ UHAMPATH · অংশ ৪ TSP · অংশ ৪
ছবি ৬১.১ — হলুদ মূল: SAT আর 3SAT. পর্ব ৫৯-এ 3SAT থেকে CLIQUE আর CLIQUE, INDEPENDENT-SET (IS), VERTEX-COVER (VC)-এর পারস্পরিক রূপান্তর এসেছে; এই পর্বে VERTEX-COVER-এ সরাসরি একটি দ্বিতীয় পথ, আর বাকি শাখাগুলো।

সারণিতে বাজারঘরের চারটি প্রশ্ন আর তাদের আনুষ্ঠানিক নাম। সবগুলোই decision problem, সঙ্গে একটি সীমা k বা t; সবচেয়ে ছোট রুট বা সবচেয়ে কম slot খোঁজার optimisation রূপ নয়।

বাজারঘরের প্রশ্নLanguageCertificate
প্রতিটি জেলায় একবার, s থেকে tHAMPATH = {⟨G, s, t⟩ : directed G-এ s থেকে t Hamiltonian path আছে}জেলার ক্রম
মোট দূরত্ব ≤ k এমন ঘুরে-আসা রুটTSP = {⟨G, w, k⟩ : ওজন w-সহ complete graph-এ খরচ ≤ k-এর একটি Hamiltonian cycle আছে}শহরের চক্রাকার ক্রম
ঠিক t কেজি পার্সেলSUBSET-SUM = {⟨S, t⟩ : S-এর কোনো উপ-collection-এর যোগফল t}প্রতিটি সংখ্যার একটি bit
তিনটি slot, বিরোধী অর্ডার আলাদা slot-এ3-COLOR = {⟨G⟩ : G-এর একটি সঠিক ৩-রঙ colouring আছে}প্রতিটি vertex-এর রঙ
k-টি মোড়ে পাহারাদার, প্রতিটি রাস্তা নজরেVERTEX-COVER = {⟨G, k⟩ : G-এ k আকারের vertex cover আছে}k-টি vertex

প্রতিটি language NP-তে, কারণ ডান কলামের certificate দৈর্ঘ্যে input-এর polynomial আর polynomial সময়ে মেলানো যায় (পর্ব ৫৮-এর ছক)। তাই প্রতিটি সমস্যার জন্য ছকের (ক) ধাপ সহজ; এই পর্বের আসল কাজ (গ) আর (ঘ)। এই পর্বে 3SAT-এর সূত্র φ-তে l-টি চলক x1, …, xl আর m-টি clause, প্রতিটিতে ঠিক তিনটি literal (একই literal দুবারও থাকতে পারে)। চলমান উদাহরণ:

φ = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3),   l = 3, m = 2.

φ-এর আটটি মান-বসানোর ছয়টি সূত্রকে সত্য করে; যেমন x = (1, 0, 0): প্রথম clause-এ x1 সত্য, দ্বিতীয়টিতে ¬x2 সত্য।

২ · 3SAT থেকে VERTEX-COVER — gadget আর পূর্ণ প্রমাণ

পর্ব ৫৯-এ VERTEX-COVER এসেছে CLIQUE হয়ে, complement graph দিয়ে। এখানে Sipser-এর বইয়ের সরাসরি reduction, যা gadget-চিন্তার সবচেয়ে পরিষ্কার উদাহরণ। মনে রাখুন, G-এর একটি vertex cover হলো এমন vertex-সেট C, যাতে প্রতিটি edge-এর অন্তত এক প্রান্ত C-তে।

গঠন ২.১ (f: 3SAT → VERTEX-COVER)

φ থেকে G আর k এভাবে বানানো হয়:

  1. চলক gadget: প্রতিটি চলক xi-এর জন্য দুটি node, নাম xi আর ¬xi, একটি edge দিয়ে যুক্ত।
  2. Clause gadget: প্রতিটি clause-এর জন্য তিনটি নতুন node, clause-এর তিনটি literal-এর নামে, পরস্পর যুক্ত (একটি ত্রিভুজ)।
  3. যোগসূত্র: প্রতিটি clause-node-কে একই নামের চলক-node-এর সঙ্গে একটি edge দিয়ে যোগ।
  4. k = l + 2m.

G-তে 2l + 3m-টি node আর l + 3m + 3m = l + 6m-টি edge, তাই f স্পষ্টতই polynomial সময়ে চলে। φ-এর জন্য ১২টি node, ১৫টি edge আর k = 7. নিচের ছবিতে সেই graph আর x = (1, 0, 0) থেকে পাওয়া একটি cover.

φ = (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3)-এর VERTEX-COVER graph

ওপরে তিনটি চলক gadget, নিচে দুটি clause ত্রিভুজ। সবুজ node-গুলো ৭টির cover.

Vertex cover graph built from a two-clause 3CNF formula x1¬x1 x2¬x2 x3¬x3 x1x2¬x3 ¬x1¬x2x3 clause ১ clause ২
ছবি ৬১.২ — প্রতিটি ধূসর node-এর প্রতিটি edge-এর অন্য প্রান্ত সবুজ। প্রতিটি ত্রিভুজে বাদ পড়া node একটি সত্য literal (বাঁয়ে x1, ডানে ¬x2), তাই তার ড্যাশ-রেখাটি ওপরের সবুজ node ঢেকে রাখে।
উপপাদ্য ২.২

φ satisfiable ⇔ G-এ k = l + 2m আকারের vertex cover আছে। তাই 3SAT ≤p VERTEX-COVER, আর VERTEX-COVER NP-complete.

প্রমাণ, দিক ⇒:

  1. একটি satisfying assignment নিন। প্রতিটি চলক gadget থেকে সত্য literal-এর node C-তে নিন: l-টি node. — গঠন
  2. প্রতিটি clause-এ অন্তত একটি literal সত্য; এমন একটি clause-node বাদ রেখে বাকি দুটি C-তে নিন: আরও 2m. মোট |C| = l + 2m. — φ সত্য
  3. চলক-edge: প্রতিটির এক প্রান্ত C-তে (ধাপ ১)। ত্রিভুজের edge: তিনটির দুটি node C-তে, তাই ত্রিভুজের প্রতিটি edge ঢাকা। — দুটি node যেকোনো ত্রিভুজ-edge ছোঁয়
  4. যোগসূত্র-edge: clause-node C-তে থাকলে ঢাকা। বাদ পড়া node একটি সত্য literal-এর, আর সেই literal-এর চলক-node ধাপ ১-এ C-তে। তাই সব edge ঢাকা। ∎

প্রমাণ, দিক ⇐:

  1. ধরুন C একটি cover, |C| = l + 2m. প্রতিটি চলক-edge ঢাকতে প্রতিটি চলক gadget থেকে অন্তত একটি node লাগে; প্রতিটি ত্রিভুজ ঢাকতে অন্তত দুটি। — একটি node ত্রিভুজের তিনটি edge-এর দুটিই ছোঁয়
  2. এই সর্বনিম্ন চাহিদা মোট l + 2m = |C|, তাই প্রতিটি চলক gadget থেকে ঠিক একটি আর প্রতিটি ত্রিভুজ থেকে ঠিক দুটি node C-তে। — গোনা
  3. Assignment: xi = 1 যদি node xi C-তে থাকে, নইলে 0. এটি সুসংজ্ঞায়িত, কারণ প্রতিটি gadget-এর ঠিক একটি node C-তে। — ধাপ ২
  4. প্রতিটি ত্রিভুজের বাদ পড়া node v-এর যোগসূত্র-edge ঢাকা থাকতে হবে; v নিজে C-তে নেই, তাই একই নামের চলক-node C-তে, অর্থাৎ সেই literal সত্য। প্রতিটি clause-এ একটি সত্য literal: φ satisfiable. ∎

লক্ষ করুন, দিক ⇐-এর মূল কৌশল একটি গোনার আঁটসাঁট সীমা: k এমনভাবে বাছা যে কোনো cover বাড়তি node দিয়ে “প্রতারণা” করতে পারে না। নিচের stepper graph-টি গড়ে, তারপর cover বসায়।

1প্রতিটি চলক: x — ¬x edge2প্রতিটি clause: ত্রিভুজ3clause-node — একই নামের চলক-node4k = l + 2m5cover: সত্য literal-এর চলক-node6প্রতি ত্রিভুজে একটি সত্য বাদ, দুটি নেওয়া
Graph আর cover
node / edge
k
cover
ঢাকা edge
  1. চলক gadget. x1–¬x1, x2–¬x2, x3–¬x3: ছয়টি node, তিনটি edge. যেকোনো cover-কে প্রতিটি জোড়া থেকে অন্তত একটি node নিতে হবে; এটিই “চলকের মান বাছাই”।
  2. Clause ১-এর ত্রিভুজ. নতুন তিনটি node x1, x2, ¬x3, পরস্পর যুক্ত। মোট ৯টি node, ৬টি edge.
  3. যোগসূত্র. প্রতিটি clause-node ওপরের একই নামের node-এর সঙ্গে যুক্ত: x1–x1, x2–x2, ¬x3–¬x3. Edge এখন ৯টি।
  4. Clause ২ আর k. ¬x1, ¬x2, x3-এর ত্রিভুজ আর তিনটি যোগসূত্র। ১২টি node, ১৫টি edge (l + 6m), k = l + 2m = 7.
  5. চলকের মান থেকে cover. x = (1, 0, 0), তাই ওপরের x1, ¬x2, ¬x3. এরা ৩টি চলক-edge আর ৩টি যোগসূত্র ঢাকে (clause ১-এর x1 আর ¬x3, clause ২-এর ¬x2): ১৫টির ৬টি।
  6. Clause ১. সত্য literal x1-এর node বাদ, x2 আর ¬x3 নেওয়া। ত্রিভুজের ৩টি edge আর x2-এর যোগসূত্র ঢাকা পড়ে: ১০টি।
  7. Clause ২. সত্য literal ¬x2-এর node বাদ, ¬x1 আর x3 নেওয়া। বাকি ৫টি edge ঢাকা: ৭টি node-এ ১৫টির ১৫টি, ঠিক k. বাদ পড়া দুটি node-এর যোগসূত্র ওপরের সবুজ node ঢাকে।

এবার Python-এ reduction, আর ছোট সব সূত্রে “⇔”-এর brute force যাচাই। দুটি চলকের ওপর তিন-literal-এর clause (একই literal দুবার চলে) মোট ২০ রকম; এক বা দুটি clause-এর সব সূত্র নেওয়া হলো।

from itertools import product, combinations, combinations_with_replacement as cwr
def to_vc(phi, l):          # Sipser: variable edges + clause triangles + links
    E = [((i,), (-i,)) for i in range(1, l + 1)]      # (i,) = node "x_i"
    for j, c in enumerate(phi):
        tri = [(j, p) for p in range(3)]              # (j, p) = clause j, slot p
        E += list(combinations(tri, 2))
        E += [((j, p), (lit,)) for p, lit in enumerate(c)]
    V = sorted({v for e in E for v in e}, key=str)
    return V, E, l + 2 * len(phi)
def sat(phi, l):
    return any(all(any((a[abs(x) - 1] == 1) == (x > 0) for x in c) for c in phi)
               for a in product((0, 1), repeat=l))
def has_vc(V, E, k):
    return any(all(a in S or b in S for a, b in E) for S in map(set, combinations(V, k)))
phi = [(1, 2, -3), (-1, -2, 3)]
V, E, k = to_vc(phi, 3)
print("phi:", phi, "-> nodes", len(V), "edges", len(E), "k =", k)
cover = {(1,), (-2,), (-3,), (0, 1), (0, 2), (1, 0), (1, 2)}   # from x = (1, 0, 0)
print("cover size", len(cover), "covers every edge:", all(a in cover or b in cover for a, b in E))
print("a cover of size k - 1 =", k - 1, "exists?", has_vc(V, E, k - 1))
clauses = list(cwr([1, -1, 2, -2], 3))     # every 3-literal clause over x1, x2
agree = total = unsat = 0
for m in (1, 2):
    for f in cwr(clauses, m):
        V, E, k = to_vc(f, 2); s = sat(f, 2)
        total += 1; unsat += not s; agree += has_vc(V, E, k) == s
print(f"{total} formulas (l = 2, m <= 2), {unsat} unsatisfiable")
print(f"phi satisfiable == graph has a k-cover: {agree}/{total}")

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

phi: [(1, 2, -3), (-1, -2, 3)] -> nodes 12 edges 15 k = 7
cover size 7 covers every edge: True
a cover of size k - 1 = 6 exists? False
230 formulas (l = 2, m <= 2), 2 unsatisfiable
phi satisfiable == graph has a k-cover: 230/230

প্রথম দুই লাইন stepper-এর শেষ ধাপ: ১২টি node, ১৫টি edge, আর ৭টির cover সব edge ঢাকে। তৃতীয় লাইন দিক ⇐-এর গোনার যুক্তি: ৬টি node-এর কোনো cover নেই, কারণ তিনটি চলক gadget আর দুটি ত্রিভুজের ন্যূনতম চাহিদাই ৭। শেষ দুই লাইনে ২৩০টি সূত্রের প্রতিটিতে “φ satisfiable” আর “G-এ k-cover আছে” একই উত্তর দেয়। এর মধ্যে মাত্র ২টি unsatisfiable, যেমন (x1 ∨ x1 ∨ x1) ∧ (¬x1 ∨ ¬x1 ∨ ¬x1); কিন্তু দুই দিক পরীক্ষার জন্য দুটিই জরুরি। এটি প্রমাণ নয়, শুধু ছোট ক্ষেত্রে ভুল ধরার জাল; প্রমাণ ওপরে।

৩ · 3SAT থেকে SUBSET-SUM — অঙ্কের সারণি

VERTEX-COVER-এ gadget ছিল node আর edge. SUBSET-SUM-এ আছে শুধু কিছু সংখ্যা আর একটি লক্ষ্য t; তাই gadget হবে সংখ্যার অঙ্ক। মূল কৌশল: সংখ্যাগুলো দশমিকে লেখা হবে, আর প্রতিটি অঙ্ক-কলাম একটি চলক বা একটি clause-এর “হিসাবের খাতা”। কোনো কলামে যোগফল কখনো ৯ ছাড়াবে না, তাই হাতে-রাখা (carry) হবে না, আর প্রতিটি কলাম স্বাধীনভাবে আচরণ করবে।

গঠন ৩.১ (f: 3SAT → SUBSET-SUM, Sipser)

প্রতিটি সংখ্যায় l + m-টি দশমিক অঙ্ক: প্রথম l-টি কলাম চলকের, শেষ m-টি clause-এর।

  1. প্রতিটি চলক xi-এর জন্য দুটি সংখ্যা yi আর zi: দুটিরই কলাম xi-এ 1. yi-এর clause-কলাম cj-এ 1, যদি xi cj-এ থাকে; zi-এর cj-এ 1, যদি ¬xi cj-এ থাকে। বাকি সব অঙ্ক 0.
  2. প্রতিটি clause cj-এর জন্য দুটি “ফাঁক-ভরানো” সংখ্যা gj আর hj: শুধু কলাম cj-এ 1.
  3. লক্ষ্য t: চলক-কলামে 1, clause-কলামে 3; অর্থাৎ t = 1…1 3…3.

φ-এর সারণি নিচে। সারি y1: x1 প্রথম clause-এ আছে, তাই c1 কলামে 1; z1: ¬x1 দ্বিতীয় clause-এ, তাই c2-তে 1.

সংখ্যাx1x2x3c1c2
y110010
z110001
y201010
z201001
y300101
z300110
g1, h100010
g2, h200001
t11133
উপপাদ্য ৩.২

φ satisfiable ⇔ সারণির কোনো উপ-collection-এর যোগফল t. তাই 3SAT ≤p SUBSET-SUM, আর SUBSET-SUM NP-complete.

প্রমাণ:

  1. Carry নেই। প্রতিটি কলামে বড়জোর ৫টি 1 থাকে (চলক-কলামে ২টি, clause-কলামে তিনটি literal-এর বড়জোর ৩টি আর g, h-এর ২টি)। তাই যেকোনো উপ-collection-এর যোগে প্রতিটি কলামের অঙ্ক ≤ 5, আর যোগফল কলামে কলামে আলাদা পড়া যায়। — 5 < 10
  2. ⇒. Satisfying assignment থেকে xi = 1 হলে yi, নইলে zi নিন। প্রতিটি চলক-কলামে ঠিক 1. Clause-কলাম cj-এ যোগফল = cj-এর সত্য literal-এর সংখ্যা, যা 1, 2 বা 3; ঘাটতি 3 − (সেই সংখ্যা) ≤ 2 পূরণ করতে gj, hj থেকে প্রয়োজনমতো নিন। যোগফল t. — ধাপ ১
  3. ⇐, চলক. ধরুন একটি উপ-collection-এর যোগফল t. চলক-কলাম xi-এ 1 পেতে yi আর zi-এর ঠিক একটি নেওয়া হয়েছে। xi = 1 যদি yi নেওয়া হয়, নইলে 0. — ধাপ ১, carry নেই
  4. ⇐, clause. cj কলামে 3 লাগে, আর gj, hj বড়জোর 2 দেয়। তাই অন্তত একটি নেওয়া y বা z সংখ্যার cj-এ 1 আছে, অর্থাৎ এমন একটি literal, যা ধাপ ৩-এর assignment-এ সত্য আর cj-এ আছে। প্রতিটি clause সত্য। ∎
  5. সময়। 2l + 2m-টি সংখ্যা, প্রতিটি l + m অঙ্কের: সারণির আকার O((l + m)2), যা φ-এর দৈর্ঘ্যের polynomial.
1কলাম: x1 x2 x3 │ c1 c22প্রতি চলক: y (x) আর z (¬x)3প্রতি clause: g আর h4t = 111 │ 335সত্য literal-এর সারি নেওয়া6ঘাটতি g, h দিয়ে পূরণ
সারণি আর যোগফল
নতুন সারি
যোগফল
c1 c2 অঙ্ক
  1. কলাম. তিনটি চলক-কলাম আর দুটি clause-কলাম, তাই প্রতিটি সংখ্যা ৫ অঙ্কের। প্রতিটি কলামে বড়জোর ৫টি 1, তাই carry অসম্ভব।
  2. x1-এর সারি. y1 = 10010 (x1 আছে c1-এ), z1 = 10001 (¬x1 আছে c2-তে)।
  3. x2, x3. y2 = 01010, z2 = 01001; y3 = 00101 (x3 আছে c2-তে), z3 = 00110 (¬x3 আছে c1-এ)।
  4. ফাঁক-ভরানো সংখ্যা আর t. g1 = h1 = 00010, g2 = h2 = 00001. লক্ষ্য t = 11133: প্রতিটি চলক একবার, প্রতিটি clause-কলামে ঠিক ৩।
  5. Assignment থেকে বাছাই. x = (1, 0, 0): y1, z2, z3. যোগফল 10010 + 01001 + 00110 = 11121. c1-এ 2 (x1 আর ¬x3 সত্য), c2-তে 1 (শুধু ¬x2).
  6. ঘাটতি পূরণ. c1-এ এক কম, তাই g1; c2-তে দুই কম, তাই g2 আর h2. যোগফল 11133 = t. Satisfying assignment থেকে একটি “হ্যাঁ” উপ-collection পাওয়া গেল।
  7. উল্টো দিক. যেকোনো উপ-collection যোগফল t দিলে প্রতিটি চলক-কলামে y বা z-এর ঠিক একটি, আর প্রতিটি clause-কলামে g, h-এর ২-এর বেশি পূরণ হয় না, তাই অন্তত একটি সত্য literal লাগে। এখান থেকে assignment পড়ে নেওয়া যায়।
from itertools import product, combinations_with_replacement as cwr
def to_subset_sum(phi, l):           # Sipser's digit table, base 10
    m, rows = len(phi), []
    def num(digits): return int("".join(map(str, digits)))
    for i in range(1, l + 1):
        for name, lit in ((f"y{i}", i), (f"z{i}", -i)):
            d = [0] * (l + m); d[i - 1] = 1
            for j, c in enumerate(phi): d[l + j] = int(lit in c)
            rows.append((name, num(d)))
    for j in range(m):
        d = [0] * (l + m); d[l + j] = 1
        rows += [(f"g{j + 1}", num(d)), (f"h{j + 1}", num(d))]
    return rows, int("1" * l + "3" * m)
def sat_count(phi, l):
    return sum(all(any((a[abs(x) - 1] == 1) == (x > 0) for x in c) for c in phi)
               for a in product((0, 1), repeat=l))
def reachable(nums, t):              # all subset sums up to t
    sums = {0}
    for x in nums: sums |= {s + x for s in sums if s + x <= t}
    return t in sums
phi = [(1, 2, -3), (-1, -2, 3)]
rows, t = to_subset_sum(phi, 3)
print("  ".join(f"{n}={v:05d}" for n, v in rows[:6]))
print("  ".join(f"{n}={v:05d}" for n, v in rows[6:]), "  t =", t)
hits = [b for b in product((0, 1), repeat=len(rows))
        if sum(v for (_, v), x in zip(rows, b) if x) == t]
print("subsets hitting t:", len(hits), "| satisfying assignments:", sat_count(phi, 3))
print("one subset:", [n for (n, _), x in zip(rows, hits[-1]) if x])
clauses = list(cwr([1, -1, 2, -2], 3))
agree = total = unsat = 0
for m in (1, 2, 3):
    for f in cwr(clauses, m):
        rows, t = to_subset_sum(f, 2); s = sat_count(f, 2) > 0
        total += 1; unsat += not s; agree += reachable([v for _, v in rows], t) == s
print(f"{total} formulas (l = 2, m <= 3), {unsat} unsatisfiable; agree: {agree}/{total}")

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

y1=10010  z1=10001  y2=01010  z2=01001  y3=00101  z3=00110
g1=00010  h1=00010  g2=00001  h2=00001   t = 11133
subsets hitting t: 12 | satisfying assignments: 6
one subset: ['y1', 'y2', 'y3', 'g1', 'g2', 'h2']
1770 formulas (l = 2, m <= 3), 66 unsatisfiable; agree: 1770/1770

প্রথম দুই লাইন সারণিটি হুবহু। তৃতীয় লাইনে একটি সূক্ষ্ম তথ্য: ৬টি satisfying assignment, কিন্তু ১২টি উপ-collection. কারণ যে clause-এ দুটি literal সত্য, সেখানে ঘাটতি এক, আর তা g বা h যেকোনোটি দিয়ে পূরণ করা যায়: দুই রকম। তাই এই reduction “হ্যাঁ/না” রক্ষা করে, কিন্তু সমাধানের সংখ্যা রক্ষা করে না; অর্থাৎ এটি parsimonious reduction নয়। চতুর্থ লাইনের উপ-collection x = (1, 1, 1)-এর: c1-এ দুটি সত্য (g1 লাগে), c2-তে একটি (g2, h2 লাগে)। শেষ লাইনে ১,৭৭০টি সূত্রে (৬৬টি unsatisfiable) দুই দিক মিলেছে।

৪ · 3SAT থেকে HAMPATH, তারপর UHAMPATH আর TSP

বাজারঘরের ভ্যানের রুট প্রশ্নটি, অর্থাৎ HAMPATH, সবচেয়ে বিখ্যাত reduction-গুলোর একটি; Sipser-এর উপপাদ্য ৭.৪৬. এখানে প্রমাণের রূপরেখা দেওয়া হলো; পূর্ণ বিবরণ Sipser-এর বইয়ের সেই অংশে। ধারণাটি: প্রতিটি চলকের জন্য একটি “diamond” রাস্তা, যা দুইভাবে পার হওয়া যায়, বাঁ থেকে ডানে (চলক সত্য) বা ডান থেকে বাঁয়ে (মিথ্যা)। প্রতিটি clause একটি আলাদা node, যেখানে শুধু “সঠিক দিকে” চলা রুট ঘুরে আসতে পারে।

গঠন ৪.১ (f: 3SAT → HAMPATH, diamond gadget)
  1. প্রতিটি চলক xi-এর একটি diamond: একটি ওপরের node, একটি নিচের node, আর মাঝে 3m + 1-টি node-এর একটি আড়াআড়ি সারি। সারির পাশাপাশি node-দুটি দুই দিকেই edge দিয়ে যুক্ত; ওপরের node থেকে সারির দুই প্রান্তে, আর দুই প্রান্ত থেকে নিচের node-এ edge.
  2. সারিতে প্রতিটি clause cj-এর জন্য একটি জোড়া (aj, bj), জোড়াগুলোর মাঝে আর দুই প্রান্তে একটি করে “বিভাজক” node: m জোড়া আর m + 1 বিভাজক, মোট 3m + 1.
  3. Diamond-গুলো শিকলে: xi-এর নিচের node-ই xi+1-এর ওপরের node. s = প্রথম diamond-এর ওপর, t = শেষ diamond-এর নিচ।
  4. প্রতিটি clause cj-এর একটি node. xi cj-এ থাকলে xi-এর diamond-এ aj → cj → bj (বাঁ থেকে ডানে); ¬xi থাকলে bj → cj → aj (ডান থেকে বাঁয়ে)।

x1-এর diamond, যখন x1 ∈ c1 আর ¬x1 ∈ c2 (m = 2)

সারির ৭টি node: বিভাজক, a1, b1, বিভাজক, a2, b2, বিভাজক। সারির ধূসর রেখা দুই দিকেই চলা যায়।

Diamond gadget of one variable with detours to two clause nodes s c1 c2 a1b1 a2b2 পরের diamond
ছবি ৬১.৩ — সবুজ ঘুরপথ (a1 → c1 → b1) শুধু বাঁ থেকে ডানে চলা রুট নিতে পারে: x1 সত্য হলে c1 সন্তুষ্ট। লাল ঘুরপথ (b2 → c2 → a2) শুধু ডান থেকে বাঁয়ে: x1 মিথ্যা হলে c2 (যেখানে ¬x1) সন্তুষ্ট।
1ওপর → সারির এক প্রান্ত2সারি ধরে অন্য প্রান্ত পর্যন্ত3সঠিক দিকে হলে clause-এ ঘুরপথ4প্রান্ত → নিচ (পরের diamond)
রুট
মোড
এ পর্যন্ত
clause node
  1. গঠন. ওপরের node s থেকে সারির দুই প্রান্তে যাওয়া যায়, আর দুই প্রান্ত থেকে নিচে। সারির মাঝের node-গুলোতে ঢোকার আর কোনো পথ নেই, ঘুরপথ ছাড়া।
  2. সত্য মোড. রুট বাঁ প্রান্তের বিভাজক দিয়ে ঢুকে ডানে এগোয়: s → বিভাজক → a1.
  3. সবুজ ঘুরপথ. a1 → c1 → b1. দিক মিলেছে (বাঁ থেকে ডানে), তাই c1 এখানেই নেওয়া যায়। অন্য diamond-ও c1 নিতে পারত; প্রতিটি clause node ঠিক একবার নিতে হবে, যেকোনো একটি সত্য literal-এর diamond থেকে।
  4. লাল ঘুরপথ বাদ. b2 → c2 → a2 ডান থেকে বাঁয়ে; বাঁ থেকে ডানে চলা রুট a2-তে আগে, b2-তে পরে আসে, তাই ঘুরপথ নিলে a2-তে ফেরা যেত না। রুট সোজা b2, বিভাজক হয়ে নিচে নামে।
  5. মিথ্যা মোড. s → ডান প্রান্ত → b2 → c2 → a2 → বিভাজক → b1 → a1 → বিভাজক → নিচ। এবার c2 নেওয়া হলো (সেখানে ¬x1), c1 নয়।
  6. পর্যবেক্ষণ. দুই মোডেই সারির সাতটি node ঠিক একবার; শুধু clause node বদলায়। একটি diamond একটি চলকের মান “বেছে নেয়”।
  7. সারা graph. s থেকে l-টি diamond পার হয়ে t; প্রতিটি clause node কোনো সত্য literal-এর diamond থেকে ঘুরে নেওয়া হয়। উল্টো দিকের সূক্ষ্ম অংশ: একটি রুট cj-এ ঢুকে অন্য diamond-এ বেরোলে, বিভাজকের কারণে কোনো সারি-node আটকে যায়; তাই সব Hamiltonian path “স্বাভাবিক”, আর তা থেকে assignment পড়া যায়।

প্রমাণের রূপরেখা: ⇒ দিক stepper-এর ধাপ ২–৭: সত্য চলকের diamond বাঁ থেকে ডানে, মিথ্যারটি ডান থেকে বাঁয়ে, আর প্রতিটি clause node-কে তার একটি সত্য literal-এর diamond থেকে ঘুরিয়ে আনা। ⇐ দিকের মূল দাবি: যেকোনো s–t Hamiltonian path-এ, যদি এটি aj থেকে cj-এ যায়, তাহলে পরের node অবশ্যই একই diamond-এর bj. নইলে bj-এর প্রতিবেশী শুধু aj (আগেই দেখা), পাশের বিভাজক আর হয়তো cj (আগেই দেখা)। তখন bj একটিমাত্র অদেখা প্রতিবেশী নিয়ে রুটের মাঝখানে বসতে পারে না, আর সে রুটের শেষও নয় (শেষ t). এই দাবি থেকে প্রতিটি diamond একটি দিকে পার হয়, আর দিকটিই assignment; প্রতিটি cj দেখা হয়েছে বলে প্রতিটি clause সত্য। গঠনে node সংখ্যা l(3m + 1) + (l + 1) + m, তাই f polynomial. Scratch-এ দুই চলক আর বড়জোর দুই clause-এর সব ২৩০টি সূত্রে আমাদের Python গঠনটি backtracking খোঁজের সঙ্গে মিলিয়ে দেখা হয়েছে।

UHAMPATH. বাস্তব রাস্তা দুই-মুখী। HAMPATH ≤p UHAMPATH: s আর t ছাড়া প্রতিটি node u-কে তিনটি node uin — umid — uout-এর একটি ছোট শিকলে বদলানো; s থাকে শুধু sout, t শুধু tin; প্রতিটি directed edge (u, v) হয় undirected edge {uout, vin}. umid-এর প্রতিবেশী মাত্র দুটি, তাই যেকোনো Hamiltonian path in → mid → out ক্রমে যেতে বাধ্য, আর সেটিই পুরোনো দিক ফিরিয়ে আনে। Scratch-এ ৩০০টি random ছোট directed graph-এ দুই দিকের উত্তর মিলেছে।

TSP. TSP-এর decision রূপ: ওজনসহ complete graph আর বাজেট k; খরচ ≤ k এমন একটি Hamiltonian cycle আছে কি? UHAMPATH থেকে: একটি নতুন node w যোগ করে তাকে s আর t-এর সঙ্গে যুক্ত করুন; তাহলে s–t Hamiltonian path আছে ⇔ নতুন graph-এ Hamiltonian cycle আছে। তারপর N-টি node-এর complete graph বানান, যেখানে আসল edge-এর ওজন 1, বাকি জোড়ার ওজন 2, আর k = N. খরচ N-এর cycle মানে সব edge ওজন 1-এর, অর্থাৎ আসল graph-এর Hamiltonian cycle. বাজারঘরের “সব জেলা ঘুরে ফেরা, মোট দূরত্ব ≤ k” প্রশ্ন তাই NP-complete.

৫ · 3SAT থেকে 3-COLOR — রঙের palette আর OR-gadget

বাজারঘরের delivery slot প্রশ্নটি graph colouring: প্রতিটি অর্ডার একটি vertex, দুটি বিরোধী অর্ডারের মধ্যে একটি edge, আর তিনটি slot তিনটি রঙ। 3-COLOR ∈ NP সহজ (certificate প্রতিটি vertex-এর রঙ)। কঠিনতার reduction-টির রূপরেখা দেওয়া হলো; এর gadget-গুলো সুন্দরভাবে “যুক্তির বর্তনী” বানায়। ইতিহাসে 3-COLOR-এর NP-completeness সাধারণত Stockmeyer-এর ১৯৭৩ সালের কাজের সঙ্গে উল্লেখ করা হয়, যেখানে planar graph-এর জন্যও এটি দেখানো হয়েছিল বলে পরিচিত।

গঠন ৫.১ (f: 3SAT → 3-COLOR, রূপরেখা)
  1. Palette: তিনটি node T, F, B, পরস্পর যুক্ত (একটি ত্রিভুজ)। এদের রঙের নামই “সত্য”, “মিথ্যা” আর “ভিত্তি”।
  2. চলক: প্রতিটি xi-এর জন্য node xi আর ¬xi, পরস্পর যুক্ত, আর দুটিই B-এর সঙ্গে যুক্ত। তাই একটির রঙ T, অন্যটির F.
  3. Clause (a ∨ b ∨ c): ছয়টি নতুন node u1…u6-এর একটি OR-gadget: a–u1, b–u2, u1–u2, u1–u3, u2–u3, u3–u4, c–u5, u4–u5, u4–u6, u5–u6; আর u6 যুক্ত F আর B-এর সঙ্গে, তাই u6-এর রঙ T হতে বাধ্য।

প্রথম তিনটি node (u1, u2, u3) a আর b-এর একটি “OR” বানায়: a আর b দুটিই F হলে u3-কে F হতে হয়; অন্তত একটি T হলে u3-কে T রঙ দেওয়া যায়। পরের তিনটি একই কাজ করে u3 আর c নিয়ে, আর ফল u6. Gadget-এর মূল ধর্ম: a, b, c-এর রঙ T বা F দেওয়া থাকলে gadget-টি u6 = T নিয়ে সঠিকভাবে রাঙানো যায় ⇔ a, b, c-এর অন্তত একটি T. এই ধর্মটি scratch-এ আটটি রঙ-সমন্বয়ের প্রতিটিতে u1…u6-এর সব 36 রঙ চেষ্টা করে যাচাই করা হয়েছে, আর পুরো reduction দুই চলকের ২৩০টি সূত্রে।

প্রমাণের রূপরেখা: ⇒: satisfying assignment থেকে সত্য literal-এর node-এ T-এর রঙ, মিথ্যাগুলোতে F-এর রঙ; প্রতিটি clause-এ অন্তত একটি সত্য literal, তাই gadget-এর ধর্মে প্রতিটি OR-gadget রাঙানো যায়। ⇐: যেকোনো ৩-রঙ colouring-এ palette-এর তিনটি রঙ আলাদা; xi-এর রঙ T-এর রঙের সমান হলে xi = 1. প্রতিটি u6 T-রঙের, তাই gadget-এর ধর্মে প্রতিটি clause-এর একটি literal T: φ সত্য। Graph-এ 3 + 2l + 6m-টি node আর 3 + 3l + 12m-টি edge: polynomial. ∎

বাজারঘরের অনুবাদ: তিনটি slot যথেষ্ট কি না, এই প্রশ্নের একটি দ্রুত সাধারণ algorithm থাকলে 3SAT-এরও থাকত, আর তাহলে P = NP. বিপরীতে, দুটি slot যথেষ্ট কি না (2-COLOR) BFS দিয়ে রৈখিক সময়ে বলা যায় (অংশ ৭)। আর চারটি বা তার বেশি slot-ও NP-complete: 3-COLOR-এর graph-এ সবার সঙ্গে যুক্ত একটি নতুন vertex যোগ করলেই 3-COLOR ≤p 4-COLOR (অনুশীলন ৪)।

সব শাখা দেখা হলো। প্রতিটি reduction যে সত্যিই polynomial, তা দেখতে নিচের JavaScript ছোট “গাছ-নেভিগেটর” l চলক আর m clause-এর একটি সূত্র থেকে প্রতিটি gadget কত বড় instance বানায়, তা হিসাব করে, আর SAT থেকে যেকোনো সমস্যা পর্যন্ত পথ ছাপে। প্রথম লাইনের তালিকায় নিজের (l, m) বসিয়ে আবার চালাতে পারেন।

// Family tree of reductions: parent, and the size of the instance each
// gadget builds from a 3-CNF formula with l variables and m clauses.
const sizes = [[3, 2], [50, 200]];
const tree = {
  "3SAT":         ["SAT",          (l, m) => "split long clauses (lesson 60)"],
  "CLIQUE":       ["3SAT",         (l, m) => `${3 * m} nodes, k = ${m}`],
  "VERTEX-COVER": ["3SAT",         (l, m) => `${2 * l + 3 * m} nodes, ${l + 6 * m} edges, k = ${l + 2 * m}`],
  "INDEP-SET":    ["VERTEX-COVER", (l, m) => `same graph, k = ${l + m}`],
  "SUBSET-SUM":   ["3SAT",         (l, m) => `${2 * l + 2 * m} numbers of ${l + m} digits`],
  "HAMPATH":      ["3SAT",         (l, m) => `${hp(l, m)[0]} nodes, ${hp(l, m)[1]} edges`],
  "UHAMPATH":     ["HAMPATH",      (l, m) => `${3 * hp(l, m)[0] - 4} nodes, ${hp(l, m)[1] + 2 * (hp(l, m)[0] - 2)} edges`],
  "TSP":          ["UHAMPATH",     (l, m) => `${3 * hp(l, m)[0] - 3} cities, budget ${3 * hp(l, m)[0] - 3}`],
  "3-COLOR":      ["3SAT",         (l, m) => `${3 + 2 * l + 6 * m} nodes, ${3 + 3 * l + 12 * m} edges`],
};
function hp(l, m) {   // diamonds: rows of 3m+1, l+1 joints, m clause nodes
  return [l * (3 * m + 1) + (l + 1) + m, l * (6 * m + 4) + 6 * m];
}
function chain(p) { const c = [p]; while (tree[p]) { p = tree[p][0]; c.unshift(p); } return c; }
for (const [l, m] of sizes) {
  console.log(`--- 3-CNF formula with l = ${l} variables, m = ${m} clauses ---`);
  for (const p of Object.keys(tree)) console.log(p.padEnd(13), tree[p][1](l, m));
}
console.log("path to TSP:", chain("TSP").join(" -> "));
console.log("path to INDEP-SET:", chain("INDEP-SET").join(" -> "));

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

--- 3-CNF formula with l = 3 variables, m = 2 clauses ---
3SAT          split long clauses (lesson 60)
CLIQUE        6 nodes, k = 2
VERTEX-COVER  12 nodes, 15 edges, k = 7
INDEP-SET     same graph, k = 5
SUBSET-SUM    10 numbers of 5 digits
HAMPATH       27 nodes, 60 edges
UHAMPATH      77 nodes, 110 edges
TSP           78 cities, budget 78
3-COLOR       21 nodes, 36 edges
--- 3-CNF formula with l = 50 variables, m = 200 clauses ---
3SAT          split long clauses (lesson 60)
CLIQUE        600 nodes, k = 200
VERTEX-COVER  700 nodes, 1250 edges, k = 450
INDEP-SET     same graph, k = 250
SUBSET-SUM    500 numbers of 250 digits
HAMPATH       30301 nodes, 61400 edges
UHAMPATH      90899 nodes, 121998 edges
TSP           90900 cities, budget 90900
3-COLOR       1303 nodes, 2553 edges
path to TSP: SAT -> 3SAT -> HAMPATH -> UHAMPATH -> TSP
path to INDEP-SET: SAT -> 3SAT -> VERTEX-COVER -> INDEP-SET

φ-এর সংখ্যাগুলো আগের অংশের সঙ্গে মেলে: VERTEX-COVER-এ ১২ node, ১৫ edge, k = 7; SUBSET-SUM-এ ৫ অঙ্কের ১০টি সংখ্যা; 3-COLOR-এ ২১ node আর ৩৬ edge. HAMPATH আর UHAMPATH-এর সংখ্যা scratch-এ graph বানিয়ে গোনা সংখ্যার সঙ্গে মিলেছে (যখন কোনো clause-এ একই literal দুবার নেই)। সব আকার l আর m-এর বড়জোর দ্বিঘাত, তাই polynomial; শিকল জুড়লেও polynomial থাকে (উপপাদ্য ১.১-এর composition). দুটি জিনিস লক্ষ করুন। SUBSET-SUM-এর ২৫০ অঙ্কের সংখ্যা লেখা সহজ, কিন্তু তাদের মান প্রায় 10250: অংশ ৮-এর মূল কথা এটিই। আর INDEP-SET-এর k = (2l + 3m) − (l + 2m) = l + m, কারণ vertex cover-এর বাকি node-গুলো একটি independent set (পর্ব ৫৯)।

৬ · সত্যিকারের SAT solver-এ বাজারঘরের instance

Reduction শুধু প্রমাণের হাতিয়ার নয়, বাস্তব কৌশলও: একটি কঠিন সমস্যাকে CNF সূত্রে লিখে একটি SAT solver-কে দেওয়া। এখানে দিকটি উল্টো, 3-COLOR ≤p SAT আর SUBSET-SUM ≤p SAT; কারণ এখন লক্ষ্য কঠিনতা প্রমাণ নয়, সমাধান খোঁজা। আমরা pycosat 0.6.6 (MIT licence; PicoSAT solver-এর Python binding, Windows-এ uv source থেকে build করেছে) আর networkx 3.7 (BSD-3-Clause) ব্যবহার করেছি, Python 3.12.13-এ একটি uv প্রকল্পে। দুটির কোনোটিতে usage-reporting বা network কোড নেই (installed source-এ খুঁজে দেখা)। সূত্রগুলো DIMACS CNF ফাইলেও লেখা হয়েছে, যা প্রায় সব solver পড়ে।

3-COLOR-এর encoding: প্রতিটি vertex v আর রঙ c-এর জন্য একটি চলক “v-এর slot c”; প্রতিটি v-এর জন্য “অন্তত একটি slot” clause, প্রতিটি রঙ-জোড়ার জন্য “একসঙ্গে দুটি নয়” clause, আর প্রতিটি বিরোধ (u, v) ও প্রতিটি c-এর জন্য ¬(u, c) ∨ ¬(v, c). SUBSET-SUM-এর encoding: প্রতিটি পার্সেলের একটি “নেওয়া হলো” bit, আর binary full adder-এর একটি শিকল, যার Tseitin-ধাঁচের clause যোগফলের bit-গুলোকে t-এর bit-এর সমান হতে বাধ্য করে; এতে সূত্রের আকার সংখ্যার bit-দৈর্ঘ্যের polynomial থাকে।

import itertools, pycosat, networkx as nx
def color_cnf(G):                      # CNF class: var(), add(*lits), dimacs()
    F = CNF(); x = {(v, c): F.var() for v in G for c in range(3)}
    for v in G:
        F.add(*(x[v, c] for c in range(3)))            # at least one slot
        for c, d in itertools.combinations(range(3), 2):
            F.add(-x[v, c], -x[v, d])                   # at most one slot
    for u, v in G.edges:
        for c in range(3): F.add(-x[u, c], -x[v, c])    # clash: different slots
    return F, x
conflicts = [("A","B"),("A","C"),("B","C"),("B","D"),("C","E"),("D","E"),("D","F"),
             ("E","G"),("F","G"),("F","H"),("G","I"),("H","I"),("H","J"),("I","J"),("A","J")]
G = nx.Graph(conflicts)
head, col = solve_color(G, "slots")    # writes slots.cnf, runs pycosat.solve
print("networkx check:", all(col[u] != col[v] for u, v in G.edges))
n_sol = sum(1 for _ in pycosat.itersolve(color_cnf(G)[0].cl))
# ... 3SAT -> 3-COLOR gadget graph (section 5), then solve_color on it
# ... subset_cnf(w, t): ripple-carry full adders over the chosen bits

সত্যিকারের run (ডেস্কটপ, pycosat 0.6.6, networkx 3.7, Python 3.12.13):

~/bazarghar-toc$ uv run python solve_bg.py
python 3.12.13 | pycosat 0.6.6 | networkx 3.7
bazarghar slots: 10 orders, 15 conflicts; 2 slots enough? False
p cnf 30 85 -> A3B2C1D3E2F2G3H3I2J1
networkx check: every conflict in different slots: True
all 3-colourings: 108 = 6 x 18 different slot plans
add A-D, C-D (A,B,C,D all clash): p cnf 30 91 -> UNSAT
phi -> 3-COLOR graph: 21 nodes, 36 edges; p cnf 63 192
  colouring found; x_i = 1 iff colour(x_i) == colour(T): {1: 1, 2: 1, 3: 1} satisfies phi: True
all 8 clauses on x1,x2,x3 (unsatisfiable) -> p cnf 171 552 -> UNSAT
parcels (kg): [7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
  truck t=100: p cnf 171 1129 -> [17, 23, 29, 31] sum=100 | DP agrees: True
  truck t=101: p cnf 171 1129 -> [29, 31, 41] sum=101 | DP agrees: True
  truck t=227: p cnf 171 1129 -> UNSAT | DP agrees: True
phi -> SUBSET-SUM (t=11133): p cnf 311 2116 -> chosen ['z1', 'z2', 'z3', 'g1', 'h1', 'g2']
  x_i = 1 iff y_i chosen: {1: 0, 2: 0, 3: 0} satisfies phi: True

Slot. ১০টি অর্ডারের বিরোধ-graph-এ একটি বিজোড় চক্র আছে (A, B, C একটি ত্রিভুজ), তাই networkx বলছে দুটি slot যথেষ্ট নয়। ৩০টি চলক আর ৮৫টি clause-এর সূত্রে solver একটি পরিকল্পনা দিয়েছে: A slot 3, B slot 2, C slot 1, …; networkx প্রতিটি বিরোধ আলাদাভাবে মিলিয়েছে। সব সমাধান গুনে ১০৮টি, অর্থাৎ slot-এর নাম অদলবদলের 3! = ৬ রকম বাদ দিলে ১৮টি আলাদা পরিকল্পনা। A–D আর C–D বিরোধ যোগ করলে A, B, C, D চারটিই পরস্পর-বিরোধী, আর solver সঠিকভাবে UNSAT বলেছে।

Reduction-এর শিকল. অংশ ৫-এর gadget graph-টি solver-কে দিয়ে রঙ থেকে assignment পড়া হয়েছে; ফল x = (1, 1, 1) φ-কে সত্য করে। আটটি clause-এর unsatisfiable সূত্রের gadget graph ৩-রঙযোগ্য নয়: reduction-এর ⇐ দিক বাস্তবে। পার্সেলের ক্ষেত্রে ১০০ আর ১০১ কেজির সমাধান মিলেছে, আর ২২৭ অসম্ভব (মোট ওজন ২২৮, আর 1 কেজির পার্সেল নেই); প্রতিবার একটি স্বাধীন DP একই উত্তর দিয়েছে। শেষে পুরো যাত্রা: φ → অংশ ৩-এর অঙ্ক-সারণি → adder CNF → solver → উপ-collection {z1, z2, z3, g1, h1, g2} → assignment (0, 0, 0), যা φ-এর ছয়টি সমাধানের একটি। Solver দ্রুত উত্তর দিয়েছে বলে এই সমস্যাগুলো “সহজ” প্রমাণ হয় না; এগুলো ছোট instance, আর solver-এর সবচেয়ে খারাপ ক্ষেত্র সূচকীয়। বাস্তবে বড় instance-এ solver কেন প্রায়ই ভালো চলে, তা পর্ব ৭৩-এ (বাস্তবে NP-hard সমস্যা — SAT solver, ILP আর heuristic).

৭ · ছদ্মবেশে NP-complete, আর পাশের সহজ সমস্যা

বাস্তবে কেউ বলে না “এটি 3-COLOR”. বলে “পরীক্ষার রুটিন বানাতে হবে, যাতে একই ছাত্রের দুটি পরীক্ষা একই দিনে না পড়ে”, বা “সবচেয়ে কম ভ্যানে সব পার্সেল ভরতে হবে”। ছদ্মবেশ চেনার উপায়: সমস্যার “হ্যাঁ” উত্তরের প্রমাণ কেমন, আর তার গঠন কোন পরিচিত সমস্যার মতো, তা দেখা। কিন্তু উল্টো ভুলও সমান বিপজ্জনক: দেখতে প্রায় একই রকম অনেক সমস্যা আসলে P-তে। নিচের সারণিতে জোড়ায় জোড়ায়।

P-তে (দ্রুত algorithm জানা)NP-complete (decision রূপ)পার্থক্য কোথায়
প্রতিটি রাস্তা একবার: Euler pathপ্রতিটি জেলা একবার: HAMPATHEuler-এ শুধু degree গোনা লাগে; Hamilton-এর কোনো স্থানীয় শর্ত জানা নেই
দুটি slot: 2-COLOR (BFS)তিনটি slot: 3-COLORদুই রঙে একটি vertex-এর রঙ পাশেরটিকে বাধ্য করে; তিন রঙে পছন্দ থাকে
প্রতি clause-এ দুটি literal: 2SATতিনটি literal: 3SAT(a ∨ b) মানে “¬a হলে b”: একটি implication-এর শিকল
রাইডার আর অর্ডার জোড়া: bipartite matchingতিন দলের জোড়া (3-dimensional matching)দুই দলে augmenting path কাজ করে; তিনে জানা নেই
দুই জেলার সবচেয়ে ছোট পথ (Dijkstra)সব জেলা ঘুরে ছোট রুট: TSPছোট পথে উপ-পথও সবচেয়ে ছোট; TSP-তে “কোনগুলো আগে ঘোরা হলো” মনে রাখতে হয়
ভ্যানের ওজন-সীমায় যত খুশি পার্সেল, ভাঙা চলে (fractional)সবচেয়ে কম ভ্যান: bin packingভাঙা চললে greedy-ই সেরা; অবিভাজ্য হলে সমন্বয়ের বিস্ফোরণ

2SAT কেন সহজ, তা সবচেয়ে শিক্ষণীয়। প্রতিটি clause (a ∨ b) দুটি “যদি-তাহলে” দেয়: ¬a → b আর ¬b → a. সব clause থেকে এমন edge নিয়ে একটি directed implication graph হয়, যার node 2l-টি literal. মূল উপপাদ্য (Aspvall, Plass আর Tarjan ১৯৭৯-এ রৈখিক সময়ের algorithm-সহ): φ unsatisfiable ⇔ কোনো চলক x-এর জন্য x আর ¬x একই strongly connected component-এ (অর্থাৎ x থেকে ¬x আর ¬x থেকে x, দুই দিকেই পথ আছে)। এক দিকের যুক্তি সহজ: x ⇒ ⋯ ⇒ ¬x আর ¬x ⇒ ⋯ ⇒ x থাকলে x সত্য বা মিথ্যা, কোনোটিই টেকে না। অন্য দিক: এমন জোড়া না থাকলে SCC-গুলোর topological ক্রমে পরে আসা literal-কে সত্য ধরলে একটি সঠিক assignment পাওয়া যায় (প্রমাণ বাদ; Aspvall–Plass–Tarjan বা যেকোনো algorithm বইয়ে আছে)। 3SAT-এ (a ∨ b ∨ c) থেকে “¬a হলে b বা c”, একটি পছন্দ; শিকল আর তৈরি হয় না।

1node: x1 ¬x1 x2 ¬x2 x3 ¬x32(a ∨ b): ¬a → b, ¬b → a3x আর ¬x একই SCC-তে?4হ্যাঁ হলে UNSAT
Implication graph
clause
নতুন edge
মোট edge
x2 ⇝ ¬x2 ?
  1. Node. তিনটি চলক, তাই ছয়টি literal-node. এখনো কোনো edge নেই।
  2. (x1 ∨ x2). “x1 মিথ্যা হলে x2 সত্য” আর “x2 মিথ্যা হলে x1 সত্য”: দুটি edge.
  3. (¬x1 ∨ x2). x1 → x2 আর ¬x2 → ¬x1. এখন ¬x2 থেকে x1 আর ¬x1 দুটিতেই যাওয়া যায়, আর দুটি থেকেই x2-তে: x2 মিথ্যা ধরলে বিপদ, তাই x2 সত্য হতে বাধ্য।
  4. (¬x2 ∨ x3). x2 → x3, ¬x3 → ¬x2. x2 থেকে ¬x2-তে কোনো পথ নেই (x3-এর বাইরের কোনো edge নেই), তাই কোনো চলক আর তার উল্টো একই SCC-তে নেই: satisfiable. Assignment x2 = 1, x3 = 1, x1 যেকোনো; brute force-ও ঠিক এই দুটি দেয়।
  5. (¬x2 ∨ ¬x3). x2 → ¬x3 আর x3 → ¬x2. এবার x2 → x3 → ¬x2 একটি পথ। আর উল্টো দিকে ¬x2 → x1 → x2 আগেই ছিল।
  6. রায়. x2 আর ¬x2 একই SCC-তে: সূত্রটি unsatisfiable. প্রথম দুই clause x2-কে সত্য হতে বাধ্য করে, আর শেষ দুটি তখন x3 আর ¬x3 দুটিই চায়। Graph-এর আকার O(l + m), আর SCC বের করা রৈখিক সময়ের কাজ।
import random; from itertools import product
random.seed(61)
def two_sat(phi, l):                  # implication graph + SCC (Kosaraju)
    nodes = [v for i in range(1, l + 1) for v in (i, -i)]
    G = {v: [] for v in nodes}; R = {v: [] for v in nodes}
    for a, b in phi:                  # (a or b) gives -a -> b and -b -> a
        for u, v in ((-a, b), (-b, a)): G[u].append(v); R[v].append(u)
    def dfs(g, v, seen, out):         # iterative DFS, appends v when finished
        stack = [(v, iter(g[v]))]; seen.add(v)
        while stack:
            u, it = stack[-1]
            w = next((w for w in it if w not in seen), None)
            if w is None: stack.pop(); out.append(u)
            else: seen.add(w); stack.append((w, iter(g[w])))
    order, seen = [], set()
    for v in (v for v in nodes if v not in seen): dfs(G, v, seen, order)
    comp, seen = {}, set()
    for c, v in enumerate(reversed(order)):   # components in topological order
        if v not in seen:
            members = []; dfs(R, v, seen, members)
            for u in members: comp[u] = c
    if any(comp[i] == comp[-i] for i in range(1, l + 1)): return None
    return {i: int(comp[i] > comp[-i]) for i in range(1, l + 1)}
def holds(a, phi): return all(any((a[abs(x)] == 1) == (x > 0) for x in c) for c in phi)
f = [(1, 2), (-1, 2), (-2, 3)]
print("3 clauses:", two_sat(f, 3), "| with (-x2 or -x3):", two_sat(f + [(-2, -3)], 3))
ok = 0
for _ in range(2000):
    l = random.randint(2, 7)
    phi = [tuple(random.choice((1, -1)) * random.randint(1, l) for _ in range(2))
           for _ in range(random.randint(1, 3 * l))]
    a = two_sat(phi, l)
    brute = any(holds(dict(enumerate(b, 1)), phi) for b in product((0, 1), repeat=l))
    ok += (a is not None) == brute and (a is None or holds(a, phi))
print("random 2-CNF formulas where SCC answer == brute force:", ok, "/ 2000")

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

3 clauses: {1: 1, 2: 1, 3: 1} | with (-x2 or -x3): None
random 2-CNF formulas where SCC answer == brute force: 2000 / 2000

প্রথম লাইন stepper-এর ধাপ ৪ আর ৬: তিন clause-এ SCC পদ্ধতি একটি assignment দিয়েছে (x1 এখানে 1 এসেছে, যা brute force-এর দুটি সমাধানের একটি), আর চতুর্থ clause যোগ করলে None, অর্থাৎ unsatisfiable. দ্বিতীয় লাইনে ২,০০০টি random 2-CNF সূত্রের প্রতিটিতে SCC-এর হ্যাঁ/না brute force-এর সঙ্গে মেলে, আর “হ্যাঁ” হলে দেওয়া assignment সত্যিই সূত্রটিকে সত্য করে। SCC পদ্ধতি graph-এর node আর edge একবার করে দেখে, তাই সময় O(l + m); brute force 2l-টি assignment দেখে। কিন্তু মনে রাখুন: 3SAT-এর জন্য এমন কোনো কৌশল জানা নেই, আর থাকলে P = NP হতো।

NP-complete যা বোঝায় না। (১) প্রতিটি instance কঠিন নয়: ছোট instance, বা গঠনে বিশেষ instance প্রায়ই সহজ। গাছ-আকৃতির graph-এ 3-COLOR তুচ্ছ (গাছ দুই রঙেই রাঙানো যায়), আর bipartite graph-এ VERTEX-COVER-এর সবচেয়ে ছোট মাপ maximum matching-এর সমান (Kőnig-এর উপপাদ্য), তাই polynomial. (২) “এখন পর্যন্ত কেউ দ্রুত algorithm পায়নি” আর “দ্রুত algorithm নেই” এক কথা নয়; দ্বিতীয়টি P ≠ NP-এর ওপর নির্ভর করে, যা প্রমাণিত নয়, যদিও বেশিরভাগ গবেষক তা-ই মনে করেন। (৩) বাস্তব সমাধান অসম্ভব নয়: SAT solver, approximation আর heuristic প্রতিদিন বড় instance সামলায় (পর্ব ৭১ আর ৭৩)। algorithm-এর দিক থেকে এই আলোচনা আছে DSA কোর্সের পর্ব ৬৫-এ।

৮ · Strong আর weak NP-completeness — সংখ্যার আকার কেন জরুরি

SUBSET-SUM-এর একটি পরিচিত dynamic programming আছে: “প্রথম i-টি সংখ্যা দিয়ে s যোগফল বানানো যায় কি?” একটি n × (t + 1) সারণিতে, O(n · t) সময়ে। বাজারঘরের ট্রাকে t = 100 কেজি হলে এটি ঝটপট চলে। তাহলে কি P = NP প্রমাণ হলো? না। Input-এ t লেখা থাকে binary-তে, প্রায় log2 t bit-এ; t-এর মান তার দৈর্ঘ্যের সূচকীয়। তাই O(n · t) হলো pseudo-polynomial: সংখ্যার মানের polynomial, কিন্তু input-দৈর্ঘ্যের নয়। অংশ ৩-এর reduction ঠিক এই ফাঁক দিয়ে কাজ করে: তার সংখ্যাগুলোর অঙ্ক l + m-টি, অর্থাৎ মান প্রায় 10l+m, আর সেখানে DP-এর সারণি সূচকীয় বড়।

সংজ্ঞা ৮.১ (Strong আর weak NP-completeness)

একটি সংখ্যাযুক্ত সমস্যা strongly NP-complete, যদি সব সংখ্যার মান input-দৈর্ঘ্যের একটি polynomial দিয়ে সীমিত, এমন instance-এর সীমিত রূপটিও NP-complete থাকে (সমতুল্যভাবে: সংখ্যা unary-তে লিখলেও)। NP-complete কিন্তু pseudo-polynomial algorithm আছে, এমন সমস্যাকে বলা হয় weakly NP-complete.

ধারণাটি Garey আর Johnson-এর ১৯৭৮ সালের একটি প্রবন্ধে আনুষ্ঠানিক রূপ পায় বলে পরিচিত। তাঁদের একটি সহজ কিন্তু শক্তিশালী পর্যবেক্ষণ: strongly NP-complete সমস্যার কোনো pseudo-polynomial algorithm থাকলে P = NP হতো, কারণ ছোট-সংখ্যার কঠিন রূপটিতে pseudo-polynomial মানেই polynomial. উদাহরণ:

  • Weak: SUBSET-SUM, 0/1 knapsack, দুই ভাগে সমান ভাগ (PARTITION). সংখ্যা ছোট হলে DP যথেষ্ট।
  • Strong: VERTEX-COVER, HAMPATH, 3-COLOR, CLIQUE (এদের input-এ কোনো বড় সংখ্যাই নেই), TSP (অংশ ৪-এর reduction-এ শুধু ওজন 1 আর 2), আর bin packing ও 3-PARTITION, যাদের সংখ্যা থাকলেও কঠিনতা টিকে থাকে বলে পরিচিত।

বাজারঘরের জন্য ব্যবহারিক শিক্ষা: পার্সেলের ওজন কেজিতে পূর্ণসংখ্যা আর ট্রাকের সীমা কয়েকশো কেজি হলে “ঠিক t কেজি” প্রশ্ন DP-তে মুহূর্তে মেটে; কিন্তু “সবচেয়ে কম ভ্যানে সব পার্সেল” (bin packing) প্রশ্নে ছোট সংখ্যাও বাঁচায় না।

আরও গভীরে: Schaefer ১৯৭৮ সালে একটি “dichotomy theorem” প্রমাণ করেন বলে পরিচিত: Boolean constraint-এর একটি বড় শ্রেণির প্রতিটি সমস্যা হয় P-তে (2SAT, Horn-SAT, XOR-SAT-এর মতো কয়েকটি ধরন), নয়তো NP-complete; মাঝামাঝি কিছু নেই। অথচ Ladner-এর উপপাদ্য (১৯৭৫) বলে, P ≠ NP হলে সাধারণভাবে NP-তে এমন সমস্যা আছে, যা P-তেও নয়, NP-complete-ও নয় (পর্ব ৬৩)। আরেকটি সূক্ষ্মতা: reduction হ্যাঁ/না রক্ষা করে, কিন্তু approximation রক্ষা করে না; VERTEX-COVER-এর একটি সহজ 2-গুণ approximation আছে, অথচ একই graph-এ INDEPENDENT-SET-কে ভালোভাবে approximate করা কঠিন বলে প্রমাণিত (P ≠ NP অনুমানে)। এর কারণ PCP তত্ত্বে, পর্ব ৭১-এ।

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

  • B NP-complete প্রমাণের ছক কী? B ∈ NP, আর পরিচিত NP-complete A থেকে A ≤p B, f polynomial, দুই দিকের ⇔.
  • 3SAT ≤p VERTEX-COVER-এ k কত? l + 2m: প্রতিটি চলক-edge-এ একটি, প্রতিটি ত্রিভুজে দুটি।
  • SUBSET-SUM-এর DP থাকলে P = NP নয় কেন? O(n · t) pseudo-polynomial; t-এর মান তার bit-দৈর্ঘ্যের সূচকীয়।
  • 2SAT কেন P-তে? Implication graph-এ x আর ¬x একই SCC-তে কি না, রৈখিক সময়ে।
  • Euler path আর Hamiltonian path-এর পার্থক্য? প্রথমটি প্রতিটি edge একবার (P), দ্বিতীয়টি প্রতিটি vertex একবার (NP-complete).

৯ · AI-এর যুগে NP-completeness প্রমাণ

AI assistant-কে “X NP-complete প্রমাণ করো” বললে প্রায়ই সুন্দর দেখতে একটি উত্তর আসে, যার কাঠামো ঠিক কিন্তু ভেতরে বড় ফাঁক। সবচেয়ে সাধারণ ভুল দিকের: X থেকে 3SAT-এ reduction লিখে “X NP-hard” দাবি করা, যা আসলে শুধু X ∈ NP-এর দিকে একটি ইঙ্গিত দেয়। অন্য ভুলগুলো: দুই দিকের একটি বাদ, gadget-এর সংখ্যা (যেমন k) ভুল, reduction-এর সময় না গোনা, বা সংখ্যাকে unary ধরে pseudo-polynomial algorithm-কে polynomial বলা। এই পর্বের Python ব্লকগুলোর মতো একটি ছোট brute-force “⇔ পরীক্ষক” লিখলে এসব ভুলের বেশিরভাগ মিনিটে ধরা পড়ে।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
নতুন সমস্যা X থেকে 3SAT-এ reduction দিয়ে “X NP-hard”তীর পরিচিত কঠিন সমস্যা থেকে X-এ হতে হবে: 3SAT ≤p X
শুধু ⇒ দিক প্রমাণ (“সমাধান থাকলে নতুন instance-এ সমাধান আছে”)⇐ দিক আলাদা খুঁজুন; ছোট unsatisfiable সূত্রে reduction চালিয়ে দেখুন উত্তর “না” আসে কি না
Gadget-এর সংখ্যা ভুল, যেমন VERTEX-COVER-এ k = l + mসব ছোট সূত্রে brute force-এ ⇔ পরীক্ষা করুন; একটি ভুল k সঙ্গে সঙ্গে অমিল দেখায়
SUBSET-SUM-এর DP দেখে “P-তে”সংখ্যা binary-তে; O(n · t) pseudo-polynomial
“NP-complete, তাই এই instance সমাধান করা যাবে না”Solver বা DP দিয়ে ছোট বা বিশেষ instance চালিয়ে দেখুন; NP-completeness সবচেয়ে খারাপ ক্ষেত্রের কথা
বানানো ইতিহাস বা রেফারেন্স (“Karp ১৯৭২ সালে 3-COLOR প্রমাণ করেন”)Karp-এর ২১টি সমস্যার তালিকা, Garey–Johnson বা Sipser-এ নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: ছকের চারটি ধাপ আলাদা আলাদা চাওয়া, gadget-এর আকার স্পষ্ট সংখ্যায় চাওয়া, আর একটি brute-force ⇔ পরীক্ষক চেয়ে সেটি নিজে চালানো।

আমি গণনার তত্ত্ব শিখছি। INDEPENDENT-SET = {⟨G, k⟩ : G-এ k আকারের independent set আছে} NP-complete, তা 3SAT থেকে সরাসরি reduction দিয়ে প্রমাণ করো। ১. প্রথমে INDEPENDENT-SET ∈ NP দেখাও: certificate আর verifier, সময়সহ। ২. Reduction-এর দিক স্পষ্ট লেখো: 3SAT ≤p INDEPENDENT-SET, উল্টো নয়। l চলক আর m clause-এর সূত্র থেকে কতটি node, কতটি edge আর কোন k, সূত্রে লেখো। ৩. দুই দিক আলাদা প্রমাণ করো: φ satisfiable ⇒ k-আকারের independent set আছে, আর তার উল্টো। ৪. শুধু standard library দিয়ে Python-এ reduction লেখো, আর দুই চলকের সব ছোট সূত্রে (অন্তত একটি unsatisfiable-সহ) brute force দিয়ে ⇔ পরীক্ষা করো। ৫. P বনাম NP নিয়ে কিছু বললে স্পষ্ট লেখো কোনটি প্রমাণিত আর কোনটি খোলা; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১Cook-এর একটি সমস্যা থেকে কয়েক বছরে কয়েকশো NP-complete সমস্যা কীভাবে এল? Karp-এর ১৯৭২ সালের প্রবন্ধ কেন এত প্রভাবশালী?

Stephen Cook ১৯৭১ সালে দেখান যে SAT-এর মতো একটি সমস্যা NP-এর প্রতিটি সমস্যাকে ধারণ করে। ফলটি গভীর, কিন্তু প্রথমে মনে হতে পারত এটি যুক্তিবিদ্যার একটি বিশেষ সমস্যার খবর মাত্র। পরের বছর Richard Karp “Reducibility Among Combinatorial Problems” প্রবন্ধে দেখান যে এই ঘটনা মোটেই বিশেষ নয়: ২১টি পরিচিত combinatorial সমস্যা, যেমন CLIQUE, vertex cover (তাঁর ভাষায় node cover), directed আর undirected Hamiltonian circuit, chromatic number, knapsack ধাঁচের একটি সংখ্যা-সমস্যা, exact cover, সবই একই শ্রেণির, আর একটি থেকে আরেকটিতে polynomial-time reduction আছে। এগুলোর অনেকগুলোর জন্য গবেষকেরা বছরের পর বছর দ্রুত algorithm খুঁজছিলেন, আলাদা আলাদা।

Karp-এর প্রবন্ধের প্রভাবের কারণ তিনটি। প্রথম, তিনি দেখালেন কৌশলটি পুনরাবৃত্তিযোগ্য: উপপাদ্য ১.১-এর মতো একটি সরল যুক্তিতে প্রতিটি নতুন reduction পরিবারে একটি নতুন সদস্য যোগ করে। দ্বিতীয়, তাঁর সমস্যাগুলো operations research, scheduling আর graph theory-র বাস্তব সমস্যা, তাই বার্তাটি প্রকৌশলীদের কাছেও পৌঁছাল: “এর দ্রুত সাধারণ algorithm খোঁজা হয়তো অর্থহীন; approximation বা বিশেষ ক্ষেত্র খুঁজুন।” তৃতীয়, polynomial-time many-one reduction, যাকে আজ প্রায়ই Karp reduction বলা হয়, এক ধরনের মানক ভাষা হয়ে গেল।

এরপর বিস্ফোরণ। Garey আর Johnson-এর ১৯৭৯ সালের বই “Computers and Intractability” কয়েকশো NP-complete সমস্যার একটি তালিকা দেয়, আর বইটি আজও গবেষকদের হাতের কাছে থাকে বলে পরিচিত। Leonid Levin সোভিয়েত ইউনিয়নে স্বাধীনভাবে একই ধরনের ফল পান, প্রকাশ ১৯৭৩, যেখানে কয়েকটি “universal search problem” ছিল। ফলে একটি মজার পরিস্থিতি তৈরি হয়েছে: হাজারো সমস্যা একটি সুতোয় বাঁধা, আর কোনো একটির polynomial algorithm বা কোনো একটির polynomial-এর বাইরে থাকার প্রমাণ বাকি সবার ভাগ্য ঠিক করে দেবে।

মূল উপলব্ধি: Cook একটি সমস্যার কঠিনতা দেখান; Karp দেখান reduction-এর শিকলে সেই কঠিনতা বাস্তব সমস্যার বিশাল পরিবারে ছড়িয়ে দেওয়া যায়, আর সেখান থেকেই NP-completeness প্রকৌশলের দৈনন্দিন ভাষা হয়।

প্র ০২2SAT সহজ, 3SAT কঠিন; 2-COLOR সহজ, 3-COLOR কঠিন। “দুই থেকে তিন” কেন এত বড় লাফ? কঠিন আর সহজের সীমানা কি সবসময় এমন তীক্ষ্ণ?

দুই ক্ষেত্রেই সহজ সংস্করণে একটি সিদ্ধান্ত পরের সিদ্ধান্তকে বাধ্য করে। 2-COLOR-এ একটি vertex লাল হলে তার প্রতিবেশী নীল হতে বাধ্য, তাদের প্রতিবেশী লাল; BFS এই বাধ্যবাধকতা ছড়িয়ে দেয়, আর বিজোড় চক্র পেলে “না” বলে। 2SAT-এ (a ∨ b) মানে ¬a হলে b বাধ্য; implication graph এই শিকল লেখে। কোনো ধাপেই অনুমান বা পিছিয়ে আসা (backtracking) দরকার হয় না। তিন রঙ বা তিন literal হলে একটি সিদ্ধান্ত পরেরটিকে শুধু সংকুচিত করে, বাধ্য করে না: প্রতিবেশীর জন্য দুটি রঙ খোলা থাকে, বা “b বা c” দুই পথ। পছন্দগুলো জমে জমে সূচকীয় সংখ্যক সমন্বয় তৈরি করে, আর gadget দিয়ে যুক্তির বর্তনী বানানো সম্ভব হয়, যেমন অংশ ৫-এর OR-gadget.

এই অন্তর্দৃষ্টির একটি গাণিতিক রূপ আছে। Thomas Schaefer ১৯৭৮ সালে Boolean constraint satisfaction-এর জন্য একটি dichotomy theorem প্রমাণ করেন বলে পরিচিত: constraint-এর ধরন ছয়টি বিশেষ শ্রেণির (যেমন 2-CNF, Horn, XOR-এর রৈখিক সমীকরণ) একটিতে পড়লে সমস্যা P-তে, নইলে NP-complete.

তবে সাধারণভাবে সীমানা এমন তীক্ষ্ণ হবে, তার নিশ্চয়তা নেই। Ladner-এর উপপাদ্য বলে, P ≠ NP হলে NP-তে “মাঝামাঝি” সমস্যাও আছে। Graph isomorphism আর integer factoring-এর decision রূপকে প্রায়ই এমন প্রার্থী ধরা হয়, যদিও কোনোটির অবস্থান প্রমাণিত নয়। আর planar graph-এ ৪-রঙ সমস্যা তুচ্ছ (Appel আর Haken-এর ১৯৭৬ সালের চার-রঙ উপপাদ্যে উত্তর সবসময় “হ্যাঁ”), অথচ planar 3-COLOR NP-complete: “কত রঙ” আর “কোন graph” দুটিই সীমানা সরায়।

মূল উপলব্ধি: দুই-বিকল্পের সমস্যায় সিদ্ধান্ত শিকলের মতো বাধ্যবাধকতা ছড়ায়, আর তা polynomial; তিন বিকল্পে পছন্দ জমে gadget বানানো যায়। অনেক শ্রেণিতে এই সীমানা প্রমাণিতভাবে তীক্ষ্ণ, কিন্তু NP-এর পুরোটায় তা নয়।

প্র ০৩Knapsack আর SUBSET-SUM-এর জন্য খুব ভালো approximation আছে, bin packing-এর জন্য তেমন নেই। strong আর weak NP-completeness এর সঙ্গে কীভাবে যুক্ত?

0/1 knapsack-এর optimisation রূপ ভাবুন: ওজনের সীমার মধ্যে মোট মান সবচেয়ে বেশি। মান যদি ছোট পূর্ণসংখ্যা হয়, DP “এই মোট মান পেতে সবচেয়ে কম ওজন কত” সারণি ভরে pseudo-polynomial সময়ে নিখুঁত উত্তর দেয়। Ibarra আর Kim ১৯৭৫ সালে এর একটি চতুর ব্যবহার দেখান বলে পরিচিত: মানগুলোকে একটি উপযুক্ত গুণক দিয়ে ভাগ করে নিচে গোল করলে সংখ্যা ছোট হয়, DP দ্রুত চলে, আর হারানো মান খুব কম। ফল একটি fully polynomial-time approximation scheme (FPTAS): যেকোনো ε > 0-এর জন্য (1 − ε) গুণ ভালো উত্তর, সময় n আর 1/ε দুটিরই polynomial. এই কৌশল সম্ভব হয়েছে ঠিক কারণ সমস্যাটি weakly NP-complete: কঠিনতা লুকিয়ে আছে বড় সংখ্যায়, আর গোল করলে সেই কঠিনতা কমে।

Garey আর Johnson-এর পর্যবেক্ষণের একটি পরিণতি: একটি strongly NP-hard optimisation সমস্যার (পূর্ণসংখ্যা মূল্যের, আর সর্বোত্তম মান input-এর polynomial দিয়ে সীমিত এমন হলে) FPTAS থাকলে P = NP হতো, কারণ যথেষ্ট ছোট ε নিলে approximation নিখুঁত উত্তরে পরিণত হয়। Bin packing এর উদাহরণ: “দুটি বাক্সে আঁটে কি?” প্রশ্নটিই PARTITION, তাই 3/2-এর চেয়ে ভালো গুণফলে সবচেয়ে কম বাক্স বের করা P ≠ NP হলে অসম্ভব বলে পরিচিত। তবু বাস্তবে First Fit Decreasing-এর মতো সরল নিয়ম প্রায় সর্বোত্তমের কাছে থাকে, আর বড় instance-এ asymptotic scheme-ও আছে।

বাজারঘরের প্রকৌশলীর জন্য প্রশ্নটি তাই কয়েক স্তরের: সংখ্যাগুলো কত বড়? নিখুঁত উত্তর লাগবে, নাকি কাছাকাছি চলবে? উত্তর অনুযায়ী DP, FPTAS, heuristic বা solver. “NP-complete” লেবেল আলোচনার শুরু, শেষ নয়। Approximation আর inapproximability-র আনুষ্ঠানিক তত্ত্ব পর্ব ৭১-এ, আর algorithm-এর দিক DSA কোর্সের পর্ব ৬৬-এ।

মূল উপলব্ধি: Weak NP-completeness-এ কঠিনতা থাকে বড় সংখ্যায়, তাই সংখ্যা ছোট করলে (DP বা গোল করে FPTAS) কাজ হয়; strong NP-completeness-এ সংখ্যা ছোট হলেও কঠিনতা থাকে, আর pseudo-polynomial algorithm বা FPTAS থাকলে P = NP হতো।

প্র ০৪NP-complete হলেও SAT solver লক্ষ লক্ষ চলকের সূত্র সমাধান করে, আর Sudoku বা Minesweeper-এর সাধারণ রূপও NP-complete; worst case আর বাস্তব instance-এর এই ফারাক কীভাবে বুঝবেন?

NP-completeness একটি worst-case বিবৃতি: কোনো polynomial algorithm সব instance ঠিক সময়ে সমাধান করতে পারে না (যদি P ≠ NP). কিন্তু বাস্তব instance এলোমেলো নয়। Chip-নকশা যাচাই, software-এর bounded model checking বা পরিকল্পনা সমস্যা থেকে আসা সূত্রে প্রচুর গঠন থাকে: স্থানীয় নির্ভরতা, পুনরাবৃত্ত অংশ, ছোট “backdoor” চলক-সেট। ১৯৯০-এর দশকের মাঝামাঝি GRASP আর ২০০১ সালে Chaff-এর মতো solver conflict-driven clause learning (CDCL), চতুর চলক-বাছাই আর দ্রুত তথ্য-কাঠামো একত্র করে বলে পরিচিত; তারপর থেকে solver-এর ক্ষমতা অনেক গুণ বেড়েছে। এগুলো ভুল থেকে শিখে নতুন clause যোগ করে, যা খোঁজের বিশাল অংশ কেটে দেয়।

অন্যদিকে random 3-CNF সূত্রে একটি পরিচিত পরীক্ষালব্ধ ঘটনা আছে: clause আর চলকের অনুপাত প্রায় ৪.২৬-এর কাছে গেলে সূত্রগুলো হঠাৎ satisfiable থেকে unsatisfiable-এ বদলায়, আর ঠিক সেই অঞ্চলে solver-এর জন্য সবচেয়ে কঠিন instance পাওয়া যায়। অনুপাত কম হলে প্রায় সব সূত্র সহজে satisfiable, বেশি হলে সহজে প্রমাণযোগ্য unsatisfiable. অর্থাৎ কঠিনতা instance-এর গঠনের ওপর নির্ভর করে।

খেলার উদাহরণগুলো উল্টো শিক্ষা দেয়। n² × n² Sudoku-র সাধারণ রূপ NP-complete বলে দেখানো হয়েছে (Yato আর Seta, ২০০৩), আর Minesweeper-এর “এই বোর্ড কি সংগতিপূর্ণ?” প্রশ্নটি Kaye ২০০০ সালে NP-complete দেখান বলে পরিচিত। তবু পত্রিকার ৯ × ৯ Sudoku সেকেন্ডে মেটে, কারণ আকার স্থির আর ছোট; NP-completeness বড় হতে থাকা পরিবারের কথা বলে। বাজারঘরের ১০টি অর্ডারের slot পরিকল্পনা এই পর্বের solver মুহূর্তে মিটিয়েছে; দশ হাজার অর্ডারে solver-ও সাধারণত চলে, কিন্তু নিশ্চয়তা নেই।

মূল উপলব্ধি: NP-completeness সবচেয়ে খারাপ ক্ষেত্রের সীমা; বাস্তব instance-এর গঠন, স্থির আকার আর CDCL solver-এর কৌশল প্রায়ই সমস্যাকে সামলানোর যোগ্য করে, কিন্তু কোনো নিশ্চয়তা দেয় না।

প্র ০৫একটি নতুন gadget কীভাবে আবিষ্কার করা হয়? আর reduction যখন সমাধানের সংখ্যাও রক্ষা করে, তখন কী নতুন জানা যায়?

Gadget-নকশার একটি প্রচলিত পদ্ধতি তিন প্রশ্নে ভাগ করা যায়। এক, লক্ষ্য সমস্যায় “একটি বাইনারি পছন্দ” কীভাবে প্রকাশ করা যায়? VERTEX-COVER-এ একটি edge-এর কোন প্রান্ত, HAMPATH-এ diamond-এর কোন দিক, 3-COLOR-এ x আর ¬x-এর কোনটি T. দুই, “এই তিনটির অন্তত একটি” কীভাবে বাধ্য করা যায়? ত্রিভুজের একটি node বাদ পড়ার সুযোগ, ঘুরপথ, OR-gadget, বা অঙ্ক-কলামে “৩ পেতে অন্তত একটি”। তিন, দুটি অংশ কীভাবে সংগতিপূর্ণ রাখা যায়, যাতে একই চলক এক জায়গায় সত্য আর আরেক জায়গায় মিথ্যা না হয়? যোগসূত্র-edge, একই diamond-এ সব clause-এর জোড়া, একই কলামে y আর z. তারপর আসে সবচেয়ে কঠিন অংশ: ⇐ দিকে “প্রতারণা” বন্ধ করা, যেমন k-এর আঁটসাঁট গোনা বা HAMPATH-এর বিভাজক node. বাস্তবে গবেষকেরা ছোট gadget-এর জন্য কম্পিউটারে সব সম্ভাবনা খুঁজেও দেখেন, যেমন এই পর্বে OR-gadget-এর ধর্ম brute force-এ যাচাই হয়েছে।

দ্বিতীয় প্রশ্নের উত্তর গোনার জটিলতায়। Leslie Valiant ১৯৭৯ সালে #P শ্রেণির সংজ্ঞা দেন: NP সমস্যার সমাধান গোনা। Reduction যদি parsimonious হয়, অর্থাৎ সমাধানের সংখ্যা হুবহু রক্ষা করে, তাহলে গোনার কঠিনতাও বয়ে যায়। অংশ ৩-এ দেখা গেছে Sipser-এর SUBSET-SUM reduction parsimonious নয়: ৬টি assignment থেকে ১২টি উপ-collection, কারণ g আর h পরস্পর বদলানো যায়। অনেক সময় gadget সামান্য বদলে, যেমন দুটি সমান slack-এর বদলে আলাদা মানের slack দিয়ে, গণনাটি নিয়ন্ত্রণে আনা যায়, যদিও সবসময় এক-এক মিল আসে না। Valiant-এর আরেকটি বিস্ময়কর ফল: bipartite graph-এ perfect matching আছে কি না polynomial সময়ে বলা যায়, অথচ তাদের সংখ্যা গোনা (matrix-এর permanent) #P-complete. তাই সহজ decision সমস্যার গোনা রূপও কঠিন হতে পারে।

মূল উপলব্ধি: Gadget-নকশা মানে পছন্দ, “অন্তত একটি” আর সংগতি প্রকাশের তিনটি কাঠামো, সঙ্গে ⇐ দিকে প্রতারণা বন্ধের আঁটসাঁট গোনা; আর reduction সমাধানের সংখ্যা রক্ষা করলে গোনার কঠিনতাও প্রমাণ হয়, যেখানে সহজ সমস্যারও কঠিন গোনা-রূপ থাকতে পারে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। sat_to_vc.py আর sat_to_subset_sum.py-তে নিজের সূত্র বসিয়ে যাচাইও করতে পারেন।

  1. নকশা (reduction তৈরি): বাজারঘরের slot প্রশ্ন একটি SAT solver-কে দিতে 3-COLOR ≤p SAT reduction নকশা করুন: চলক, clause-এর তিন ধরন আর n vertex ও e edge-এর graph-এ চলক ও clause-এর সংখ্যা। তারপর ত্রিভুজ A, B, C আর একটি অতিরিক্ত edge C–D-এর graph-এ সংখ্যাগুলো বের করুন। এই reduction দিয়ে কি 3-COLOR-এর কঠিনতা প্রমাণ হয়?

    চলক: প্রতিটি vertex v আর রঙ c ∈ {1, 2, 3}-এর জন্য pv,c (“v-এর রঙ c”): 3n-টি। Clause: (১) প্রতিটি v-এর জন্য pv,1 ∨ pv,2 ∨ pv,3: n-টি; (২) প্রতিটি v আর প্রতিটি রঙ-জোড়ার জন্য ¬pv,c ∨ ¬pv,d: 3n-টি; (৩) প্রতিটি edge (u, v) আর প্রতিটি c-এর জন্য ¬pu,c ∨ ¬pv,c: 3e-টি। মোট 4n + 3e clause. সঠিকতা: একটি colouring থেকে সত্য চলক পড়লে সব clause সত্য; উল্টোদিকে satisfying assignment-এ প্রতিটি v-এর ঠিক একটি রঙ, আর কোনো edge-এর দুই প্রান্ত একই রঙ নয়। আকার রৈখিক, তাই polynomial.

    n = 4, e = 4: চলক 12, clause 16 + 12 = 28. (বাজারঘরের ১০ অর্ডার আর ১৫ বিরোধে 30 আর 85, solver-এর DIMACS header-এর সঙ্গে মেলে।) কঠিনতার প্রশ্নে উত্তর: না। এই তীর 3-COLOR থেকে SAT-এ, তাই এটি শুধু দেখায় 3-COLOR SAT-এর চেয়ে কঠিন নয় (এবং 3-COLOR ∈ NP-এর আরেকটি প্রমাণ)। কঠিনতার জন্য লাগে 3SAT ≤p 3-COLOR, অংশ ৫-এর gadget.

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: 2SAT NP-complete. প্রমাণ: 2SAT ∈ NP (certificate assignment). এখন 2SAT ≤p 3SAT দেখাই: প্রতিটি clause (a ∨ b)-কে (a ∨ b ∨ b) লিখুন। এটি polynomial, আর φ satisfiable ⇔ নতুন সূত্র satisfiable. 3SAT NP-complete, তাই 2SAT-ও। ∎” ভুলটি কোথায়, আর সঠিক সিদ্ধান্ত কী?

    Reduction-টি নিজে সঠিক, কিন্তু দিক উল্টো। 2SAT ≤p 3SAT দেখায় যে 2SAT, 3SAT-এর চেয়ে কঠিন নয়: 3SAT-এর একটি দ্রুত algorithm থাকলে 2SAT-এরও থাকত। NP-hardness প্রমাণে তীর পরিচিত কঠিন সমস্যা থেকে নতুন সমস্যায় যেতে হয়: 3SAT ≤p 2SAT. সেটি দেখানো গেলে P = NP হতো, কারণ 2SAT ∈ P (অংশ ৭)।

    সঠিক সিদ্ধান্ত: 2SAT ∈ P, implication graph আর SCC দিয়ে রৈখিক সময়ে। তাই P ≠ NP হলে 2SAT NP-complete নয়; আর P = NP হলে (তুচ্ছ কয়েকটি language বাদে) P-এর প্রতিটি language NP-complete হতো, যা আজও অজানা।

  3. Trace (আউটপুট অনুমান): φ′ = (x1 ∨ x2 ∨ x2) ∧ (¬x1 ∨ ¬x2 ∨ ¬x2)-এর জন্য অংশ ৩-এর গঠনে SUBSET-SUM-এর সব সংখ্যা আর t লিখুন। কতগুলো উপ-collection t দেয়, আর φ′-এর কয়টি satisfying assignment? একই φ′ থেকে VERTEX-COVER-এর graph-এ কয়টি node, আর k কত?

    চার অঙ্ক (x1 x2 │ c1 c2): y1 = 1010, z1 = 1001, y2 = 0110, z2 = 0101, g1 = h1 = 0010, g2 = h2 = 0001, t = 1133. (y2-তে c1-এর অঙ্ক 1, যদিও x2 সেখানে দুবার আছে: গঠন শুধু “আছে কি না” দেখে।) Satisfying assignment দুটি: (1, 0) আর (0, 1). (1, 0)-এ y1 + z2 = 1111: দুই clause-এ একটি করে সত্য literal, তাই g1, h1, g2, h2 চারটিই লাগে: এক রকম। (0, 1)-এ z1 + y2 = 1111, একইভাবে এক রকম। মোট ২টি উপ-collection; scratch-এ সব 28 উপ-collection গুনে মিলেছে।

    VERTEX-COVER: 2l + 3m = 4 + 6 = 10টি node, edge l + 6m = 14 (ত্রিভুজের node “x2” দুটি আলাদা node, দুটিই ওপরের x2-তে যুক্ত), আর k = l + 2m = 6.

  4. প্রমাণ: প্রমাণ করুন যে 4-COLOR NP-complete. ইঙ্গিত: 3-COLOR থেকে reduction, একটি নতুন vertex দিয়ে। তারপর ব্যাখ্যা করুন, একই যুক্তি k ≥ 3-এর প্রতিটি k-COLOR-এর জন্য কেন চলে, আর k = 2-এ কেন থামে।
    1. 4-COLOR ∈ NP: certificate প্রতিটি vertex-এর রঙ (n-টি), verifier প্রতিটি edge-এ দুই প্রান্তের রঙ আলাদা কি না দেখে, O(n + e). — ছকের (ক)
    2. f(⟨G⟩) = ⟨G′⟩, যেখানে G′ = G-এর সঙ্গে একটি নতুন vertex u, যা G-এর প্রতিটি vertex-এর সঙ্গে যুক্ত। n-টি নতুন edge: polynomial. — গঠন
    3. ⇒: G-এর ৩-রঙ colouring নিয়ে u-কে চতুর্থ রঙ দিন; u-এর প্রতিটি edge-এর অন্য প্রান্ত প্রথম তিন রঙের, তাই G′ ৪-রঙযোগ্য। — নতুন রঙ
    4. ⇐: G′-এর ৪-রঙ colouring-এ u-এর রঙ G-এর কোনো vertex পায় না (সবাই u-এর প্রতিবেশী), তাই G-এর vertex-গুলো বাকি তিন রঙে সঠিকভাবে রাঙানো: G ৩-রঙযোগ্য। — u সবার প্রতিবেশী
    5. 3-COLOR NP-complete (অংশ ৫), আর 3-COLOR ≤p 4-COLOR, তাই উপপাদ্য ১.১ অনুযায়ী 4-COLOR NP-complete. ∎

    একই যুক্তি k-COLOR ≤p (k + 1)-COLOR দেয়, তাই induction-এ k ≥ 3-এর প্রতিটির জন্য NP-complete. k = 2-এ থামে, কারণ শুরুর ধাপটিই নেই: 1-COLOR থেকে শুরু করলে কোনো কঠিন সমস্যা পাওয়া যায় না, আর 2-COLOR P-তে (BFS). এই reduction-টি দিক রক্ষা করে উপরে ওঠে, নিচে নামে না।

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

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

ক্রমএকটি নতুন সমস্যা B-কে NP-complete প্রমাণ করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. certificate আর polynomial-time verifier দিয়ে B ∈ NP দেখানো
  2. একটি পরিচিত NP-complete সমস্যা A বাছাই করা, যেমন 3SAT
  3. A-এর instance থেকে B-এর instance বানানোর f নকশা করা
  4. f polynomial সময়ে চলে, তা দেখানো
  5. দুই দিক প্রমাণ: w ∈ A ⇒ f(w) ∈ B, আর f(w) ∈ B ⇒ w ∈ A

একটি নতুন সমস্যা B ∈ NP-কে NP-complete দেখাতে কোন reduction যথেষ্ট?

  • B ≤p 3SAT
  • 3SAT ≤p B
  • 2SAT ≤p B
  • 3SAT থেকে B-এ একটি exponential সময়ের রূপান্তর

3SAT ≤p SUBSET-SUM-এর অঙ্ক-সারণি (Sipser) তিন চলক আর দুই clause-এর একটি 3-CNF সূত্রে প্রয়োগ করলে লক্ষ্য t কত হয়?

  • 11111
  • 33311
  • 11133
  • 11122

3SAT ≤p VERTEX-COVER-এর সরাসরি গঠনে (চলক-edge, clause-ত্রিভুজ, যোগসূত্র) l = 4 চলক আর m = 5 clause-এর সূত্র থেকে graph-এ কয়টি node আর k কত?

  • 23টি node, k = 14
  • 23টি node, k = 9
  • 19টি node, k = 14
  • 18টি node, k = 9

নিচের কোন সমস্যাটি polynomial সময়ে সমাধানযোগ্য বলে প্রমাণিত?

  • একটি graph তিন রঙে রাঙানো যায় কি না
  • একটি directed graph-এ s থেকে t Hamiltonian path আছে কি না
  • প্রতি clause-এ তিনটি literal-এর CNF satisfiable কি না
  • প্রতি clause-এ দুটি literal-এর CNF satisfiable কি না

SUBSET-SUM-এর O(n · t) সময়ের dynamic programming থাকা সত্ত্বেও কেন বলা যায় না SUBSET-SUM ∈ P?

  • DP কিছু instance-এ ভুল উত্তর দেয়
  • t-এর মান তার bit-দৈর্ঘ্যের সূচকীয়, তাই O(n · t) input-দৈর্ঘ্যের polynomial নয়
  • SUBSET-SUM NP-তেই নেই
  • SUBSET-SUM strongly NP-complete

NP-complete সমস্যা নিয়ে কোন বক্তব্যটি সঠিক?

  • এদের প্রতিটি instance সমাধান করতে সূচকীয় সময় লাগে
  • এদের কোনো polynomial algorithm নেই, তা প্রমাণিত
  • এদের যেকোনো একটি P-তে থাকলে P = NP
  • সব NP-complete সমস্যা approximation-এর দিক থেকেও সমান কঠিন

শব্দকোষ

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

মনে রাখুন

  1. A NP-complete, B ∈ NP আর A ≤p B হলে B NP-complete; তীর সবসময় পরিচিত কঠিন সমস্যা থেকে নতুন সমস্যায়।
  2. 3SAT ≤p VERTEX-COVER: চলক-edge, clause-ত্রিভুজ, যোগসূত্র, k = l + 2m; ⇐ দিকে আঁটসাঁট গোনা।
  3. 3SAT ≤p SUBSET-SUM: দশমিক অঙ্কের সারণি, t = 1…1 3…3, carry নেই; HAMPATH-এ diamond, 3-COLOR-এ palette আর OR-gadget; সেখান থেকে UHAMPATH আর TSP.
  4. দেখতে কাছাকাছি সহজ সমস্যা: 2SAT (implication graph আর SCC), 2-COLOR, Euler path, bipartite matching, সবচেয়ে ছোট পথ।
  5. SUBSET-SUM weakly NP-complete (pseudo-polynomial DP); bin packing, TSP, 3-COLOR strongly. NP-complete মানে worst case কঠিন, প্রতিটি instance নয়; P ≠ NP প্রমাণিত নয়।

পরের পর্বে: coNP, NP-hard আর search বনাম decision: “না” উত্তরের প্রমাণ, NP-এর বাইরের NP-hard সমস্যা, আর decision-এর উত্তরদাতা দিয়ে আসল সমাধান খুঁজে বের করা।

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

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