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

coNP, NP-hard আর search বনাম decision

coNP and coNP-Completeness, NP ∩ coNP, NP-Hard Problems Outside NP, Self-Reducibility, and Cook versus Karp Reductions

Taught in Bangla, this lesson defines coNP two ways, proves that TAUTOLOGY and UNSAT are coNP-complete, and shows that an NP-complete problem in coNP would give NP = coNP. It explains resolution certificates for UNSAT, NP ∩ coNP with FACTOR, the NP-hard but undecidable halting problem, self-reducibility of SAT and Cook versus Karp reductions. In-page Python (Pyodide) checks each step, and a real PySAT run with Glucose on pigeonhole formulas is checked by an independent proof checker.

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

  • coNP-এর দুই রকম সংজ্ঞা (complement দিয়ে, আর “সব certificate” verifier দিয়ে), আর TAUTOLOGY ও UNSAT
  • coNP-complete-এর সংজ্ঞা, প্রমাণসহ: “NP-complete সমস্যা coNP-তে থাকলে NP = coNP”
  • UNSAT-এর certificate কেমন হতে পারে (resolution), আর কেন তা ছোট হবে এমন নিশ্চয়তা নেই
  • NP ∩ coNP, NP-hard কিন্তু NP-এর বাইরে এমন সমস্যা, আর ধারণাগুলোর পুরো মানচিত্র
  • SAT-এর search-কে decision-এ নামানোর প্রমাণ, FP আর FNP, আর Cook বনাম Karp reduction

১ · “না” উত্তরের প্রমাণ — coNP-এর ধারণা

বাজারঘরের delivery বিভাগ প্রতিদিন সকালে অর্ডারগুলোকে তিনটি delivery slot-এ ভাগ করে। দুটি অর্ডার একই ভ্যানের দরকার হলে তারা “সংঘাতে” থাকে, আর একই slot পায় না। এটি graph colouring-এর প্রশ্ন: অর্ডার vertex, সংঘাত edge, আর slot রং। প্রশ্নটি 3-COLOR, যা NP-তে আছে (পর্ব ৫৮)।

একদিন manager দুটি আলাদা দাবি শুনলেন। প্রথম কর্মী বললেন, “তিন slot-এ ভাগ করা যায়।” প্রমাণ সহজ: তিনি একটি তালিকা দেখালেন, কোন অর্ডার কোন slot-এ। Manager প্রতিটি সংঘাত মিলিয়ে দেখলেন, কাজ শেষ। দ্বিতীয় কর্মী অন্য দিনের অর্ডার নিয়ে বললেন, “আজ তিন slot-এ ভাগ করা যায় না।” Manager জিজ্ঞেস করলেন, “প্রমাণ কী?” এবার উত্তর কঠিন। “আমি অনেক চেষ্টা করেছি” কোনো প্রমাণ নয়। সব সম্ভাব্য ভাগ লিখে দেখানো একটি প্রমাণ, কিন্তু ৬০টি অর্ডারে তা 360-এর মতো সারি। কখনো কখনো ছোট যুক্তি পাওয়া যায়: “এই চারটি অর্ডারের প্রতিটি জোড়া সংঘাতে আছে, তাই চারটি আলাদা slot লাগে।” কিন্তু প্রতিটি “না”-দিনের এমন ছোট যুক্তি থাকবেই, তা কেউ জানে না।

পরীক্ষার হলে রোল নম্বর মিলিয়ে “এই ছাত্র উপস্থিত” প্রমাণ করা সহজ: তাঁকে দেখালেই হলো। কিন্তু “এই হলে কোনো নকলের কাগজ নেই” প্রমাণ করতে হলে পুরো হল তল্লাশি করতে হয়। প্রথমটি “আছে” ধরনের দাবি, একটি উদাহরণই প্রমাণ। দ্বিতীয়টি “কোথাও নেই” ধরনের দাবি; একটি উদাহরণ দিয়ে তা প্রমাণ হয় না। NP হলো প্রথম ধরনের দাবির জগৎ, আর coNP দ্বিতীয় ধরনের।

NP-এর সংজ্ঞায় এই অসমতা লুকিয়ে ছিল: “হ্যাঁ” উত্তরের ছোট certificate থাকতে হবে, “না” উত্তরের কোনো শর্ত নেই। পর্ব ৫৮-এর শেষে এর পূর্বাভাস দেখেছেন। এই পর্বে প্রশ্নটি উল্টে দেখা হবে: কোন সমস্যায় “না” উত্তরের ছোট প্রমাণ আছে, তারা কতটা কঠিন, আর সব মিলিয়ে NP-এর চারপাশের মানচিত্র কেমন। শেষে দেখবেন, “উত্তর আছে কি না” জানা আর “উত্তরটি খুঁজে দেওয়া” কতটা আলাদা।

২ · coNP-এর সংজ্ঞা — TAUTOLOGY আর UNSAT

একটি language L ⊆ Σ∗-এর complement L̄ = Σ∗ ∖ L, অর্থাৎ যেসব string L-এ নেই। কোনো decision problem-এর complement মানে প্রশ্নটি উল্টে দেওয়া: “হ্যাঁ” আর “না” অদলবদল। ভুলভাবে লেখা string (যা কোনো সূত্র বা graph-এর encoding-ই নয়) complement-এ পড়ে যায়; সেগুলো polynomial সময়ে চেনা যায়, তাই এই পর্বে উপেক্ষা করা হলো।

সংজ্ঞা ২.১ (coNP)

coNP = {L : L̄ ∈ NP}.

সমতুল্যভাবে, verifier-এর ভাষায়: L ∈ coNP ⇔ একটি polynomial-time verifier V আর polynomial p আছে, যাতে প্রতিটি w-এর জন্য

w ∈ L ⇔ ∀c (|c| ≤ p(|w|) হলে V ⟨w, c⟩ গ্রহণ করে).

∀ মানে “প্রতিটির জন্য”। NP-এর সংজ্ঞায় ছিল ∃ (অন্তত একটি ভালো certificate আছে); coNP-তে ∀ (কোনো certificate-ই দোষ ধরতে পারে না)। দুটি রূপ কেন একই, তা এক লাইনে: L̄ ∈ NP হলে L̄-এর verifier V′ নিন, আর V = “V′ গ্রহণ করলে বর্জন, নইলে গ্রহণ”। তাহলে w ∉ L ⇔ কোনো c V′-কে রাজি করায় ⇔ কোনো c V-কে বর্জন করায়। Deterministic verifier-এর উত্তর উল্টানো নিরাপদ; nondeterministic যন্ত্রে নয় (পর্ব ৪৬)। ভাষাগতভাবে, coNP-এর c হলো প্রতি-প্রমাণ: একটি ছোট সাক্ষ্য যে w ∉ L.

এই শ্রেণির দুটি প্রধান সদস্য Boolean সূত্র নিয়ে, যেখানে SAT = {⟨φ⟩ : φ satisfiable}:

  • UNSAT = {⟨φ⟩ : φ-কে কোনো মান-বসানোই সত্য করে না}. এটি SAT-এর complement, তাই সংজ্ঞা অনুযায়ী coNP-তে। “না” উত্তরের (অর্থাৎ φ satisfiable) প্রমাণ: একটি satisfying assignment.
  • TAUTOLOGY = {⟨φ⟩ : φ-কে প্রতিটি মান-বসানো সত্য করে}, যেমন x ∨ ¬x. এখানে “না” উত্তরের প্রমাণ: একটি সারি, যা φ-কে মিথ্যা করে। সারিটি বসিয়ে φ-এর মান বের করা polynomial কাজ, তাই TAUTOLOGY ∈ coNP. Tautology-র যুক্তিবিদ্যার দিক দেখুন ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ০৩-এ।
  • HAMPATH = {⟨G, s, t⟩ : s থেকে t কোনো Hamiltonian path নেই}. “না” উত্তরের প্রমাণ: একটি path.
  • PRIMES = {⟨n⟩ : n মৌলিক}. “না” উত্তরের প্রমাণ: একটি গুণনীয়ক। তাই PRIMES ∈ coNP; এর চেয়ে অনেক বেশি সত্য, কারণ PRIMES ∈ P (Agrawal–Kayal–Saxena ২০০২, পর্ব ৫৭)।

UNSAT আর TAUTOLOGY-র সম্পর্ক সরল: φ unsatisfiable ⇔ ¬φ সব সারিতে সত্য। CNF সূত্র φ-এর ¬φ De Morgan-এর নিয়মে একটি DNF সূত্র: প্রতিটি clause-এর প্রতিটি literal উল্টে OR-এর জায়গায় AND. এই রূপান্তর f সূত্রের দৈর্ঘ্যের রৈখিক সময়ে হয়, আর w ∈ UNSAT ⇔ f(w) ∈ TAUTOLOGY. অর্থাৎ UNSAT ≤p TAUTOLOGY. নিচের কোড f-কে সত্যিই একটি রূপান্তর হিসেবে লেখে (¬φ-কে আলাদা DNF হিসেবে মূল্যায়ন করে), আর দুটি চলকের ওপর ১ থেকে ৪টি clause-এর সব CNF সূত্রে “⇔” পরীক্ষা করে।

from itertools import product, combinations, combinations_with_replacement
# CNF = list of clauses (OR of literals); DNF = list of terms (AND of literals).
# Literal +i means x_i, -i means NOT x_i.
def lit(l, a): return a[abs(l)] == (l > 0)
def cnf_val(f, a): return all(any(lit(l, a) for l in c) for c in f)
def dnf_val(d, a): return any(all(lit(l, a) for l in t) for t in d)
def assignments(n):
    return [dict(zip(range(1, n + 1), b)) for b in product((False, True), repeat=n)]
def f_reduce(cnf):            # UNSAT -> TAUTOLOGY: NOT phi, written by De Morgan
    return [[-l for l in c] for c in cnf]
def in_unsat(cnf, n): return not any(cnf_val(cnf, a) for a in assignments(n))
def in_taut(dnf, n):  return all(dnf_val(dnf, a) for a in assignments(n))

clauses = [c for k in range(1, 5) for c in combinations((1, -1, 2, -2), k)]
formulas = [list(f) for m in range(1, 5)
            for f in combinations_with_replacement(clauses, m)]
agree = sum(in_unsat(f, 2) == in_taut(f_reduce(f), 2) for f in formulas)
print("CNF formulas over x1, x2 (1-4 clauses):", len(formulas))
print("unsatisfiable:", sum(in_unsat(f, 2) for f in formulas))
print("phi in UNSAT <=> f(phi) in TAUTOLOGY holds for", agree)

def refute_taut(dnf, n):      # certificate for a NO answer: one falsifying row
    return next((a for a in assignments(n) if not dnf_val(dnf, a)), None)
for cnf in ([[1, 2], [-1]], [[1, 2], [1, -2], [-1, 2], [-1, -2]]):
    d = f_reduce(cnf)
    print("f(phi) =", d, "| tautology:", in_taut(d, 2),
          "| falsifying row:", refute_taut(d, 2))

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

CNF formulas over x1, x2 (1-4 clauses): 3875
unsatisfiable: 380
phi in UNSAT <=> f(phi) in TAUTOLOGY holds for 3875
f(phi) = [[-1, -2], [1]] | tautology: False | falsifying row: {1: False, 2: True}
f(phi) = [[-1, -2], [-1, 2], [1, -2], [1, 2]] | tautology: True | falsifying row: None

চারটি literal-এর ১৫টি অ-ফাঁকা উপসেট clause হিসেবে, আর ১ থেকে ৪টি clause-এর সব সমাবেশ মিলে ৩,৮৭৫টি সূত্র; তার ৩৮০টি unsatisfiable. প্রতিটিতে “φ ∈ UNSAT ⇔ f(φ) ∈ TAUTOLOGY” মিলেছে। শেষ দুই লাইনে coNP-এর certificate দেখুন। φ = (x1 ∨ x2) ∧ ¬x1 satisfiable, তাই ¬φ tautology নয়, আর তার প্রমাণ একটি সারি: x1 = 0, x2 = 1, যেখানে ¬φ মিথ্যা। দ্বিতীয় সূত্রের ¬φ tautology; এখানে কোনো মিথ্যা সারি নেই, আর “নেই” কথাটির প্রমাণ এই কোড দিয়েছে সব সারি দেখে, যা n চলকে 2n-টি।

শেষ পর্যবেক্ষণটিই coNP-এর কেন্দ্রীয় প্রশ্ন। TAUTOLOGY-র “না” উত্তর ছোট প্রমাণে দেখানো যায়; কিন্তু “হ্যাঁ, এটি tautology” উত্তরের ছোট প্রমাণ সবসময় আছে কি? আছে কি না, তা ঠিক NP = coNP প্রশ্ন, যা পরের অংশে।

৩ · coNP-complete আর NP = coNP প্রশ্ন

প্রথমে যা সহজে প্রমাণ হয়। P complement-এ বদ্ধ: deterministic polynomial decider-এর accept আর reject অদলবদল করলে L̄-এর decider পাওয়া যায়। তাই P ⊆ NP থেকে P = coP ⊆ coNP, অর্থাৎ P ⊆ NP ∩ coNP.

উপপাদ্য ৩.১

(ক) NP ⊆ coNP হলে NP = coNP. (খ) P = NP হলে NP = coNP. সমতুল্যভাবে, NP ≠ coNP প্রমাণ হলে P ≠ NP-ও প্রমাণ হয়ে যেত।

প্রমাণ:

  1. (ক) ধরুন NP ⊆ coNP, আর L ∈ coNP. তাহলে L̄ ∈ NP ⊆ coNP, অর্থাৎ L̄-এর complement, মানে L, NP-তে। তাই coNP ⊆ NP, আর দুই দিক মিলে NP = coNP. — সংজ্ঞা ২.১ দুবার
  2. (খ) P = NP হলে NP = P = coP = coNP, কারণ P complement-এ বদ্ধ আর coNP হলো NP-এর সব complement. ∎

এর মানে NP ≠ coNP অনুমানটি P ≠ NP-এর চেয়ে শক্তিশালী দাবি: প্রথমটি সত্য হলে দ্বিতীয়টি আসে, উল্টোটি জানা নেই। বেশিরভাগ গবেষক দুটিকেই সত্য বলে মনে করেন, কিন্তু কোনোটিই প্রমাণিত নয়।

এবার কঠিনতম সদস্য। পর্ব ৫৯-এর ভাষায়, A ≤p B মানে এমন polynomial-time computable f আছে, যাতে w ∈ A ⇔ f(w) ∈ B.

সংজ্ঞা ৩.২ (coNP-complete)

B coNP-complete, যদি (১) B ∈ coNP, আর (২) প্রতিটি A ∈ coNP-এর জন্য A ≤p B.

উপপাদ্য ৩.৩

(ক) A ≤p B ⇔ Ā ≤p B̄. (খ) B NP-complete ⇔ B̄ coNP-complete. (গ) তাই UNSAT আর TAUTOLOGY coNP-complete.

প্রমাণ:

  1. (ক) একই f কাজ করে: w ∈ A ⇔ f(w) ∈ B, তাই দুই পাশে না-বোধক নিলে w ∉ A ⇔ f(w) ∉ B, অর্থাৎ w ∈ Ā ⇔ f(w) ∈ B̄. — “⇔”-এর দুই পাশ উল্টানো
  2. (খ, “⇒”) B ∈ NP, তাই B̄ ∈ coNP. যেকোনো A ∈ coNP নিন; Ā ∈ NP, আর B NP-hard বলে Ā ≤p B. (ক) থেকে A ≤p B̄. — সংজ্ঞা ৩.২
  3. (খ, “⇐”) একই যুক্তি উল্টো দিকে, NP আর coNP-এর ভূমিকা বদলে।
  4. (গ) SAT NP-complete (Cook–Levin, পর্ব ৬০), তাই তার complement UNSAT coNP-complete. অংশ ২-এর f দেখায় UNSAT ≤p TAUTOLOGY, আর TAUTOLOGY ∈ coNP; transitivity থেকে প্রতিটি coNP language TAUTOLOGY-তে reduce হয়। ∎
উপপাদ্য ৩.৪

কোনো NP-complete language B coNP-তে থাকলে NP = coNP. সমতুল্যভাবে, কোনো coNP-complete language NP-তে থাকলে NP = coNP.

প্রমাণ:

  1. প্রথমে একটি সহায়ক তথ্য: coNP ≤p-এর নিচে বদ্ধ। A ≤p B আর B ∈ coNP হলে উপপাদ্য ৩.৩(ক) থেকে Ā ≤p B̄ ∈ NP. NP ≤p-এর নিচে বদ্ধ (B̄-এর verifier-কে f(w)-এর ওপর চালান), তাই Ā ∈ NP, অর্থাৎ A ∈ coNP.
  2. যেকোনো A ∈ NP নিন। B NP-complete, তাই A ≤p B. — NP-hard-এর সংজ্ঞা
  3. B ∈ coNP আর ধাপ ১ থেকে A ∈ coNP. তাই NP ⊆ coNP. — closure
  4. উপপাদ্য ৩.১(ক) থেকে NP = coNP. দ্বিতীয় বাক্যের প্রমাণ একই, ভূমিকা বদলে। ∎

এই উপপাদ্যের ব্যবহার গবেষণায় খুব বাস্তব। কোনো সমস্যা NP আর coNP দুটিতেই প্রমাণিত হলে, সেটি NP-complete হওয়ার সম্ভাবনা কম বলে ধরা হয়, কারণ তাহলে NP = coNP হতো। অংশ ৫-এ এমন সমস্যা দেখবেন।

৪ · UNSAT-এর certificate কেমন হতে পারে — resolution

UNSAT-এর “হ্যাঁ” উত্তর, অর্থাৎ “φ-কে কিছুতেই সত্য করা যায় না”, প্রমাণ করার স্বাভাবিক একটি পদ্ধতি আছে: resolution. দুটি clause-এর একটিতে x আর অন্যটিতে ¬x থাকলে, দুটি জুড়ে x আর ¬x বাদ দিয়ে নতুন clause পাওয়া যায়: (x ∨ A) আর (¬x ∨ B) থেকে (A ∨ B). যুক্তি সহজ: যে মান-বসানো দুটিকে সত্য করে, x সত্য হলে B সত্য আর x মিথ্যা হলে A সত্য, তাই (A ∨ B) সত্য। ফাঁকা clause □ কোনো মানেই সত্য হয় না। তাই resolution-এর ধাপে □ পাওয়া গেলে মূল সূত্র unsatisfiable. এমন ধাপের তালিকাকে বলে resolution refutation; এটিই UNSAT-এর একটি certificate, আর প্রতিটি ধাপ মেলানো এক লাইনের কাজ। (Resolution সম্পূর্ণও: প্রতিটি unsatisfiable CNF-এর একটি refutation আছে; ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭-এ SAT solver-এর দিক থেকে দেখুন।)

1C1 = x1 ∨ x22C2 = x1 ∨ ¬x23C3 = ¬x1 ∨ x24C4 = ¬x1 ∨ ¬x25C5 = x16C6 = ¬x17C7 = □ (ফাঁকা)
এই ধাপে
কাজ
ফল
clause সংখ্যা
  1. Brute force দিয়ে শুরু। g-এর চলক দুটি, সারি চারটি। প্রতিটি সারি ঠিক একটি clause মিথ্যা করে: 00-তে C1, 01-তে C2, 10-তে C3, 11-তে C4. তাই g unsatisfiable. কিন্তু n চলকে এই পদ্ধতির দৈর্ঘ্য 2n.
  2. প্রথম resolution. C1-এ x2, C2-তে ¬x2. দুটি জুড়ে x2 বাদ দিলে থাকে x1 ∨ x1 = x1. মানে: g সত্য হলে x1 অবশ্যই সত্য।
  3. দ্বিতীয় resolution. C3-এ x2, C4-এ ¬x2. থাকে ¬x1. মানে: g সত্য হলে x1 অবশ্যই মিথ্যা।
  4. ফাঁকা clause. C5 = x1 আর C6 = ¬x1, x1-এ resolve করলে কিছুই থাকে না: □. একই সঙ্গে x1 সত্য আর মিথ্যা হতে পারে না, তাই কোনো মান-বসানো g-কে সত্য করে না।
  5. Verifier-এর কাজ। Certificate হলো তিনটি লাইন: (C1, C2, x2), (C3, C4, x2), (C5, C6, x1). Verifier প্রতিটিতে শুধু দেখে, দুটি clause-এ চলকটি উল্টো চিহ্নে আছে কি না, আর নতুন clause ঠিক লেখা কি না। তিনটি স্থানীয় check, কোনো খোঁজ নেই।

নিচের checker ঠিক এই verifier: ধাপের তালিকা নেয়, প্রতিটি resolvent নিজে গোনে, আর শেষে □ এসেছে কি না দেখে। দ্বিতীয় অংশে একটি pigeonhole formula: ৩টি পার্সেল, ২টি slot, প্রতিটি পার্সেল কোনো slot পায় কিন্তু কোনো slot-এ দুটি নয়, যা অসম্ভব। ইচ্ছা করে একটি ভুল ধাপ দেওয়া হয়েছে, checker তা ধরতে পারে কি না দেখতে।

from itertools import product
def resolve(c1, c2, v):          # c1 has v, c2 has NOT v  ->  the resolvent
    assert v in c1 and -v in c2, "the variable is not clashing"
    return (c1 - {v}) | (c2 - {-v})

def check_refutation(cnf, steps):          # a coNP certificate checker
    known = [frozenset(c) for c in cnf]
    for i, j, v in steps:
        r = frozenset(resolve(known[i], known[j], v))
        known.append(r)
        name = "{}" if not r else "{" + ", ".join(
            ("~" if l < 0 else "") + "x%d" % abs(l) for l in sorted(r, key=abs)) + "}"
        print(f"  C{len(known)} = resolve(C{i+1}, C{j+1}) on x{v}: {name}")
    return len(known[-1]) == 0             # empty clause = contradiction

def brute_sat(cnf, n):
    return [b for b in product((0, 1), repeat=n)
            if all(any(b[abs(l) - 1] == (l > 0) for l in c) for c in cnf)]

# g = (x1 v x2)(x1 v ~x2)(~x1 v x2)(~x1 v ~x2)
g = [{1, 2}, {1, -2}, {-1, 2}, {-1, -2}]
print("brute force: satisfying rows of g =", brute_sat(g, 2), "(checked 4 rows)")
print("refutation valid:", check_refutation(g, [(0, 1, 2), (2, 3, 2), (4, 5, 1)]))

# Pigeonhole PHP(3,2): 3 parcels, 2 slots; p_ij = parcel i in slot j -> var 2i+j+1
v = lambda i, j: 2 * i + j + 1
php = [{v(i, 0), v(i, 1)} for i in range(3)] + \
      [{-v(i, j), -v(k, j)} for j in range(2) for i in range(3) for k in range(i + 1, 3)]
print("PHP(3,2): clauses", len(php), "| satisfying rows:",
      len(brute_sat(php, 6)), "of", 2 ** 6)
try:
    check_refutation(php, [(0, 3, 1), (1, 4, 2)])     # a wrong step on purpose
except AssertionError as e:
    print("checker rejects a bad step:", e)

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

brute force: satisfying rows of g = [] (checked 4 rows)
  C5 = resolve(C1, C2) on x2: {x1}
  C6 = resolve(C3, C4) on x2: {~x1}
  C7 = resolve(C5, C6) on x1: {}
refutation valid: True
PHP(3,2): clauses 9 | satisfying rows: 0 of 64
  C10 = resolve(C1, C4) on x1: {x2, ~x3}
checker rejects a bad step: the variable is not clashing

g-এর তিন ধাপের refutation stepper-এর সঙ্গে হুবহু মিলেছে, শেষে ফাঁকা clause {}. Pigeonhole সূত্রে ৯টি clause, আর ৬৪টি সারির একটিও সত্য করে না। প্রথম ধাপটি বৈধ (C1-এ x1, C4-এ ¬x1), কিন্তু দ্বিতীয় ধাপে C2 = {x3, x4}-এ x2 নেই, তাই checker বর্জন করেছে। Verifier কখনো নিজে প্রমাণ খোঁজে না; শুধু দেওয়া ধাপগুলো মেলায়।

তাহলে কি UNSAT ∈ NP, resolution refutation-কে certificate ধরে? না, কারণ সংজ্ঞায় certificate-এর দৈর্ঘ্য |φ|-এর polynomial হতে হবে, আর refutation ছোট হবে এমন নিশ্চয়তা নেই। Haken ১৯৮৫ সালে প্রমাণ করেন, n + 1 কবুতর n খোপের pigeonhole সূত্রের প্রতিটি resolution refutation n-এর সূচকীয় দৈর্ঘ্যের। এটি শুধু resolution-এর সীমা; অন্য কোনো শক্তিশালী প্রমাণ-পদ্ধতিতে সব tautology-র ছোট প্রমাণ আছে কি না, সেই প্রশ্ন NP = coNP-এর সমতুল্য (ভাবনার প্রশ্ন ১)।

একটি সত্যিকারের SAT solver দিয়ে দেখা। আধুনিক SAT solver “UNSAT” বলার সঙ্গে একটি প্রমাণ-লগও দিতে পারে, যার প্রতিটি লাইন একটি নতুন clause; প্রতিটি লাইন আগের clause থেকে unit propagation দিয়ে যাচাই করা যায় (DRUP ধরনের প্রমাণ, resolution-এর ঘনিষ্ঠ আত্মীয়)। uv দিয়ে বানানো একটি ছোট প্রকল্পে PySAT (python-sat, MIT licence; এর ভেতরের Glucose solver-ও উন্মুক্ত licence-এর) দিয়ে PHP(n + 1, n) সমাধান করা হলো। PySAT-এর source-এ কোনো network বা usage-reporting কোড নেই, তা পরীক্ষা করে নেওয়া হয়েছিল। ছোট তিনটি ক্ষেত্রে প্রমাণটি আমাদের নিজের লেখা, solver থেকে স্বাধীন একটি checker দিয়েও যাচাই করা হয়েছে।

from pysat.solvers import Glucose4
def php(n):                      # n+1 parcels (pigeons), n slots (holes)
    v = lambda p, h: p * n + h + 1
    cnf = [[v(p, h) for h in range(n)] for p in range(n + 1)]
    cnf += [[-v(p, h), -v(q, h)] for h in range(n)
            for p, q in combinations(range(n + 1), 2)]
    return cnf
# rup_check(cnf, proof): our own checker, every added lemma must follow
# from earlier clauses by unit propagation; ... (25 lines)
for n in range(4, 10):
    with Glucose4(bootstrap_with=php(n), with_proof=True) as s:
        sat = s.solve(); proof = s.get_proof()
    ...

সত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev21, Python 3.12.13):

~/bazarghar-toc$ uv run python unsat_proofs.py
python 3.12.13 | python-sat 1.9.dev21
PHP(5,4): vars  20  clauses   45  SAT=False  proof lemmas     30  literals     104  0.00s  my checker: VALID
PHP(6,5): vars  30  clauses   81  SAT=False  proof lemmas    157  literals     919  0.00s  my checker: VALID
PHP(7,6): vars  42  clauses  133  SAT=False  proof lemmas    888  literals    9098  0.00s  my checker: VALID
PHP(8,7): vars  56  clauses  204  SAT=False  proof lemmas   7406  literals  108612  0.09s
PHP(9,8): vars  72  clauses  297  SAT=False  proof lemmas  48009  literals  956291  1.08s
PHP(10,9): vars  90  clauses  415  SAT=False  proof lemmas 258230  literals 6318445  11.02s

সূত্রের আকার ধীরে বাড়ে: ৪৫ থেকে ৪১৫টি clause. কিন্তু solver-এর UNSAT-প্রমাণ বাড়ে প্রায় প্রতি ধাপে ৫ থেকে ১০ গুণ: ৩০টি lemma থেকে আড়াই লাখের বেশি, আর মোট literal ১০৪ থেকে ৬৩ লাখের বেশি। সময়ও একই ধাঁচে, ১১ সেকেন্ডে পৌঁছেছে। ছোট তিনটি প্রমাণ আমাদের checker স্বাধীনভাবে VALID বলেছে: “না, ১০টি পার্সেল ৯টি slot-এ ধরে না” কথাটির একটি যাচাইযোগ্য প্রমাণ সত্যিই আছে, শুধু তা বিশাল। সতর্কতা: এটি একটি solver-এর একটি প্রমাণ-পদ্ধতির হিসাব; সূচকীয় নিম্নসীমার গাণিতিক প্রমাণ Haken-এর, এই সংখ্যাগুলো তার উদাহরণ মাত্র।

৫ · NP ∩ coNP — যেখানে দুই উত্তরেরই ছোট প্রমাণ আছে

কিছু সমস্যায় “হ্যাঁ” আর “না” দুই উত্তরই ছোট প্রমাণে দেখানো যায়। সবচেয়ে পরিচিত উদাহরণ পূর্ণসংখ্যার উৎপাদক-বিশ্লেষণ (factoring). এর একটি decision রূপ:

সংজ্ঞা ৫.১ (FACTOR)

FACTOR = {⟨n, k⟩ : n-এর এমন একটি গুণনীয়ক d আছে, যেখানে 1 < d ≤ k}. n আর k binary-তে লেখা, তাই input-এর দৈর্ঘ্য মোটামুটি log n.

  • FACTOR ∈ NP. Certificate: d নিজে। Verifier দেখে 1 < d ≤ k আর n mod d = 0; একটি ভাগ, bit-দৈর্ঘ্যের polynomial সময়।
  • FACTOR ∈ coNP. “না” উত্তরের certificate: n-এর পুরো মৌলিক উৎপাদক-বিশ্লেষণ p1 · p2 ⋯ pm. Verifier দেখে (১) গুণফল ঠিক n, (২) প্রতিটি pi মৌলিক, যা PRIMES ∈ P বলে polynomial সময়ে হয়, আর (৩) প্রতিটি pi > k. তাহলে n-এর ক্ষুদ্রতম অতুচ্ছ গুণনীয়ক (যা সবসময় মৌলিক) k-এর চেয়ে বড়, তাই কোনো d ≤ k নেই। m ≤ log2 n, তাই certificate ছোট।

উদাহরণ: বাজারঘরের একটি পরীক্ষামূলক কুপন-নম্বর n = 91. ⟨91, 10⟩ ∈ FACTOR, certificate d = 7. ⟨91, 5⟩ ∉ FACTOR, প্রতি-certificate 91 = 7 · 13: দুটিই মৌলিক, দুটিই 5-এর বড়।

২০০২ সালের আগে PRIMES-এর ক্ষেত্রেও “হ্যাঁ” দিকের ছোট প্রমাণ জানা ছিল: Pratt ১৯৭৫ সালে দেখান যে প্রতিটি মৌলিক সংখ্যার একটি ছোট, polynomial সময়ে মেলানো যায় এমন certificate আছে (একটি primitive root আর n − 1-এর উৎপাদক-বিশ্লেষণ, পুনরাবৃত্তভাবে)। তাই PRIMES ∈ NP ∩ coNP অনেক আগেই জানা ছিল, আর ২০০২ সালে AKS দেখায় PRIMES ∈ P. Linear programming-এর decision রূপের গল্পও এমন: duality তত্ত্ব থেকে NP ∩ coNP-তে থাকা জানা ছিল, আর Khachiyan ১৯৭৯ সালে ellipsoid পদ্ধতিতে একে P-তে আনেন।

সাবধান: FACTOR-এর অবস্থা। FACTOR-এর কোনো polynomial-time (ক্লাসিক্যাল) algorithm জানা নেই, আর RSA-র মতো cryptography এই কঠিনতার অনুমানের ওপর দাঁড়িয়ে। আবার FACTOR NP-complete হলে উপপাদ্য ৩.৪ অনুযায়ী NP = coNP হতো; তাই বেশিরভাগ গবেষক মনে করেন এটি NP-complete নয়। দুটিই বিশ্বাস, প্রমাণ নয়। NP ∩ coNP = P কি না, তা-ও খোলা প্রশ্ন। Shor ১৯৯৪ সালে quantum computer-এর জন্য polynomial-time factoring algorithm দেন (পর্ব ৭৫)।

৬ · NP-hard কিন্তু NP-তে নয় — halting problem আর optimisation

পর্ব ৫৯-এর সংজ্ঞা: B NP-hard, যদি প্রতিটি A ∈ NP-এর জন্য A ≤p B. সংজ্ঞায় B-এর NP-তে থাকার কোনো শর্ত নেই। NP-complete মানে দুটিই: NP-hard এবং NP-তে। তাই NP-hard সমস্যা NP-এর চেয়ে অনেক কঠিন হতে পারে, এমনকি undecidable. সবচেয়ে চমকপ্রদ উদাহরণ halting problem.

উপপাদ্য ৬.১

HALTTM = {⟨M, w⟩ : M w-এ থামে} NP-hard, কিন্তু NP-তে নয়। তাই HALTTM NP-complete নয়।

প্রমাণ:

  1. একটি স্থির Turing machine M নিন: “input ⟨ψ⟩-এ: ψ ভুলভাবে লেখা হলে চিরকাল loop. নইলে ψ-এর চলকগুলোর সব মান-বসানো একে একে চেষ্টা; কোনোটি ψ-কে সত্য করলে থামা (গ্রহণ)। সব ব্যর্থ হলে চিরকাল loop.” — গঠন
  2. f(⟨φ⟩) = ⟨M, ⟨φ⟩⟩. M প্রতিটি φ-এর জন্য একই, তাই f শুধু একটি স্থির string আর φ-এর একটি কপি লেখে: O(|φ|) সময়। — f polynomial-time computable
  3. φ ∈ SAT ⇒ কোনো সারি φ-কে সত্য করে, M সেখানে থামে ⇒ f(⟨φ⟩) ∈ HALTTM. φ ∉ SAT ⇒ কোনো সারি কাজ করে না, M loop করে ⇒ f(⟨φ⟩) ∉ HALTTM. তাই SAT ≤p HALTTM. — দুই দিক
  4. যেকোনো A ∈ NP-এর জন্য A ≤p SAT (Cook–Levin), আর ≤p transitive, তাই A ≤p HALTTM: HALTTM NP-hard. — সংজ্ঞা
  5. NP-এর প্রতিটি language decidable (NP ⊆ EXP, পর্ব ৫৮), কিন্তু HALTTM undecidable (পর্ব ৫১)। তাই HALTTM ∉ NP. ∎

লক্ষ করুন, reduction-এর দিক পর্ব ৫২-এর নিয়ম মেনেই: পরিচিত কঠিন সমস্যা SAT থেকে নতুন সমস্যা HALT-এর দিকে। আরেকটি সূক্ষ্মতা: f-এর polynomial হওয়া জরুরি, কিন্তু M নিজে সূচকীয় সময় নিলেও কোনো সমস্যা নেই, কারণ f M-কে চালায় না, শুধু লেখে।

1f: ⟨φ⟩ থেকে ⟨M, ⟨φ⟩⟩ লেখা2M: পরের সারি a চেষ্টা3a φ-কে সত্য করে? থামা4সারি শেষ: চিরকাল loop
এই ধাপে
φ
সারি
M-এর অবস্থা
SAT ⇔ HALT
  1. f-এর কাজ। Input φ = (x1 ∨ x2) ∧ ¬x1. f লেখে ⟨M, ⟨φ⟩⟩: M-এর স্থির বর্ণনা আর φ-এর কপি। f M-কে চালায় না, তাই f-এর সময় |φ|-এর রৈখিক।
  2. M, প্রথম সারি। x1 = 0, x2 = 0: প্রথম clause x1 ∨ x2 মিথ্যা। M থামে না, পরের সারিতে যায়।
  3. M, দ্বিতীয় সারি। x1 = 0, x2 = 1: x1 ∨ x2 সত্য, ¬x1 সত্য। M থামে। φ ∈ SAT, আর ⟨M, ⟨φ⟩⟩ ∈ HALTTM.
  4. দ্বিতীয় instance. φ′ = x1 ∧ ¬x1. f আবার একই M লেখে, শুধু φ′ বদলে। M দুটি সারি চেষ্টা করে: x1 = 0-তে প্রথম clause, x1 = 1-এ দ্বিতীয় clause মিথ্যা।
  5. Loop. সারি শেষ, M ইচ্ছা করে চিরকাল loop-এ ঢোকে। φ′ ∉ SAT, আর ⟨M, ⟨φ′⟩⟩ ∉ HALTTM. Loop-টিই reduction-এর কৌশল: “না”-কে “থামে না” বানানো।
  6. উপসংহার। দুই দিকেই w ∈ SAT ⇔ f(w) ∈ HALTTM, আর f polynomial. তাই HALTTM NP-hard. কিন্তু HALTTM undecidable, তাই NP-তে নয়, আর NP-complete-ও নয়।

এবার একই reduction Python-এ। M এখানে একটি generator, যার প্রতিটি yield একটি ধাপ; f শুধু (M, φ) জোড়া ফেরত দেয়। চালানোর সময় একটি step cap (১,০০০ ধাপ) রাখা হয়েছে, কারণ loop-এ ঢুকলে M কখনো থামবে না।

from itertools import product, count
def M(phi_text):                 # the FIXED machine M, written as a step generator
    cnf = [[int(l) for l in c.split()] for c in phi_text.split("|")]
    n = max(abs(l) for c in cnf for l in c)
    for bits in product((False, True), repeat=n):
        yield "try"              # one step per assignment tried
        if all(any(bits[abs(l) - 1] == (l > 0) for l in c) for c in cnf):
            return               # a satisfying row: HALT
    for _ in count():
        yield "loop"             # no satisfying row: loop forever

def f(phi_text):                 # the reduction SAT <=p HALT: just write <M, phi>
    return ("M", phi_text)       # M is the same for every phi; cost O(|phi|)

def run_capped(pair, cap):
    machine, w = pair
    for steps, _ in enumerate(M(w), 1):
        if steps >= cap: return f"still running after {cap} steps"
    return f"halted after {steps} step(s)"

tests = {"(x1 v x2)(~x1)": "1 2|-1",
         "(x1)(~x1)": "1|-1",
         "(x1 v x2)(x1 v ~x2)(~x1 v x2)(~x1 v ~x2)": "1 2|1 -2|-1 2|-1 -2",
         "(~x1 v ~x2 v x3)(x1)(x2)": "-1 -2 3|1|2"}
for name, phi in tests.items():
    print(f"{name:42} -> f gives {len(str(f(phi)))} chars;",
          run_capped(f(phi), 1000))

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

(x1 v x2)(~x1)                             -> f gives 15 chars; halted after 2 step(s)
(x1)(~x1)                                  -> f gives 13 chars; still running after 1000 steps
(x1 v x2)(x1 v ~x2)(~x1 v x2)(~x1 v ~x2)   -> f gives 28 chars; still running after 1000 steps
(~x1 v ~x2 v x3)(x1)(x2)                   -> f gives 20 chars; halted after 8 step(s)

প্রথম লাইন stepper-এর মতো: দ্বিতীয় সারিতে থামে। দুটি unsatisfiable সূত্রে (দ্বিতীয় আর তৃতীয়) M ১,০০০ ধাপ পরেও চলছে। শেষ সূত্রটি satisfiable, কিন্তু একমাত্র সমাধান x1 = x2 = x3 = 1, যা ৮টি সারির শেষটি, তাই ৮ ধাপে থামে। f-এর আউটপুটের দৈর্ঘ্য সূত্রের দৈর্ঘ্যের সঙ্গে রৈখিক। একটি সতর্কতা: “১,০০০ ধাপ পরেও চলছে” দেখে কেউ সাধারণভাবে বলতে পারে না যে যন্ত্রটি কখনো থামবে না; এখানে আমরা জানি, কারণ M-এর গঠন জানা। এই সীমার কথা পর্ব ৫১-এ ছিল।

HALT-এর বাইরেও NP-hard সমস্যার দুটি বড় দল আছে। প্রথম, EXP-এর কঠিনতম সমস্যাগুলো: প্রতিটি NP language EXP-এ, তাই কোনো EXP-complete সমস্যায় (polynomial reduction-এর অর্থে) সব NP সমস্যা reduce হয়, অর্থাৎ সেটি NP-hard. Time hierarchy (পর্ব ৬৭) থেকে এরা P-তে নেই। এমন একটি পরিচিত উদাহরণ n × n বোর্ডে সাধারণীকৃত দাবা, যা Fraenkel আর Lichtenstein ১৯৮১ সালে EXP-complete দেখান। দ্বিতীয় দল optimisation আর search রূপ, যেমন “বাজারঘরের সব জেলা ঘুরে আসার সবচেয়ে ছোট রুটের দৈর্ঘ্য বের করুন” (TSP-এর optimisation রূপ)। এগুলো language-ই নয়, তাই NP-তে থাকার প্রশ্নই ওঠে না; তাদের NP-hard বলা হয় অংশ ৮-এর Cook reduction-এর অর্থে: “এটি polynomial সময়ে সমাধান হলে P = NP হতো।”

নিচের stepper পুরো মানচিত্রটি ধাপে ধাপে আঁকে: কী প্রমাণিত, বেশিরভাগ গবেষক কী মনে করেন, NP-hard কোথায়, আর P = NP হলে ছবিটি কেমন হতো।

NP, coNP, P, EXP and NP-hard under two possible worlds EXP NP coNP P ? ড্যাশ = আলাদা কি না অজানা প্রমাণিত: P ⊆ NP ∩ coNP SAT 3-COLOR HAMPATH UNSAT TAUT FACTOR PATH P ≠ NP আর NP ≠ coNP হলে (বেশিরভাগ গবেষকের অনুমান) NP-complete coNP-complete EXP-complete (NP-hard) HALT: NP-hard undecidable, EXP-এর বাইরে P = NP = coNP SAT UNSAT FACTOR PATH 3-COLOR TAUT প্রায় সবই NP-complete P ≠ EXP তবুও প্রমাণিত
  1. যা প্রমাণিত। P ⊆ NP ∩ coNP, আর NP ও coNP দুটিই EXP-এর ভেতরে (সব certificate চেষ্টা করে)। P ≠ EXP-ও প্রমাণিত (পর্ব ৬৭)। কিন্তু প্রতিটি ড্যাশ দেওয়া সীমানা সত্যিই আলাদা কি না, অজানা।
  2. প্রচলিত বিশ্বাসের ছবি। P ≠ NP আর NP ≠ coNP ধরে: SAT, 3-COLOR, HAMPATH শুধু NP-তে; UNSAT, TAUTOLOGY শুধু coNP-তে; FACTOR দুটিরই মিলিত অংশে, কিন্তু সম্ভবত P-এর বাইরে; PATH P-তে। এটি অনুমান, প্রমাণ নয়।
  3. NP-hard কোথায়। লাল চিহ্ন: NP-complete সমস্যা, EXP-complete সমস্যা আর EXP-এর বাইরে HALT. লক্ষ করুন coNP-complete লাল নয়: Karp reduction-এ UNSAT NP-hard হলে NP ⊆ coNP হতো, তাই এই ছবিতে সে NP-hard নয়।
  4. P = NP হলে। তিনটি অঞ্চল একটিতে মিশে যায়: P = NP = coNP. তখন ∅ আর Σ∗ ছাড়া P-এর প্রতিটি language NP-complete. কিন্তু EXP-complete সমস্যা তবুও P-এর বাইরে, আর HALT তবুও undecidable.

৭ · Search বনাম decision — SAT-এর self-reducibility

এ পর্যন্ত সব শ্রেণি decision problem নিয়ে: উত্তর শুধু হ্যাঁ বা না। কিন্তু বাজারঘরের manager “হ্যাঁ, তিন slot-এ ভাগ করা যায়” শুনে খুশি হবেন না; তাঁর দরকার ভাগটি নিজেই। এটি search problem: একটি সাক্ষী y খুঁজে দেওয়া, বা বলা যে নেই। আর “সবচেয়ে কম ভ্যানে কীভাবে হয়?” একটি optimisation problem. প্রশ্ন: decision সহজ হলে কি search-ও সহজ? SAT-এর ক্ষেত্রে উত্তর হ্যাঁ, আর প্রমাণটি সুন্দর।

উপপাদ্য ৭.১ (SAT-এর self-reducibility)

ধরুন D একটি decider, যা ⟨φ⟩ ∈ SAT কি না বলে দেয়। তাহলে D-কে বড়জোর n + 1 বার ডেকে, আর মাঝে polynomial কাজ করে, n চলকের যেকোনো satisfiable φ-এর একটি satisfying assignment পাওয়া যায়। বিশেষত SAT ∈ P হলে SAT-এর search রূপ polynomial সময়ে সমাধানযোগ্য।

প্রমাণ: φ|x=b মানে φ-এ x-এর জায়গায় b বসিয়ে সরল করা সূত্র (এটি |φ|-এর রৈখিক সময়ে লেখা যায়, আর দৈর্ঘ্য বাড়ে না)।

  1. D(φ) জিজ্ঞেস করা; “না” হলে “কোনো assignment নেই” বলে থামা। — ১টি ডাক
  2. φ0 = φ. i = 1, …, n-এর প্রতিটির জন্য: D(φi−1|xi=1) “হ্যাঁ” হলে bi = 1, নইলে bi = 0; φi = φi−1|xi=bi. — n-টি ডাক
  3. অপরিবর্তনীয় শর্ত (invariant): প্রতিটি φi satisfiable. শুরুতে ধাপ ১ থেকে সত্য। ধরুন φi−1 satisfiable, আর তার একটি সমাধান xi-এ মান c দেয়; তাহলে φi−1|xi=c satisfiable. D “হ্যাঁ” বললে bi = 1 নিরাপদ। “না” বললে c = 1 হতে পারে না, তাই c = 0, আর bi = 0-ও নিরাপদ। — induction
  4. শেষে φn-এ কোনো চলক নেই আর সেটি satisfiable, অর্থাৎ সত্য। তাই (b1, …, bn) φ-কে সত্য করে। মোট n + 1টি ডাক, প্রতিটির input ≤ |φ|; বাকি কাজ polynomial. ∎
1D(φ)? না হলে: কোনো সমাধান নেই2i = 1 … n প্রতিটির জন্য:3  D(আগের মান + xi = 1)?4  হ্যাঁ: xi = 1; না: xi = 05সব মান স্থির: সমাধান
এই ধাপে
ডাক নং
প্রশ্ন
D-এর উত্তর
স্থির মান
  1. প্রথম ডাক। D বলে φ satisfiable. সে কোনো সমাধান দেখায় না, শুধু “হ্যাঁ”। এখন খোঁজা শুরু।
  2. x1 = 1 চেষ্টা। x1 = 1 হলে ¬x1 ∨ x3 থেকে x3 = 1 লাগে, আর ¬x1 ∨ ¬x3 থেকে x3 = 0 লাগে: অসম্ভব। D বলে “না”, তাই x1 = 0 স্থির; invariant অনুযায়ী এটি নিরাপদ।
  3. x2 = 1 চেষ্টা। x1 = 0-তে প্রথম clause বলে x2 = 1 লাগবেই। D বলে “হ্যাঁ”, তাই x2 = 1.
  4. x3 = 1 চেষ্টা। x2 = 1 হলে ¬x2 ∨ ¬x3 থেকে x3 = 0 লাগে। D বলে “না”, তাই x3 = 0. এখানে x3 = 0 যাচাই করতে আরেকটি ডাক লাগে না: invariant-ই নিশ্চয়তা দেয়।
  5. ফল। (x1, x2, x3) = (0, 1, 0). মিলিয়ে দেখুন: x1 ∨ x2 = 1, ¬x1 ∨ x3 = 1, ¬x2 ∨ ¬x3 = 0 ∨ 1 = 1, ¬x1 ∨ ¬x3 = 1. মোট ৪ = n + 1টি ডাক।

নিচের কোডে oracle শুধু হ্যাঁ/না বলে, কোনো সারি ফেরত দেয় না; ভেতরে সে brute force-এ কাজ করে, কিন্তু self-reduction তা জানে না। প্রথমে stepper-এর φ, তারপর বাজারঘরের পাঁচটি অর্ডারের delivery-slot সমস্যা, CNF-এ লেখা: চলক 3i + s + 1 মানে “অর্ডার i slot s পায়”।

from itertools import product
calls = rows = 0
def oracle(cnf, n, fixed):       # DECISION only: says yes/no, never shows a row
    global calls, rows
    calls += 1
    free = [x for x in range(1, n + 1) if x not in fixed]
    for bits in product((False, True), repeat=len(free)):
        rows += 1
        a = {**fixed, **dict(zip(free, bits))}
        if all(any(a[abs(l)] == (l > 0) for l in c) for c in cnf): return True
    return False

def self_reduce(cnf, n):         # search using n + 1 decision calls
    if not oracle(cnf, n, {}): return None
    fixed = {}
    for x in range(1, n + 1):
        fixed[x] = oracle(cnf, n, {**fixed, x: True})   # True works? keep it
    return fixed                  # else False must work: invariant kept

phi = [[1, 2], [-1, 3], [-2, -3], [-1, -3]]
print("phi:", self_reduce(phi, 3), "| oracle calls:", calls)

# Bazarghar: orders A..E, 3 delivery slots, conflicting orders need
# different slots. Variable 3*i + s + 1 = "order i gets slot s".
orders, conflicts = "ABCDE", ["AB", "BC", "CA", "CD", "DE"]
V = lambda o, s: 3 * orders.index(o) + s + 1
cnf = [[V(o, s) for s in range(3)] for o in orders]
cnf += [[-V(o, s), -V(o, t)] for o in orders for s in range(3) for t in range(s + 1, 3)]
cnf += [[-V(p, s), -V(q, s)] for p, q in conflicts for s in range(3)]
calls = rows = 0
a = self_reduce(cnf, 15)
plan = {o: s + 1 for o in orders for s in range(3) if a[V(o, s)]}
print("plan:", plan, "| clauses:", len(cnf))
print("oracle calls:", calls, "| rows tried inside the oracle:", rows)
print("valid:", all(plan[p] != plan[q] for p, q in conflicts))

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

phi: {1: False, 2: True, 3: False} | oracle calls: 4
plan: {'A': 1, 'B': 2, 'C': 3, 'D': 1, 'E': 2} | clauses: 35
oracle calls: 16 | rows tried inside the oracle: 21402
valid: True

φ-এর উত্তর stepper-এর মতোই (0, 1, 0), ৪টি ডাকে। Delivery সমস্যায় ১৫টি চলক, তাই ১৬টি ডাক, আর পাওয়া plan-এ পাঁচটি সংঘাতের প্রতিটিতে দুই অর্ডারের slot আলাদা। মোট খরচের বেশিরভাগ oracle-এর ভেতরে: ২১,৪০২টি সারি। Self-reduction নিজে সস্তা; কঠিন কাজ পুরোটাই decision-এ। তাই decision polynomial হলে search-ও polynomial.

সত্যিকারের solver-কে শুধু decision oracle হিসেবে। একই কৌশল PySAT-এর Glucose দিয়ে, বড় instance-এ: solver-এর কাছ থেকে শুধু হ্যাঁ/না নেওয়া হয় (assumption হিসেবে আগের মানগুলো দিয়ে), তার model কখনো পড়া হয় না। Random সংঘাত-graph, seed স্থির।

def oracle(cnf, fixed):          # DECISION only: is cnf + fixed literals satisfiable?
    global calls; calls += 1
    with Glucose4(bootstrap_with=cnf) as s:
        return s.solve(assumptions=fixed)          # the model is never read
def self_reduce(cnf, nvars):
    if not oracle(cnf, []): return None
    fixed = []
    for x in range(1, nvars + 1):
        fixed.append(x if oracle(cnf, fixed + [x]) else -x)
    return fixed

সত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev21, Python 3.12.13):

~/bazarghar-toc$ uv run python self_reduce.py
python 3.12.13 | python-sat 1.9.dev21
orders 30, conflicts  40: vars  90, oracle calls  91, plan valid: True
orders 60, conflicts  90: vars 180, oracle calls 181, plan valid: True
orders 12, conflicts  45: no 3-slot plan, oracle calls 1

৩০টি অর্ডারে ৯০টি চলক, তাই ঠিক ৯১টি ডাক; ৬০টিতে ১৮১টি। দুটি plan-ই প্রতিটি সংঘাত মেনেছে। তৃতীয় instance-এ (১২টি অর্ডার, ৪৫টি সংঘাত) প্রথম ডাকেই “না”, তাই খোঁজা শুরুই হয়নি। লক্ষ করুন, এই “না” উত্তরের সঙ্গে কোনো প্রমাণ আসেনি; সেটি দেখাতে হলে অংশ ৪-এর মতো UNSAT-প্রমাণ লাগত।

Optimisation-ও একই পথে। TSP-এর decision রূপ “দৈর্ঘ্য ≤ k এমন রুট আছে?” থেকে সবচেয়ে ছোট দৈর্ঘ্য পাওয়া যায় binary search-এ: দূরত্বগুলো পূর্ণসংখ্যা আর সব মিলিয়ে W-এর বেশি নয় হলে log2 W-এর মতো ডাক, যা input-এর bit-দৈর্ঘ্যের polynomial. তারপর রুটটি পেতে প্রতিটি রাস্তা একে একে মুছে দেখা: মুছলেও সর্বোত্তম দৈর্ঘ্য অটুট থাকলে মুছে ফেলা, নইলে রাখা। শেষে যা থাকে, তা-ই রুট।

FP আর FNP: function আর search সমস্যার জন্যও শ্রেণি আছে। FP হলো যেসব function problem deterministic polynomial সময়ে গোনা যায়। FNP হলো NP-এর search রূপ: একটি polynomial-time-যাচাইযোগ্য সম্পর্ক R(x, y), |y| ≤ p(|x|), দেওয়া আছে; x পেলে এমন y খুঁজে দিতে হবে, বা বলতে হবে নেই। একটি জানা ফল: FP = FNP ⇔ P = NP. এক দিক উপপাদ্য ৭.১-এর ধারণা, SAT-এর search সমাধান হলে decision-ও হয়; অন্য দিক, P = NP হলে SAT-এর self-reduction আর Cook–Levin মিলে যেকোনো FNP সম্পর্কের সাক্ষী খোঁজা যায়।

সাবধান: সব সমস্যায় decision আর search সমান নয়। COMPOSITES (“n যৌগিক?”) P-তে আছে, কারণ PRIMES ∈ P. কিন্তু একটি গুণনীয়ক খুঁজে দেওয়ার কোনো polynomial algorithm জানা নেই। কারণ COMPOSITES-এর উত্তরদাতা দিয়ে খোঁজা ছোট করার কোনো উপায় জানা নেই; FACTOR-এর মতো সীমা k-সহ রূপ থাকলে binary search চলে, কিন্তু সেই রূপটি P-তে আছে কি না অজানা। Self-reducibility একটি ধর্ম, যা প্রতিটি সমস্যার জন্য আলাদা করে প্রমাণ করতে হয়। প্রতিটি NP-complete সমস্যার ক্ষেত্রে এটি সত্য, কারণ তাদের search-কে SAT-এর search-এ নামানো যায়।

৮ · Cook reduction বনাম Karp reduction

Self-reduction-এ আমরা SAT-এর উত্তরদাতাকে বারবার প্রশ্ন করেছি। এটি একটি নতুন ধরনের reduction, যা পর্ব ৫২-এর Turing reduction-এর polynomial-সময় রূপ।

সংজ্ঞা ৮.১ (দুই রকম polynomial reduction)

Karp reduction (many-one), A ≤p B: polynomial-time f, যাতে w ∈ A ⇔ f(w) ∈ B. B-কে একবারই প্রশ্ন, আর উত্তরই চূড়ান্ত উত্তর।

Cook reduction, A ≤Tp B: B-এর oracle-সহ একটি polynomial-time deterministic oracle Turing machine A decide করে। Oracle-কে polynomial সংখ্যক বার প্রশ্ন করা যায়, উত্তর নিয়ে যা খুশি করা যায়, উল্টে দেওয়াসহ।

সম্পর্কগুলো এমন। (১) A ≤p B হলে A ≤Tp B: f(w) গুনে একবার প্রশ্ন। (২) দিকের নিয়মের প্রথম অংশ দুটিতেই খাটে: B ∈ P হলে A ∈ P, কারণ oracle-এর জায়গায় polynomial decider বসালে polynomial গুণ polynomial সময় লাগে। (৩) কিন্তু Cook reduction NP আর coNP-কে আলাদা করতে পারে না: UNSAT ≤Tp SAT, কারণ “D(φ)-কে জিজ্ঞেস করে উত্তর উল্টে দেওয়া” যথেষ্ট। অথচ UNSAT ≤p SAT হলে, NP ≤p-এর নিচে বদ্ধ বলে UNSAT ∈ NP, তাই উপপাদ্য ৩.৪ থেকে NP = coNP হতো।

বিষয়Karp (≤p)Cook (≤Tp)
প্রশ্নের সংখ্যাঠিক একবারpolynomial সংখ্যক বার
উত্তর উল্টানোচলে নাচলে
NP কি এর নিচে বদ্ধ?হ্যাঁ (প্রমাণিত)অজানা; হলে NP = coNP
UNSAT থেকে SATজানা নেই (থাকলে NP = coNP)এক প্রশ্নে, উত্তর উল্টে
সাধারণ ব্যবহারNP-complete-এর সংজ্ঞা আর প্রমাণsearch, optimisation, “সমাধান হলে P = NP”

তাই এই কোর্সে (Sipser-এর রীতিতে) NP-hard আর NP-complete সংজ্ঞায়িত Karp reduction দিয়ে; কিছু বই আর algorithm-এর আলোচনায় Cook reduction দিয়েও NP-hard বলা হয়। ইতিহাসে মজার একটি মোড় আছে: সাধারণভাবে বলা হয় Cook-এর ১৯৭১ সালের প্রবন্ধ oracle-ধরনের (polynomial-time Turing) reduction ব্যবহার করে, আর Karp ১৯৭২ সালে many-one reduction দিয়ে ২১টি সমস্যার NP-completeness দেখান; Levin স্বাধীনভাবে ১৯৭৩ সালে search সমস্যার ভাষায় একই ধারণায় পৌঁছান। দুটি সংজ্ঞায় NP-complete সমস্যার তালিকা প্রায় একই দেখায়, কিন্তু NP বনাম coNP-এর সূক্ষ্ম প্রশ্নে Karp reduction-ই সঠিক হাতিয়ার।

আরও গভীরে: Cook আর Reckhow ১৯৭৯ সালে দেখান, NP = coNP ⇔ এমন একটি propositional proof system আছে, যেখানে প্রতিটি tautology-র polynomial দৈর্ঘ্যের প্রমাণ আছে; সেখান থেকে proof complexity শাখা, যা একে একে শক্তিশালী প্রমাণ-পদ্ধতির নিম্নসীমা খোঁজে (Haken-এর resolution ফল তার প্রথম বড় সাফল্যগুলোর একটি)। Search-এর দিকে, যেসব সমস্যায় সাক্ষী সবসময় থাকে (যেমন factoring, বা একটি খেলার Nash equilibrium), তাদের শ্রেণি TFNP; Nash equilibrium খোঁজা PPAD নামের উপশ্রেণির জন্য complete, যা ২০০৬ সালের দিকে Daskalakis–Goldberg–Papadimitriou আর Chen–Deng-এর কাজে প্রমাণিত হয়। Bellare আর Goldwasser ১৯৯৪ সালে দেখান, কিছু জটিলতা-অনুমানের অধীনে NP-তে এমন language আছে, যার search decision-এ নামে না।

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

  • coNP-এর সংজ্ঞা আর একটি উদাহরণ দিন। {L : L̄ ∈ NP}; TAUTOLOGY, কারণ মিথ্যা করে এমন একটি সারি “না”-এর ছোট প্রমাণ।
  • NP-hard আর NP-complete-এর পার্থক্য? NP-complete = NP-hard + NP-তে থাকা; HALTTM NP-hard কিন্তু NP-তে নয়।
  • প্রমাণ করুন: P = NP হলে NP = coNP. P complement-এ বদ্ধ: NP = P = coP = coNP.
  • SAT-এর decider থেকে satisfying assignment কীভাবে? চলক একে একে 1 বসিয়ে জিজ্ঞেস; “না” হলে 0; n + 1টি ডাক।
  • FACTOR কেন NP-complete বলে মনে করা হয় না? এটি NP ∩ coNP-তে; NP-complete হলে NP = coNP হতো।

৯ · AI-এর যুগে coNP আর NP-hard

AI assistant এই বিষয়ে কয়েকটি ভুল বারবার করে। সবচেয়ে সাধারণ: “NP-hard মানে NP-এর সবচেয়ে কঠিন সমস্যা, তাই NP-তে”; “UNSAT NP-তে, কারণ SAT NP-তে আর উত্তর উল্টানো যায়”; reduction-এর দিক উল্টো (“SAT ≤p X দেখিয়ে X ∈ NP প্রমাণ”); আর NP = coNP বা NP ∩ coNP = P-কে প্রমাণিত বলা। Search আর decision-এ AI প্রায়ই “decision জানা থাকলে search সবসময় সহজ” লেখে, COMPOSITES-এর মতো ব্যতিক্রম ভুলে। একটি সুবিধাও আছে: AI কোনো সূত্রকে “unsatisfiable” বললে সেটি একটি দাবি, প্রমাণ নয়; একটি SAT solver বা ছোট ক্ষেত্রে brute force দিয়ে, আর সম্ভব হলে একটি resolution বা solver-প্রমাণ মিলিয়ে নিন।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“NP-hard সমস্যা NP-তে থাকে”HALTTM উদাহরণটি মনে রাখুন: NP-hard কিন্তু undecidable
“NTM-এর accept/reject উল্টে UNSAT ∈ NP”উল্টানো শুধু deterministic যন্ত্রে complement দেয়; NP = coNP খোলা
X ≤p SAT দেখিয়ে “X NP-hard”দিক পরীক্ষা করুন: কঠিনতা প্রমাণে পরিচিত NP-complete সমস্যা থেকে X-এ
Cook reduction দিয়ে NP-completeness প্রমাণoracle-এর উত্তর উল্টানো হয়েছে কি না, প্রশ্ন একাধিক কি না দেখুন
“FACTOR NP-complete” বা “FACTOR প্রমাণিতভাবে কঠিন”FACTOR ∈ NP ∩ coNP; কঠিনতা অনুমান মাত্র
Self-reduction-এ “না” এলে আবার 0 যাচাই করে, বা invariant বাদ দেয়ছোট সূত্রে ডাক গুনুন: ঠিক n + 1টি হওয়া উচিত

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞা, reduction-এর দিক, দুই দিকের যুক্তি আর কোনটি খোলা, এগুলো আলাদা করে চাওয়া, আর ছোট instance-এ নিজে কোড চালিয়ে মেলানো।

আমি গণনার তত্ত্ব শিখছি। CLIQUE = {⟨G, k⟩ : G-এ k আকারের clique আছে} NP-complete, তা ধরে নাও। ১. CLIQUE-এর complement-এর একটি “না” উত্তরের certificate কী, আর কেন complement-টি coNP-তে, ব্যাখ্যা করো। ২. CLIQUE-এর decision oracle ব্যবহার করে একটি k-clique খুঁজে বের করার self-reduction লেখো; oracle-কে কতবার ডাকতে হয়, গুনে দেখাও, আর invariant স্পষ্ট লেখো। ৩. এটি Cook reduction না Karp reduction, বলো, আর কেন। ৪. শুধু standard library দিয়ে Python-এ brute-force oracle আর self-reduction লেখো, একটি ৬-vertex graph-এ চালিয়ে ডাকের সংখ্যা আর পাওয়া clique দেখাও। ৫. NP = coNP, P = NP বা NP ∩ coNP = P নিয়ে কোনো দাবি করলে স্পষ্ট বলো কোনটি প্রমাণিত আর কোনটি খোলা; বানানো রেফারেন্স দিও না।

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

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

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

প্র ০১NP = coNP প্রশ্নটি “গণিতের প্রমাণ কত ছোট হতে পারে” প্রশ্নের সঙ্গে কীভাবে জড়িত? Cook–Reckhow-এর ধারণা কী বলে?

একটি propositional proof system হলো, মোটা দাগে, একটি polynomial-time যাচাইকারী P, যে একটি সূত্র φ আর একটি “প্রমাণ” π নিয়ে বলে π কি φ-এর বৈধ প্রমাণ; শর্ত দুটি: শুধু tautology-রই বৈধ প্রমাণ থাকে (soundness), আর প্রতিটি tautology-র অন্তত একটি প্রমাণ আছে (completeness). Truth table, resolution (¬φ-এর refutation), স্কুলের যুক্তিবিদ্যার axiom-নিয়মের পদ্ধতি, সবই এমন system. Cook আর Reckhow ১৯৭৯ সালে লক্ষ করেন, NP = coNP ⇔ এমন একটি system আছে, যেখানে প্রতিটি tautology-র প্রমাণ সূত্রের দৈর্ঘ্যের polynomial. কারণ সরল: এমন system থাকলে প্রমাণটিই TAUTOLOGY-র NP-certificate, আর TAUTOLOGY coNP-complete বলে coNP ⊆ NP. উল্টো দিকে, TAUTOLOGY ∈ NP হলে তার verifier-ই এমন একটি proof system.

এখান থেকে একটি গবেষণা-কর্মসূচি জন্ম নেয়: একে একে শক্তিশালী proof system নিয়ে দেখানো যে কিছু tautology-র ছোট প্রমাণ সেখানে নেই। Haken ১৯৮৫ সালে resolution-এর জন্য pigeonhole সূত্রে তা করেন, যার ছায়া অংশ ৪-এর solver-run-এ দেখেছেন: ১০টি পার্সেল ৯টি slot-এ ধরে না, এই প্রায় শিশুসুলভ কথাটির solver-প্রমাণে লাখ লাখ lemma. অথচ মানুষ এক লাইনে প্রমাণ করে, কারণ মানুষ “গুনতে” পারে, resolution পারে না। শক্তিশালী system (যেমন Frege system)-এর জন্য সূচকীয় নিম্নসীমা আজও প্রমাণিত নয়। প্রতিটি system-এর জন্য নিম্নসীমা প্রমাণ করলে NP ≠ coNP, আর তাই P ≠ NP-ও প্রমাণ হতো।

বাস্তবেও এর প্রভাব আছে। SAT solver যখন বলে “UNSAT”, তখন বড় শিল্প-প্রকল্প বা গণিতের প্রমাণে শুধু সেই কথায় ভরসা করা হয় না; solver একটি প্রমাণ-লগ দেয়, আর আলাদা, ছোট আর সহজে বিশ্বাসযোগ্য checker সেটি মেলায়। ২০১৬ সালে Heule, Kullmann আর Marek এভাবে Boolean Pythagorean triples সমস্যার সমাধান দেন, যার প্রমাণ-লগ প্রায় ২০০ terabyte. প্রমাণটি “যাচাইযোগ্য”, কিন্তু ছোট নয়; coNP প্রশ্নের এটাই সারকথা।

মূল উপলব্ধি: NP = coNP প্রশ্নটি আসলে জিজ্ঞেস করে, প্রতিটি সত্য “কখনোই না” দাবির ছোট, যাচাইযোগ্য প্রমাণ আছে কি না; proof complexity একে একে প্রমাণ-পদ্ধতির সীমা মেপে সেই প্রশ্নের দিকে এগোয়।

প্র ০২FACTOR NP ∩ coNP-তে আছে, আর তবুও RSA-র মতো cryptography এর কঠিনতার ওপর ভরসা করে। এই দুটি তথ্য কি পরস্পরবিরোধী?

না, তবে দুটি একসঙ্গে বুঝতে কয়েকটি সূক্ষ্ম পার্থক্য মনে রাখতে হয়। প্রথম, NP ∩ coNP-তে থাকা মানে সহজ হওয়া নয়। এর মানে শুধু এই যে “হ্যাঁ” আর “না” দুই উত্তরেরই ছোট প্রমাণ আছে; সেই প্রমাণ খুঁজে পাওয়া কঠিন হতে পারে। FACTOR-এর ক্ষেত্রে প্রমাণ হলো উৎপাদকগুলো নিজেই, আর সেগুলো খুঁজে বের করাই কঠিন কাজ। P ⊆ NP ∩ coNP প্রমাণিত, কিন্তু সমতা খোলা।

দ্বিতীয়, NP ∩ coNP-তে থাকার একটি পরোক্ষ অর্থ আছে: উপপাদ্য ৩.৪ অনুযায়ী FACTOR NP-complete হলে NP = coNP হতো, যা বেশিরভাগ গবেষক অবিশ্বাস্য মনে করেন। তাই FACTOR সম্ভবত NP-complete নয়। এটি cryptography-র জন্য একটু অস্বস্তিকর খবর: RSA এমন একটি সমস্যার ওপর দাঁড়িয়ে যা হয়তো “সবচেয়ে কঠিন” দলের নয়, আর P ≠ NP প্রমাণ হলেও factoring সহজ হতে পারত। Shor ১৯৯৪ সালে দেখান, একটি যথেষ্ট বড় quantum computer factoring polynomial সময়ে করতে পারবে; এটিই post-quantum cryptography নিয়ে কাজের একটি বড় কারণ।

তৃতীয়, cryptography-র দরকার worst-case কঠিনতা নয়, average-case কঠিনতা: random ভাবে বেছে নেওয়া চাবি ভাঙা কঠিন হতে হবে। NP-completeness শুধু worst case নিয়ে কথা বলে; একটি NP-complete সমস্যাও গড়পড়তা instance-এ সহজ হতে পারে। তাই cryptography-র নিরাপত্তা NP-completeness থেকে আসে না, বরং নির্দিষ্ট সমস্যার ওপর দশকের পর দশক ব্যর্থ আক্রমণের অভিজ্ঞতা আর “one-way function আছে” ধরনের অনুমান থেকে (পর্ব ৭৬)। আরেকটি তথ্য: one-way function থাকলে P ≠ NP হয়, তাই cryptography-র অস্তিত্বই একটি প্রমাণহীন কিন্তু বিশ্বাসযোগ্য অনুমান।

মূল উপলব্ধি: NP ∩ coNP মানে দুই দিকের প্রমাণ ছোট, খোঁজা সহজ নয়; FACTOR সম্ভবত NP-complete নয়, আর cryptography-র ভরসা average-case কঠিনতার অনুমানে, কোনো প্রমাণিত ফলে নয়।

প্র ০৩Complexity তত্ত্ব কেন decision problem দিয়ে লেখা হয়, যখন বাস্তবে আমাদের দরকার সমাধান নিজেই? এই সরলীকরণে কী হারায়?

Decision problem বেছে নেওয়ার প্রধান কারণ গাণিতিক সুবিধা। হ্যাঁ/না সমস্যা মানে একটি language, অর্থাৎ string-এর একটি সেট। তখন automata, Turing machine, complement, reduction সবকিছু একই ভাষায় লেখা যায়, আর পর্ব ০৫ থেকে যে কাঠামো গড়া হয়েছে, তা সরাসরি কাজে লাগে। দ্বিতীয় কারণ, কঠিনতা প্রমাণে decision রূপই যথেষ্ট শক্ত: decision যদি কঠিন হয়, তাহলে search আর optimisation আরও কঠিন বা সমান, কারণ সমাধান হাতে পেলে হ্যাঁ/না বলা তুচ্ছ। তাই “TSP-এর decision রূপ NP-complete” বললে optimisation রূপের কঠিনতাও বোঝা যায়।

উল্টো দিকে, decision সহজ হলে search-ও সহজ হবে, এই নিশ্চয়তা দরকার হয় algorithm-এর দিক থেকে। NP-complete সমস্যার জন্য self-reducibility সেই নিশ্চয়তা দেয়: SAT, CLIQUE, 3-COLOR, HAMPATH সবগুলোতে decision থেকে polynomial সংখ্যক প্রশ্নে search পাওয়া যায়। তাই NP-complete জগতে decision আর search “একই কঠিনতার”, আর তত্ত্বের সরলীকরণে কিছু হারায় না।

হারায় NP-complete জগতের বাইরে। COMPOSITES-এর decision P-তে, কিন্তু উৎপাদক খোঁজা অজানা। আরও নাটকীয় উদাহরণ এমন সমস্যা, যেখানে উত্তর সবসময় “হ্যাঁ”: প্রতিটি সসীম খেলায় Nash equilibrium আছে (Nash ১৯৫০), তাই decision রূপটি তুচ্ছ, কিন্তু equilibrium খুঁজে বের করা PPAD-complete, আর এর polynomial algorithm জানা নেই। এমন সমস্যার জন্য Megiddo আর Papadimitriou ১৯৯১ সালে TFNP শ্রেণির কথা বলেন। Bellare আর Goldwasser ১৯৯৪ সালে দেখান, কিছু অনুমানের অধীনে NP-তে এমন language আছে যার search decision-এ নামে না। অর্থাৎ decision রূপ সবসময় পুরো গল্প বলে না।

মূল উপলব্ধি: Decision রূপ কঠিনতা প্রমাণের জন্য যথেষ্ট আর NP-complete সমস্যায় search-এর সমান কঠিন; কিন্তু factoring বা Nash equilibrium-এর মতো সমস্যায় search আলাদা, আর সেখানে FNP, TFNP-এর মতো শ্রেণি লাগে।

প্র ০৪Cook reduction বেশি স্বাভাবিক মনে হয় (একটি subroutine বারবার ডাকা), তবু NP-completeness-এর সংজ্ঞায় Karp reduction কেন বেশি প্রচলিত?

Programmer-এর চোখে Cook reduction-ই স্বাভাবিক: “SAT-এর একটি দ্রুত library থাকলে আমার সমস্যা দ্রুত সমাধান হয়”, যেখানে library-কে যতবার খুশি ডাকা যায়। Algorithm-এর পাঠ্যবইয়ে “X NP-hard” বলার সময় অনেকে ঠিক এই অর্থই বোঝান: X polynomial সময়ে সমাধান হলে P = NP. Optimisation আর search সমস্যার জন্য, যেগুলো language-ই নয়, এই অর্থ ছাড়া উপায়ও নেই।

কিন্তু Cook reduction একটি গুরুত্বপূর্ণ পার্থক্য মুছে দেয়। এক প্রশ্নে উত্তর উল্টে UNSAT ≤Tp SAT, তাই Cook-এর অর্থে প্রতিটি coNP-complete সমস্যাও “NP-hard”, আর NP আর coNP একই দলে মিশে যায়। Karp reduction-এর নিচে NP বদ্ধ: A ≤p B আর B ∈ NP হলে A ∈ NP. এই বদ্ধতাই উপপাদ্য ৩.৪-এর মতো সূক্ষ্ম ফল সম্ভব করে, আর বলে যে NP-complete আর coNP-complete আলাদা দল, যদি না NP = coNP. Karp reduction আরও একটি কারণে পছন্দের: বাস্তবের NP-completeness প্রমাণগুলো প্রায় সবই এমনিতেই many-one, gadget দিয়ে একটি instance থেকে আরেকটি বানানো (পর্ব ৫৯ আর ৬১)। তাই কড়া সংজ্ঞায় কিছু হারায় না, বরং বেশি তথ্য পাওয়া যায়।

ইতিহাসেও এই টানাপোড়েন দেখা যায়। সাধারণভাবে বলা হয়, Cook ১৯৭১ সালের প্রবন্ধে oracle-ধরনের reduction ব্যবহার করেন, আর Karp পরের বছর many-one reduction দিয়ে ২১টি সমস্যার তালিকা দেন, যা NP-completeness-কে বিস্তৃত গবেষণার হাতিয়ার বানায়। আজও দুটি নাম পাশাপাশি চলে, আর বইয়ে কোন অর্থ, তা প্রথমে দেখে নেওয়া ভালো। আরও সূক্ষ্ম reduction-ও আছে: logspace reduction (P-এর ভেতরের প্রশ্নে, পর্ব ৬৬) আর Levin reduction (সাক্ষীও রূপান্তর হয়)।

মূল উপলব্ধি: Cook reduction “subroutine হিসেবে ব্যবহার” মাপে আর search-optimisation-এর জন্য স্বাভাবিক; Karp reduction কড়া, কিন্তু NP-কে বদ্ধ রাখে আর NP বনাম coNP-এর পার্থক্য ধরে রাখে, তাই NP-completeness-এর সংজ্ঞায় এটিই মান।

প্র ০৫“বাজারঘরের delivery পরিকল্পনা NP-hard” শুনে একজন manager বললেন, “তাহলে কম্পিউটার দিয়ে এর সমাধান অসম্ভব।” NP-hard লেবেলের সঠিক অর্থ কী, আর কী নয়?

NP-hard একটি তুলনামূলক বক্তব্য: সমস্যাটি NP-এর প্রতিটি সমস্যার অন্তত সমান কঠিন, polynomial reduction-এর অর্থে। এর সরাসরি অর্থ, এর polynomial-time সঠিক algorithm পাওয়া গেলে P = NP হবে; যেহেতু বেশিরভাগ গবেষক P ≠ NP মনে করেন, তাই সব instance-এ দ্রুত আর সবসময় সঠিক algorithm আশা করা বাস্তবসম্মত নয়। কিন্তু “অসম্ভব” কথাটি কয়েক দিক থেকে ভুল।

প্রথম, NP-hard মানে undecidable নয়। Delivery পরিকল্পনার decision রূপ NP-তে, তাই সূচকীয় সময়ে brute force দিয়েই সঠিক উত্তর পাওয়া যায়; প্রশ্ন শুধু গতির। HALTTM-এর মতো সত্যিকারের অসম্ভব সমস্যাও NP-hard, কিন্তু সেটি আলাদা কারণে। দ্বিতীয়, NP-hardness worst case-এর কথা। বাস্তবের instance প্রায়ই অনেক সহজ: আধুনিক SAT আর integer programming solver লাখ লাখ চলকের শিল্প-সমস্যা প্রায়ই দ্রুত সমাধান করে, যদিও pigeonhole-এর মতো কিছু ছোট সূত্রে আটকে যায় (অংশ ৪)। তৃতীয়, approximation: অনেক NP-hard optimisation সমস্যায় প্রমাণিত মানের কাছাকাছি সমাধান polynomial সময়ে পাওয়া যায় (পর্ব ৭১), আর বিশেষ কাঠামো থাকলে (যেমন ছোট parameter) দ্রুত exact algorithm-ও আছে (পর্ব ৭২)। DSA কোর্সের পর্ব ৬৫ এই বাস্তব কৌশলগুলো দেখায়।

তাই manager-কে সঠিক উত্তর হলো: “সবসময় সবচেয়ে ভালো plan দ্রুত বের করার নিশ্চিত পদ্ধতি সম্ভবত নেই; কিন্তু আমাদের আকারের instance-এ solver সম্ভবত ভালো plan দেবে, আর কতটা ভালো, তা-ও মাপা যায়।” আরেকটি সাধারণ ভুল উল্টো দিকের: ছোট পরীক্ষায় solver দ্রুত চলেছে দেখে “সমস্যাটি আসলে সহজ” বলা। কয়েকটি instance-এর সময় কোনো complexity প্রমাণ নয়।

মূল উপলব্ধি: NP-hard মানে সব ক্ষেত্রে দ্রুত আর নির্ভুল algorithm সম্ভবত নেই (P ≠ NP অনুমানে); এটি undecidable নয়, গড় বা বাস্তব instance-এর কঠিনতার কথা নয়, আর approximation বা solver ব্যবহার বন্ধ করে না।

অনুশীলন

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

  1. নকশা: আপনার কাছে শুধু 3-COLOR-এর একটি decision oracle আছে: একটি graph দিলে বলে তিন রঙে রাঙানো যায় কি না; আংশিক রং দেওয়ার কোনো উপায় নেই। বাজারঘরের পাঁচটি অর্ডার A–E, সংঘাত A–B, B–C, C–A, C–D, D–E. Oracle-কে polynomial সংখ্যক বার ডেকে একটি বৈধ slot-বণ্টন খুঁজে বের করার পদ্ধতি নকশা করুন, সঠিকতার যুক্তি দিন, আর এই instance-এ ডাক গুনুন (slot 1, 2, 3 ক্রমে চেষ্টা)।

    কৌশল: graph-এ একটি “রঙের palette” ত্রিভুজ t1, t2, t3 যোগ করুন (তিনটি পরস্পর যুক্ত, তাই তিনটি আলাদা রং নেয়; ti-এর রংকে slot i ধরা হয়)। vertex v-কে slot i দিতে v-কে বাকি দুটি t-এর সঙ্গে যুক্ত করুন; তখন v-এর রং ti-এর রং হতে বাধ্য। পদ্ধতি: (১) G + ত্রিভুজ 3-রঙযোগ্য কি না জিজ্ঞেস; না হলে থামা। (২) প্রতিটি v-এর জন্য i = 1, 2 চেষ্টা: v-কে বাকি দুটি t-এর সঙ্গে যুক্ত করে oracle “হ্যাঁ” বললে সেই edge রেখে দেওয়া; দুটিই “না” হলে slot 3, আর edge দুটি ডাক ছাড়াই যোগ। Invariant: বর্তমান graph সবসময় 3-রঙযোগ্য, SAT-এর self-reduction-এর মতোই। মোট ডাক ≤ 2m + 1, m = vertex সংখ্যা।

    এই instance-এ: প্রথম ডাক “হ্যাঁ”; A slot 1 (১টি ডাক); B: slot 1 না, slot 2 হ্যাঁ (২টি); C: 1 না, 2 না, তাই 3 (২টি); D slot 1 (১টি); E: 1 না, 2 হ্যাঁ (২টি)। মোট ৯টি ডাক (সীমা 2 · 5 + 1 = 11), ফল A = 1, B = 2, C = 3, D = 1, E = 2, যা self_reduce.py-র plan-এর সঙ্গে মেলে। Scratch-এ brute-force oracle দিয়ে গুনে দেখা হয়েছে।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: FACTOR NP-complete. প্রমাণ: (১) FACTOR ∈ NP, certificate একটি গুণনীয়ক d. (২) FACTOR ≤p SAT, কারণ ‘n-এর একটি গুণনীয়ক d ≤ k আছে’ কথাটি গুণের circuit দিয়ে একটি Boolean সূত্রে লেখা যায়। তাই FACTOR NP-complete.” ভুল কোথায়? দাবিটি সত্য হলে আর কী হতো?

    ধাপ (১) ঠিক। ভুল ধাপ (২)-এর দিকে: FACTOR ≤p SAT দেখায় FACTOR “SAT-এর চেয়ে কঠিন নয়”, অর্থাৎ শুধু আরেকবার FACTOR ∈ NP (NP ≤p-এর নিচে বদ্ধ)। NP-hard দেখাতে উল্টো দিক লাগে: একটি পরিচিত NP-complete সমস্যা, যেমন SAT, থেকে FACTOR-এ, অর্থাৎ SAT ≤p FACTOR. এমন কোনো reduction জানা নেই।

    দাবিটি সত্য হলে, FACTOR ∈ coNP বলে (প্রতি-certificate পুরো মৌলিক উৎপাদক-বিশ্লেষণ) উপপাদ্য ৩.৪ অনুযায়ী NP = coNP হতো। এটি অসম্ভব প্রমাণিত নয়, কিন্তু বেশিরভাগ গবেষক অবিশ্বাস্য মনে করেন, তাই FACTOR-কে NP-complete বলে ধরা হয় না।

  3. Trace (আউটপুট অনুমান): φ = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2) ∧ (¬x1 ∨ ¬x3) ∧ (¬x2 ∨ ¬x3), অর্থাৎ “ঠিক একটি চলক সত্য”। SAT-এর self-reduction (প্রথমে পুরো φ, তারপর x1, x2, x3 ক্রমে 1 বসিয়ে প্রশ্ন) চালালে oracle-এর উত্তরগুলো কী হবে, মোট কতটি ডাক, আর কোন assignment পাওয়া যাবে? φ-এর মোট কতটি satisfying assignment?

    ডাক ১: φ satisfiable? হ্যাঁ। ডাক ২: x1 = 1? হ্যাঁ (x2 = x3 = 0 দিয়ে), তাই x1 = 1. ডাক ৩: x1 = 1, x2 = 1? না (¬x1 ∨ ¬x2 ভাঙে), তাই x2 = 0. ডাক ৪: x1 = 1, x2 = 0, x3 = 1? না (¬x1 ∨ ¬x3 ভাঙে), তাই x3 = 0. মোট ৪ = n + 1টি ডাক, উত্তর-ক্রম হ্যাঁ, হ্যাঁ, না, না; ফল (1, 0, 0).

    Satisfying assignment ৩টি: (1, 0, 0), (0, 1, 0), (0, 0, 1). Self-reduction এদের মধ্যে প্রথমটি দেয়, কারণ সে প্রতিটি চলকে আগে 1 চেষ্টা করে। Scratch-এ brute force দিয়ে গোনা আর ডাক মিলিয়ে দেখা হয়েছে।

  4. প্রমাণ: প্রমাণ করুন: (ক) A ≤p B আর B ∈ coNP হলে A ∈ coNP. (খ) কোনো coNP-complete language B NP-তে থাকলে NP = coNP.

    (ক) ১. A ≤p B-এর f নিন; w ∈ A ⇔ f(w) ∈ B, তাই w ∈ Ā ⇔ f(w) ∈ B̄. — উপপাদ্য ৩.৩(ক) ২. B̄ ∈ NP; তার verifier V আর সীমা p নিন। Ā-এর verifier: “⟨w, c⟩-এ f(w) গুনে V ⟨f(w), c⟩ চালানো।” |f(w)| ≤ q(|w|) কোনো polynomial q-এর জন্য, তাই certificate-এর সীমা p(q(|w|)) আর সময় polynomial. — polynomial-এর সংযোজন polynomial ৩. তাই Ā ∈ NP, অর্থাৎ A ∈ coNP. ∎

    (খ) ১. যেকোনো A ∈ coNP নিন; B coNP-complete, তাই A ≤p B. ২. B ∈ NP আর NP ≤p-এর নিচে বদ্ধ ((ক)-এর ধাপ ২-এর মতো), তাই A ∈ NP. ৩. সুতরাং coNP ⊆ NP. ৪. complement নিলে NP ⊆ coNP, তাই NP = coNP. ∎

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

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

ক্রমSAT-এর decision oracle D থেকে n চলকের সূত্র φ-এর একটি satisfying assignment বের করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. D(φ) জিজ্ঞেস করা; “না” হলে কোনো assignment নেই বলে থামা
  2. পরের চলক xi-এ 1 বসিয়ে, আগের স্থির মানসহ, D-কে জিজ্ঞেস করা
  3. “হ্যাঁ” হলে xi = 1, “না” হলে xi = 0 স্থির করা
  4. সব n চলক স্থির না হওয়া পর্যন্ত আগের দুই ধাপ পুনরাবৃত্তি
  5. স্থির মানগুলো ফেরত দেওয়া; মোট n + 1টি ডাক

coNP শ্রেণির সঠিক সংজ্ঞা কোনটি?

  • যেসব language NP-তে নেই
  • যেসব language-এর complement NP-তে
  • যেসব language NP-hard কিন্তু NP-তে নেই
  • যেসব language-এর “হ্যাঁ” আর “না” দুই উত্তরেরই ছোট প্রমাণ আছে

HALTTM = {⟨M, w⟩ : M w-এ থামে} সম্পর্কে কোন বক্তব্যটি সঠিক?

  • এটি NP-complete
  • এটি NP-hard নয়, কারণ undecidable সমস্যা complexity শ্রেণিতে পড়ে না
  • এটি EXP-এ আছে, কারণ সব ধাপ চেষ্টা করা যায়
  • এটি NP-hard, কিন্তু NP-তে নয়

কোনো NP-complete language প্রমাণিতভাবে coNP-তে পাওয়া গেলে কী সিদ্ধান্ত টানা যায়?

  • NP = coNP
  • P = NP
  • P ≠ NP
  • কিছুই না, কারণ এমন হওয়া অসম্ভব বলে প্রমাণিত

FACTOR = {⟨n, k⟩ : n-এর একটি গুণনীয়ক d আছে, 1 < d ≤ k} সম্পর্কে নিচের কোনটি জানা সত্য?

  • এটি NP-complete
  • এটি P-তে, কারণ PRIMES ∈ P
  • এটি NP ∩ coNP-তে আছে
  • এটি NP-তে আছে, কিন্তু coNP-তে নেই বলে প্রমাণিত

UNSAT থেকে SAT-এ এমন reduction: “SAT-এর oracle-কে φ জিজ্ঞেস করে উত্তর উল্টে দেওয়া।” এটি কোন ধরনের reduction?

  • Karp (many-one) reduction
  • Cook (polynomial-time Turing) reduction
  • Computable mapping reduction, পর্ব ৫২-এর অর্থে
  • এটি কোনো বৈধ reduction নয়

φ = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x3). SAT-এর self-reduction প্রথমে পুরো φ, তারপর x1, x2, x3 ক্রমে 1 বসিয়ে oracle-কে জিজ্ঞেস করে। কোন assignment পাওয়া যায়, আর কতটি ডাকে?

  • (1, 0, 1), ৪টি ডাকে
  • (0, 1, 0), ৮টি ডাকে
  • (0, 1, 0), ৪টি ডাকে
  • (0, 0, 1), ৩টি ডাকে

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

  • NP ≠ coNP
  • NP ∩ coNP = P
  • প্রতিটি proof system-এ কিছু tautology-র প্রমাণ সূচকীয় দৈর্ঘ্যের
  • P = NP হলে NP = coNP

শব্দকোষ

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

মনে রাখুন

  1. coNP = {L : L̄ ∈ NP}: প্রতিটি “না” উত্তরের ছোট প্রমাণ আছে। TAUTOLOGY আর UNSAT coNP-complete; P ⊆ NP ∩ coNP.
  2. B NP-complete ⇔ B̄ coNP-complete. কোনো NP-complete সমস্যা coNP-তে থাকলে NP = coNP; P = NP হলেও NP = coNP. NP = coNP খোলা।
  3. NP ∩ coNP-তে FACTOR (আর আগে PRIMES, linear programming); এরা সম্ভবত NP-complete নয়, আর FACTOR P-তে আছে কি না অজানা।
  4. NP-hard-এর জন্য NP-তে থাকা লাগে না: SAT ≤p HALTTM, তাই halting problem NP-hard কিন্তু undecidable. NP-complete = NP-hard + NP.
  5. SAT self-reducible: n + 1টি decision প্রশ্নে search. এটি Cook reduction; NP-completeness-এর সংজ্ঞায় Karp reduction, কারণ Cook reduction NP আর coNP আলাদা করে না।

পরের পর্বে: P বনাম NP: প্রশ্নটির নিখুঁত রূপ, দুই দিকের পরিণাম, আর কেন এটি এত কঠিন, relativization, natural proofs আর Ladner-এর theorem.

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

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