এই পর্বে যা শিখবেন
- DPLL-এর নিয়মগুলো আর তার সঠিকতা ও সম্পূর্ণতার প্রমাণ
- CDCL-এ implication graph, decision level, first UIP, শেখা clause আর backjumping, আর শেখা clause কেন resolution থেকে আসে তার প্রমাণ
- সমস্যাকে CNF-এ লেখা: at-most-one encoding, symmetry ভাঙা, আর একটি সত্যিকারের solver দিয়ে সবচেয়ে কম slot খোঁজা
- Random 3SAT-এর phase transition, first moment পদ্ধতিতে প্রমাণিত সীমা, আর pigeonhole-এ CDCL-এর প্রমাণিত দেয়াল
- ILP formulation, LP relaxation আর integrality gap, আর WalkSAT ও Schöning-এর random walk
১ · NP-complete জানার পরে — সমস্যাকে solver-এর ভাষায় লেখা
বাজারঘরের অপারেশন দলের সামনে প্রতিদিন তিন ধরনের প্রশ্ন। ৫০টি অর্ডারের কিছু জোড়া একই রাইডার বা একই গাড়ি চায়, তাই একই delivery slot-এ যেতে পারে না: সবচেয়ে কম কয়টি slot লাগবে? আটটি অর্ডার তিনজন রাইডারের মধ্যে ভাগ করতে হবে, প্রত্যেকের সময়ের সীমা আছে: মোট যাত্রার মিনিট সবচেয়ে কম কীভাবে হবে? আর নতুন একটি নিয়ম এলে: এই সব শর্ত একসঙ্গে মানা আদৌ সম্ভব কি? প্রথমটি 3-COLOR-এর আত্মীয়, দ্বিতীয়টি একটি integer program, তৃতীয়টি সরাসরি SAT. পর্ব ৬১-এ এদের NP-complete প্রমাণ করেছেন। এখন প্রশ্ন: তবু কাজটা কীভাবে হয়?
হারানো চাবি খোঁজার কথা ভাবুন। “বাসার যেকোনো জায়গায় থাকতে পারে” মানে সবচেয়ে খারাপ ক্ষেত্রে পুরো বাসা ওল্টাতে হবে। কিন্তু অভিজ্ঞ মানুষ এলোমেলো খোঁজেন না: “আজ বাজারে গিয়েছিলাম, তাহলে ব্যাগে বা টেবিলে” (বাধ্য সিদ্ধান্ত ছড়ানো), “ড্রয়ারে একবার দেখেছি, আর দেখব না” (ভুল থেকে শেখা), আর আধা ঘণ্টা ব্যর্থ হলে গোড়া থেকে নতুন করে ভাবেন, অর্থাৎ restart করেন। SAT solver ঠিক এই কৌশলগুলোকে গাণিতিকভাবে নিখুঁত করেছে। সবচেয়ে খারাপ ক্ষেত্র বদলায়নি, বদলেছে সাধারণ ক্ষেত্র।
এখানে reduction-এর দিক উল্টো, আর সেটি ইচ্ছাকৃত। কঠিনতা প্রমাণে লিখি SAT ≤p X; সমাধান করতে লিখি X ≤p SAT: X-এর instance-কে একটি CNF সূত্রে রূপ দিয়ে একটি SAT solver-কে দেওয়া, আর solver-এর model থেকে X-এর উত্তর পড়া (polynomial-time reduction-এর সংজ্ঞা পর্ব ৫৯-এ)। Cook–Levin (পর্ব ৬০) নিশ্চয়তা দেয় যে NP-এর প্রতিটি সমস্যার জন্য এমন রূপান্তর আছে। সমাধানের যন্ত্রপাতি তিন রকম:
সম্পূর্ণ (complete) SAT solver
DPLL আর CDCL. SAT হলে model দেয়, UNSAT হলে সেটিও প্রমাণ করে। অংশ ২–৬.
ILP solver
Linear শর্ত আর একটি লক্ষ্য-ফাংশন, পূর্ণসংখ্যা চলক। LP relaxation দিয়ে সীমা, branch and bound দিয়ে খোঁজ। অংশ ৭.
অসম্পূর্ণ (incomplete) local search
WalkSAT-এর মতো heuristic: model দ্রুত পায়, কিন্তু “নেই” কখনো প্রমাণ করে না। অংশ ৮.
এই পর্বের দৃষ্টিভঙ্গি তাত্ত্বিক: প্রতিটি কৌশল কেন সঠিক, কোথায় তার প্রমাণিত সীমা, আর একটি সত্যিকারের solver সংখ্যায় কী দেখায়। ব্যবহারিক দিক থেকে solver বাছাই, benchmark আর সিদ্ধান্তদাতাকে বোঝানোর কথা DSA কোর্সের পর্ব ৬৫-এ, আর SAT/SMT দিয়ে software যাচাই ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭-এ আছে; এখানে সেগুলো আবার শেখানো হবে না।
২ · DPLL — unit propagation, pure literal আর branching
ইনপুট একটি CNF সূত্র φ: কয়েকটি clause-এর AND, প্রতিটি clause কয়েকটি literal-এর OR. আংশিক মান-বসানো α-এর নিচে একটি clause তিন অবস্থায় থাকে: সত্য (একটি literal সত্য), মিথ্যা (সব literal মিথ্যা), বা খোলা। খোলা clause-এ ঠিক একটি literal বাকি থাকলে তাকে বলে unit clause. Martin Davis আর Hilary Putnam ১৯৬০ সালে, আর Davis, George Logemann ও Donald Loveland ১৯৬২ সালে যে পদ্ধতি দেন, তার নাম DPLL:
DPLL(φ, α):
- Unit propagation: যতক্ষণ একটি unit clause (ℓ) আছে, α-তে ℓ = সত্য বসানো।
- কোনো clause মিথ্যা হলে “UNSAT এই শাখায়” ফেরত। সব clause সত্য হলে α ফেরত।
- Pure literal: কোনো চলক বাকি clause-গুলোতে শুধু একটি চিহ্নে থাকলে সেই literal সত্য বসানো।
- Branching: একটি খালি চলক x বেছে DPLL(φ, α ∪ {x = 1}) চালানো; ব্যর্থ হলে DPLL(φ, α ∪ {x = 0}).
যেকোনো CNF φ-এর জন্য DPLL(φ, ∅) থামে, আর একটি মান-বসানো ফেরত দেয় ⇔ φ satisfiable; ফেরত দেওয়া মানটি φ-কে সত্য করে।
প্রমাণ:
- থামা: প্রতিটি recursive call α-তে অন্তত একটি নতুন চলক বসায়, আর চলক n-টি; তাই call-গাছের গভীরতা ≤ n, আর প্রতিটি node-এ বড়জোর দুটি শাখা। — সসীম গাছ
- Unit নিয়ম satisfiability বদলায় না: α-কে বাড়ানো এমন যেকোনো model β-তে (ℓ) clause সত্য, আর তার বাকি literal α-তে মিথ্যা, তাই β-তে ℓ সত্য। অর্থাৎ ℓ = সত্য বসালে কোনো model হারায় না। — clause-এর সংজ্ঞা
- Pure literal নিয়ম satisfiability রক্ষা করে: ধরুন β একটি model আর ℓ pure. β-তে ℓ-এর চলক উল্টে ℓ সত্য করলে ¬ℓ আছে এমন কোনো clause নেই, তাই কোনো clause মিথ্যা হয় না; যেসব clause-এ ℓ আছে সেগুলো সত্যই থাকে। নতুন মানটিও model. (কিন্তু model-এর সেট বদলাতে পারে, তাই এটি equivalence নয়।) — pure-এর সংজ্ঞা
- Branching সম্পূর্ণ: α-কে বাড়ানো প্রতিটি model-এ x = 1 বা x = 0, তাই দুই শাখার একটিতে model থাকলে আরোহে (গভীরতার ওপর induction) সেই শাখা তা খুঁজে পায়। — দুই শাখা মিলে সব সম্ভাবনা
- সঠিকতা: ফেরত দেওয়া α-তে ধাপ ২ অনুযায়ী সব clause সত্য। তাই ফেরত ⇒ satisfiable; আর ধাপ ২–৪ মিলে satisfiable ⇒ ফেরত। ∎
একটি চার-clause সূত্রে DPLL হাতে চালানো যাক: φ = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x1 ∨ ¬x3) ∧ (¬x2 ∨ x3). শুরুতে কোনো unit clause নেই, আর প্রতিটি চলক দুই চিহ্নেই আছে, তাই pure literal-ও নেই। নিয়ম: সবচেয়ে ছোট চলক, আগে সত্য।
1C1 = x1 ∨ x22C2 = ¬x1 ∨ x33C3 = ¬x1 ∨ ¬x34C4 = ¬x2 ∨ x3
| trail | |
| বাকি clause | |
| call-গাছের node |
- প্রথম অনুমান। কোনো clause unit নয়, কোনো literal pure নয়। x1 = 1 অনুমান করা হলো (call-গাছের দ্বিতীয় বিন্দু)। C1 সত্য হয়ে গেল; C2 আর C3 থেকে ¬x1 মুছে গেল, থাকল শুধু x3 আর ¬x3.
- Unit propagation. C2 এখন unit (x3), তাই x3 = 1 বাধ্য। এতে C4 সত্য হলো, কিন্তু C3-এর শেষ literal ¬x3 মিথ্যা হয়ে গেল।
- বিরোধ। C3 = ¬x1 ∨ ¬x3-এর দুটি literal-ই মিথ্যা। এই শাখায় কোনো model নেই; DPLL শেষ অনুমানে ফিরে যায়।
- দ্বিতীয় শাখা। x1 = 0 (তৃতীয় বিন্দু)। এতে C2, C3 সত্য। C1 থেকে x1 মুছে unit (x2), তাই x2 = 1 বাধ্য।
- Model পাওয়া গেল। x2 = 1-এ C4 unit (x3), তাই x3 = 1. চারটি clause-ই সত্য: (x1, x2, x3) = (0, 1, 1). মোট তিনটি node, একটিমাত্র ফিরে-যাওয়া।
নিচের ব্লক একই DPLL চালিয়ে trail ছাপে, তারপর random 3CNF-এ unit propagation-সহ আর ছাড়া call-গাছের node গোনে। দুটি সংস্করণই সঠিক; পার্থক্য শুধু খোঁজের আকারে।
# DPLL with unit propagation: print the trail, count branching nodes
import random
def simplify(cnf, lit): # make lit true: drop satisfied clauses, shrink others
return [c - {-lit} for c in cnf if lit not in c]
def dpll(cnf, trail, stats, show, use_up=True):
stats["nodes"] += 1
while use_up and (unit := next((c for c in cnf if len(c) == 1), None)):
(lit,) = unit
trail.append(f"x{abs(lit)}={int(lit > 0)}(unit)")
cnf = simplify(cnf, lit)
if any(len(c) == 0 for c in cnf):
if show: print(" conflict after", " ".join(trail))
return None
if not cnf:
return trail
v = min(abs(l) for c in cnf for l in c) # branch on the smallest variable
for lit in (v, -v):
res = dpll(simplify(cnf, lit), trail + [f"x{v}={int(lit > 0)}(decide)"], stats, show, use_up)
if res: return res
return None
phi = [{1, 2}, {-1, 3}, {-1, -3}, {-2, 3}] # C1..C4
st = {"nodes": 0}
print("model trail:", " ".join(dpll(phi, [], st, True)), "| nodes", st["nodes"])
random.seed(72)
def rand3(n, m):
return [{v if random.random() < 0.5 else -v for v in random.sample(range(1, n + 1), 3)}
for _ in range(m)]
print(" n m SAT? nodes(with UP) nodes(no UP)")
for n in (12, 16, 20):
f = rand3(n, round(4.26 * n))
a, b = {"nodes": 0}, {"nodes": 0}
r1 = dpll(f, [], a, False); r2 = dpll(f, [], b, False, use_up=False)
assert bool(r1) == bool(r2)
print(f"{n:2} {len(f):3} {str(bool(r1)):5} {a['nodes']:10} {b['nodes']:13}")আসল আউটপুট (ব্রাউজারের Python):
conflict after x1=1(decide) x3=1(unit)
model trail: x1=0(decide) x2=1(unit) x3=1(unit) | nodes 3
n m SAT? nodes(with UP) nodes(no UP)
12 51 False 15 349
16 68 True 20 562
20 85 True 57 7910
প্রথম দুই লাইন stepper-এর সঙ্গে হুবহু মেলে: x1 = 1-এ x3 বাধ্য হয়ে বিরোধ, তারপর x1 = 0-তে x2 আর x3 বাধ্য, মোট ৩টি node. টেবিলে m ≈ 4.26n-এর random সূত্র; n = 12-এরটি unsatisfiable, তাই দুই সংস্করণকেই পুরো গাছ শেষ করতে হয়েছে। Unit propagation ছাড়া node-সংখ্যা প্রায় ২৩ থেকে ১৩৯ গুণ বেশি (n = 20-এ ৫৭ বনাম ৭,৯১০)। কারণটি সহজ: একটি অনুমান প্রায়ই একসঙ্গে অনেক চলককে বাধ্য করে, আর সেগুলো নিয়ে আর শাখা খুলতে হয় না।
একটি তাত্ত্বিক পর্যবেক্ষণ পরের অংশগুলোর জন্য জরুরি। Unsatisfiable φ-এ DPLL-এর পুরো call-গাছকে উল্টো দিক থেকে পড়লে একটি resolution refutation পাওয়া যায়, যার আকার গাছের আকারের সমান মাপের (একে বলে tree-like resolution; resolution-এর নিয়ম পর্ব ৬২-এ)। প্রতিটি পাতা একটি মিথ্যা clause, আর প্রতিটি শাখা-বিন্দু x-এ দুই সন্তানের clause x-এ resolve হয়। তাই DPLL যত চতুরই হোক, tree-like resolution-এ যে সূত্রের ছোট প্রমাণ নেই, সেখানে DPLL-এর গাছও বড় হতে বাধ্য।
৩ · CDCL — implication graph থেকে clause শেখা
DPLL একটি বড় দুর্বলতা নিয়ে চলে: বিরোধের কারণ মনে রাখে না। ধরুন x2-এর মান বিরোধের সঙ্গে সম্পর্কহীন, তবু DPLL x2-এর দুই মানেই একই বিরোধ আবার আবিষ্কার করবে। CDCL (conflict-driven clause learning) এই সমস্যা সারায়। মূল ধারণাগুলো João Marques-Silva আর Karem Sakallah-এর GRASP (১৯৯০-এর দশকের মাঝামাঝি) আর ২০০১ সালের Chaff solver থেকে আসে বলে সাধারণত উল্লেখ করা হয়।
প্রতিটি অনুমানের একটি decision level থাকে: প্রথম অনুমান level ১, দ্বিতীয়টি level ২, ইত্যাদি; unit propagation-এ বাধ্য হওয়া চলক তার কারণের level পায়। প্রতিটি বাধ্য চলকের একটি “কারণ-clause” থাকে, যেটি unit হয়ে তাকে বাধ্য করেছিল। এদের নিয়ে implication graph: প্রতিটি বসানো literal একটি node, আর কারণ-clause-এর অন্য literal-গুলো থেকে তার দিকে তীর। (পর্ব ৬১-এর 2SAT implication graph একটি ভিন্ন, পুরো সূত্রের graph.)
উদাহরণ সূত্র: C1 = (¬x1 ∨ x4), C2 = (¬x3 ∨ x5), C3 = (¬x5 ∨ ¬x2 ∨ x6), C4 = (¬x6 ∨ x7), C5 = (¬x6 ∨ ¬x4 ∨ x8), C6 = (¬x7 ∨ ¬x8). Solver অনুমান করে level ১-এ x1 = 1, level ২-এ x2 = 1, level ৩-এ x3 = 1.
Level ৩-এ বিরোধের implication graph
নীল = অনুমান, সাদা = বাধ্য, কমলা = first UIP (x6), লাল = বিরোধ। ড্যাশ রেখার ওপরের কারণ থেকে শেখা clause.
বিরোধের পর solver বিরোধী clause থেকে শুরু করে পিছনের দিকে resolve করে: বর্তমান level-এর যে literal সবার শেষে বসেছিল, তার কারণ-clause-এর সঙ্গে resolution. থামে তখন, যখন clause-এ বর্তমান level-এর ঠিক একটি literal বাকি। সেই literal-এর চলককে বলে first UIP (unique implication point), আর ফলাফলটি শেখা clause.
1C1 = ¬x1 ∨ x42C2 = ¬x3 ∨ x53C3 = ¬x5 ∨ ¬x2 ∨ x64C4 = ¬x6 ∨ x75C5 = ¬x6 ∨ ¬x4 ∨ x86C6 = ¬x7 ∨ ¬x87শেখা: ¬x6 ∨ ¬x4
| হাতের clause | |
| level ৩-এর literal | |
| level |
- বাধ্য মান ছড়ানো। Level ১-এ x1 = 1, আর C1 থেকে x4 = 1. Level ২-এ x2 = 1, কিছু বাধ্য হয় না। Level ৩-এ x3 = 1, তারপর C2 থেকে x5, C3 থেকে x6 (x5 আর x2 মিলে), C4 থেকে x7, C5 থেকে x8 (x6 আর x4 মিলে)।
- বিরোধ। C6 = ¬x7 ∨ ¬x8-এর দুটি literal-ই মিথ্যা। হাতের clause এখন C6; এতে level ৩-এর দুটি literal, তাই থামা যায় না।
- প্রথম resolution ধাপ। সবার শেষে বসেছিল x8, কারণ C5. C6 আর C5-কে x8-এ resolve করলে (¬x7 ∨ ¬x6 ∨ ¬x4). Level ৩-এর literal এখনো দুটি: x7 আর x6.
- দ্বিতীয় resolution ধাপ। এবার x7, কারণ C4. Resolve করলে (¬x6 ∨ ¬x4). Level ৩-এর literal মাত্র একটি, ¬x6: x6 হলো first UIP. এটিই শেখা clause.
- পেছনে লাফ। শেখা clause-এর বাকি literal ¬x4-এর level ১. Solver level ২ আর ৩ মুছে level ১-এ ফেরে; সেখানে x4 = 1, তাই শেখা clause unit হয়ে x6 = 0 বাধ্য করে। Level ২-এর অনুমান x2 বিরোধের অংশ ছিল না বলে বাদ পড়ল।
শেষ ধাপকে বলে backjumping বা non-chronological backtracking: DPLL এক ধাপ পিছিয়ে x3 উল্টাত, আর x2-এর দুই মানে একই বিরোধ আবার খুঁজত। শেখা clause এর সমাধান করে, কারণ এখন থেকে x4 সত্য হলেই x6 সঙ্গে সঙ্গে মিথ্যা হবে।
CDCL-এর প্রতিটি শেখা clause L মূল সূত্র φ আর আগে শেখা clause-গুলো থেকে resolution-এর ধাপে পাওয়া যায়। তাই φ ⊨ L, আর L যোগ করলে φ-এর model-এর সেট বদলায় না। Solver “UNSAT” বললে তার শেখা clause-গুলো, শেষে ফাঁকা clause পর্যন্ত, φ-এর একটি resolution refutation.
প্রমাণ:
- বিশ্লেষণ শুরু হয় বিরোধী clause দিয়ে, যা φ বা আগে শেখা clause-এর অংশ। — শুরুর বিন্দু
- প্রতিটি ধাপে হাতের clause D-তে একটি literal ¬ℓ আছে, যেখানে ℓ বাধ্য হয়েছিল কারণ-clause R দিয়ে, আর R-এ ℓ আছে। তাই D আর R ℓ-এর চলকে বিপরীত চিহ্নে আছে, আর resolvent বৈধ। R নিজে φ বা আগে শেখা clause. — কারণ-clause-এর সংজ্ঞা
- Resolution sound: (x ∨ A) আর (¬x ∨ B) সত্য হলে (A ∨ B) সত্য। Induction-এ প্রতিটি মধ্যবর্তী clause, আর শেষে L, φ-এর প্রতিটি model-এ সত্য। — পর্ব ৬২
- প্রতিটি ধাপ trail-এর একটি আলাদা literal সরায়, তাই একটি বিরোধে বড়জোর n-টি resolution ধাপ। Level ০-তে বিরোধ হলে বিশ্লেষণ ফাঁকা clause পর্যন্ত যায়; শেখা সব clause একসঙ্গে একটি resolution refutation. ∎
নিচের JavaScript ব্লক ঠিক ওপরের ছবি থেকে first UIP বের করে, আর brute force দিয়ে মেলায় যে C1–C6-এর প্রতিটি model শেখা clause-কেও সত্য করে।
// CDCL conflict analysis: resolve back to the first UIP, then backjump
const C = {C1: [-1, 4], C2: [-3, 5], C3: [-5, -2, 6], C4: [-6, 7], C5: [-6, -4, 8], C6: [-7, -8]};
// trail: literal, decision level, reason clause (null = decision), in order
const trail = [[1, 1, null], [4, 1, "C1"], [2, 2, null], [3, 3, null],
[5, 3, "C2"], [6, 3, "C3"], [7, 3, "C4"], [8, 3, "C5"]];
const info = {}; trail.forEach(([l, d, r], i) => info[Math.abs(l)] = {d, r, i});
const show = c => "(" + c.map(l => (l < 0 ? "¬x" : "x") + Math.abs(l)).join(" ∨ ") + ")";
const atLevel = (c, d) => c.filter(l => info[Math.abs(l)].d === d);
let clause = C.C6, cur = 3;
console.log("conflict: C6 = " + show(clause) + " is false at level " + cur);
while (atLevel(clause, cur).length > 1) {
// the literal of the current level that was assigned last
const last = atLevel(clause, cur).sort((a, b) => info[Math.abs(b)].i - info[Math.abs(a)].i)[0];
const v = Math.abs(last), reason = C[info[v].r];
clause = [...new Set([...clause, ...reason].filter(l => Math.abs(l) !== v))];
console.log(`resolve on x${v} with ${info[v].r} ${show(reason)} -> ${show(clause)}`);
}
const levels = clause.map(l => info[Math.abs(l)].d).sort((a, b) => b - a);
const back = levels.length > 1 ? levels[1] : 0;
console.log("learned clause " + show(clause) + ": one literal of level 3 (first UIP)");
console.log(`backjump from level 3 to level ${back}; there the clause forces x6 = 0`);
// brute force: every model of C1..C6 also satisfies the learned clause
let models = 0, ok = true;
for (let m = 0; m < 256; m++) {
const val = l => ((m >> (Math.abs(l) - 1)) & 1) === (l > 0 ? 1 : 0);
if (Object.values(C).every(c => c.some(val))) { models++; ok = ok && clause.some(val); }
}
console.log(`models of C1..C6: ${models}; all satisfy the learned clause: ${ok}`);আসল আউটপুট (ব্রাউজারের JavaScript):
conflict: C6 = (¬x7 ∨ ¬x8) is false at level 3
resolve on x8 with C5 (¬x6 ∨ ¬x4 ∨ x8) -> (¬x7 ∨ ¬x6 ∨ ¬x4)
resolve on x7 with C4 (¬x6 ∨ x7) -> (¬x6 ∨ ¬x4)
learned clause (¬x6 ∨ ¬x4): one literal of level 3 (first UIP)
backjump from level 3 to level 1; there the clause forces x6 = 0
models of C1..C6: 42; all satisfy the learned clause: true
দুটি resolution, stepper-এর ধাপ ৩ আর ৪-এর সঙ্গে হুবহু। ৮টি চলকের ২৫৬টি মানের মধ্যে ৪২টি C1–C6-কে সত্য করে, আর ৪২টিই শেখা clause-কেও সত্য করে: উপপাদ্য ৩.১-এর φ ⊨ L, এই ছোট ক্ষেত্রে গুনে দেখা।
শিল্পমানের solver-এ আরও তিনটি কৌশল থাকে, যাদের নাম জানা দরকার। VSIDS (Chaff থেকে আসা নাম): সাম্প্রতিক বিরোধে যেসব চলক বেশি এসেছে, তাদের ওপর আগে অনুমান। Watched literals: প্রতিটি clause-এর মাত্র দুটি literal “পাহারায়” রাখা, যাতে unit propagation-এ সব clause ঘাঁটতে না হয়। আর restart: কিছু বিরোধের পর সব অনুমান মুছে শুরু, কিন্তু শেখা clause রেখে। Carla Gomes আর সহকর্মীরা ১৯৯০-এর দশকের শেষে দেখান যে একই সূত্রে ছোট এলোমেলো পরিবর্তনেই সময় বিশাল ওঠানামা করতে পারে (heavy-tailed আচরণ), আর restart সেই লম্বা লেজ কাটে। অংশ ৪-এর সত্যিকারের run-এ এর একটি ঝলক দেখবেন।
৪ · সমস্যাকে CNF-এ লেখা — at-most-one, symmetry আর সবচেয়ে কম slot
Solver কতটা দ্রুত চলবে, তার বড় অংশ ঠিক হয় encoding-এ। বাজারঘরের slot সমস্যা: n-টি অর্ডার, m-টি বিরোধী জোড়া, k-টি slot. চলক xv,c = “অর্ডার v slot c-তে”। প্রতিটি অর্ডারের জন্য “অন্তত একটি slot”, “বড়জোর একটি slot”, আর প্রতিটি বিরোধ ও প্রতিটি slot-এর জন্য “দুজন একই slot-এ নয়”। এটি graph colouring-এর encoding; পর্ব ৬১ এটিকে ১০টি অর্ডারে চালিয়েছিল, এখানে আমরা encoding-এর বিকল্প আর দাম মাপব।
1চলক: A1, A2, A32A1 ∨ A2 ∨ A33¬A1 ∨ ¬A24¬A1 ∨ ¬A35¬A2 ∨ ¬A36¬Ac ∨ ¬Bc, c = 1, 2, 3
| এই অংশ | |
| clause | |
| উদাহরণ |
- চলক। অর্ডার A-এর জন্য তিনটি Boolean চলক: A1, A2, A3. A2 = 1 মানে A দ্বিতীয় slot-এ যাবে। n-টি অর্ডারে মোট n·k চলক।
- অন্তত একটি। একটি clause: A1 ∨ A2 ∨ A3. প্রতিটি অর্ডারে একটি, মোট n-টি।
- বড়জোর একটি, জোড়ায় জোড়ায়। প্রতিটি slot-জোড়ার জন্য “দুটি একসঙ্গে সত্য নয়”: k = 3-এ তিনটি clause. সাধারণভাবে প্রতিটি অর্ডারে k(k − 1)/2.
- বিরোধ। A আর B একই রাইডার চায়, তাই প্রতিটি slot c-এর জন্য ¬Ac ∨ ¬Bc: প্রতি বিরোধে k-টি clause.
- মোট। n + n·k(k − 1)/2 + m·k. পর্ব ৬১-এর ১০টি অর্ডার, ১৫টি বিরোধ, k = 3-এ 10 + 30 + 45 = 85; নিচের run-এর ৫০টি অর্ডার, ৩৭৭টি বিরোধ, k = 6-এ 50 + 750 + 2262 = 3062.
Pairwise at-most-one encoding k বাড়লে বর্গে বাড়ে। বিকল্প হলো Carsten Sinz-এর (২০০৫) sequential counter: নতুন চলক si = “x1, …, xi-এর কোনোটি সত্য”, আর clause (¬x1 ∨ s1); 1 < i < k-এর জন্য (¬xi ∨ si), (¬si−1 ∨ si), (¬xi ∨ ¬si−1); শেষে (¬xk ∨ ¬sk−1). মোট 3k − 4টি clause আর k − 1টি নতুন চলক। এটি Tseitin-এর মতোই (পর্ব ৬০): নতুন চলক মূল শর্তের সঙ্গে equisatisfiable, আর x-এর ওপর প্রক্ষেপ হুবহু “বড়জোর একটি”। প্রমাণের মূল: xi আর xj (i < j) দুটিই সত্য হলে si, si+1, …, sj−1 বাধ্যভাবে সত্য, আর (¬xj ∨ ¬sj−1) মিথ্যা হয়; উল্টো দিকে কোনো x সত্য না হলে সব s মিথ্যা, আর একটি xi সত্য হলে sj = [j ≥ i] সব clause সত্য করে। নিচের ব্লক দাবিটি k ≤ 6-এ brute force দিয়ে মেলায়।
# "At most one slot" in CNF: pairwise vs sequential counter, checked by brute force
from itertools import combinations, product
def amo_pairwise(xs, top):
return [[-a, -b] for a, b in combinations(xs, 2)], top
def amo_seq(xs, top): # s_i = "some x_1..x_i is true"
k = len(xs); s = list(range(top + 1, top + k)); top += k - 1
cl = [[-xs[0], s[0]]]
for i in range(1, k - 1):
cl += [[-xs[i], s[i]], [-s[i - 1], s[i]], [-xs[i], -s[i - 1]]]
cl.append([-xs[k - 1], -s[k - 2]])
return cl, top
def sat(cl, val): # val: dict var -> bool
return all(any(val[abs(l)] == (l > 0) for l in c) for c in cl)
def projections(cl, top, k): # x-patterns that extend to a model
pats = set()
for bits in product((False, True), repeat=top):
val = dict(enumerate(bits, 1))
if sat(cl, val):
pats.add(bits[:k])
return pats
for k in (2, 3, 4, 5, 6):
xs = list(range(1, k + 1))
want = {b for b in product((False, True), repeat=k) if sum(b) <= 1}
ok = all(projections(*enc(xs, k), k) == want for enc in (amo_pairwise, amo_seq))
print(f"k={k}: both encodings allow exactly the {len(want)} patterns with <= 1 true: {ok}")
print(" k pairwise clauses seq clauses seq extra vars")
for k in (3, 6, 20, 100):
xs = list(range(1, k + 1))
print(f"{k:3} {len(amo_pairwise(xs, k)[0]):18} {len(amo_seq(xs, k)[0]):13} {amo_seq(xs, k)[1] - k:15}")আসল আউটপুট (ব্রাউজারের Python):
k=2: both encodings allow exactly the 3 patterns with <= 1 true: True
k=3: both encodings allow exactly the 4 patterns with <= 1 true: True
k=4: both encodings allow exactly the 5 patterns with <= 1 true: True
k=5: both encodings allow exactly the 6 patterns with <= 1 true: True
k=6: both encodings allow exactly the 7 patterns with <= 1 true: True
k pairwise clauses seq clauses seq extra vars
3 3 5 2
6 15 14 5
20 190 56 19
100 4950 296 99
দুটি encoding প্রতিটি k-তে ঠিক k + 1টি x-বিন্যাস অনুমোদন করে (সব মিথ্যা, বা ঠিক একটি সত্য)। আকারে k = 3-এ pairwise ছোট (৩ বনাম ৫), k = 6-এ প্রায় সমান (১৫ বনাম ১৪), কিন্তু k = 100-এ ৪,৯৫০ বনাম ২৯৬. তাই ছোট k-এ সরল pairwise প্রায়ই যথেষ্ট; শতাধিক বিকল্পে cardinality constraint-এর counter-ধাঁচের encoding লাগে।
সত্যিকারের run: সবচেয়ে কম কয়টি slot? এটি একটি optimization problem: chromatic number χ(G) খোঁজা। SAT solver decision প্রশ্নের উত্তর দেয়, তাই k কমিয়ে কমিয়ে জিজ্ঞেস করা হয়: k-তে SAT আর k − 1-এ UNSAT হলে χ = k, আর UNSAT উত্তরটিই সর্বোত্তমতার প্রমাণ। uv দিয়ে বানানো একটি ছোট প্রকল্পে python-sat 1.9.dev23 (PySAT, MIT licence; ভেতরের CaDiCaL 1.9.5 solver-ও MIT) আর networkx 3.7 (BSD-3-Clause), Python 3.12.13. দুটির installed source-এ network বা usage-reporting কোড খুঁজে পাওয়া যায়নি। ৫০টি অর্ডার, প্রতিটি জোড়া ০.৩ সম্ভাবনায় বিরোধী (seed স্থির); তুলনার জন্য networkx-এর greedy heuristic আর একটি সবচেয়ে বড় clique (যার প্রতিটি সদস্যকে আলাদা slot দিতেই হয়, তাই এটি নিচের সীমা)।
def color_cnf(G, k, amo, clique=()):
pool = IDPool(); x = lambda v, c: pool.id(("x", v, c))
cls = []
for v in G:
lits = [x(v, c) for c in range(k)]
cls.append(lits) # at least one slot
if amo == "pairwise":
cls += [[-a, -b] for i, a in enumerate(lits) for b in lits[i + 1:]]
else: # sequential counter
cls += CardEnc.atmost(lits, bound=1, vpool=pool,
encoding=EncType.seqcounter).clauses
for u, v in G.edges:
cls += [[-x(u, c), -x(v, c)] for c in range(k)] # conflicting orders
for i, v in enumerate(clique): # symmetry breaking
cls.append([x(v, i)])
return cls, pool.top, x
# solve(): Solver(name="cadical195"), decode the model, check every edge
# main: greedy = nx.greedy_color(G, "largest_first"); clique = max(nx.find_cliques(G))
# for k = greedy-1 down: solve until UNSATসত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev23 / CaDiCaL 1.9.5, networkx 3.7, Python 3.12.13):
~/bazarghar-toc$ uv run python slots.py
python 3.12.13 | python-sat 1.9.dev23 | networkx 3.7 | solver cadical195
orders 50, conflicts 377
greedy heuristic (largest_first): 9 slots
a largest clique: [3, 43, 45, 46, 49] -> lower bound 5
pairwise k=8: vars 400 clauses 4466 SAT conflicts 0 0.00s verified True
pairwise k=7: vars 350 clauses 3739 SAT conflicts 3 0.00s verified True
pairwise k=6: vars 300 clauses 3062 UNSAT conflicts 284342 5.29s
seqcounter k=8: vars 750 clauses 4066 SAT conflicts 0 0.00s verified True
seqcounter k=7: vars 650 clauses 3539 SAT conflicts 3 0.00s verified True
seqcounter k=6: vars 550 clauses 3012 UNSAT conflicts 328085 6.40s
pairwise + clique fixed, k=6: UNSAT conflicts 634 0.00s
plan with 7 slots, orders per slot: [8, 8, 8, 6, 6, 6, 8] | every conflict in different slots: True
Greedy ৯টি slot দিয়েছে, clique বলছে অন্তত ৫টি লাগবে। Solver ৭-এ একটি পরিকল্পনা পেয়েছে (৩টি বিরোধে), যা আমাদের নিজের check-এ বৈধ। আসল কাজ k = 6-এ: “৬টিতে অসম্ভব” প্রমাণে ২,৮৪,৩৪২টি বিরোধ আর পাঁচ সেকেন্ডের বেশি লেগেছে। তাই χ = 7: greedy-র চেয়ে দুটি কম, আর clique-সীমার চেয়ে দুটি বেশি। দুই encoding-এর পার্থক্য এখানে ছোট, কারণ k = 6-এ clause-সংখ্যা প্রায় সমান। নাটকীয় পার্থক্য দিয়েছে symmetry breaking: slot-এর নাম অদলবদল করলে প্রতিটি সমাধান থেকে 6! = ৭২০টি সমতুল্য সমাধান আসে, আর solver প্রতিটি অসম্ভব বিন্যাস বারবার বাতিল করে। Clique-এর পাঁচটি অর্ডারকে slot 1–5-এ বেঁধে দিলে (কোনো সমাধান হারায় না, কারণ যেকোনো সমাধানের slot-নাম বদলে এই রূপে আনা যায়) বিরোধ ৬৩৪-এ নেমেছে। একই CNF আরেকটি সত্যিকারের run-এ MiniSat আর Glucose solver-এও UNSAT এসেছে; তবে PySAT-এর MiniSat দুইবার চালাতে বিরোধ-সংখ্যা ৫,০৪,৬২৩ আর ৮,৩৪,৮১৬, অর্থাৎ run থেকে run-এ বদলেছে। এ কারণে এই পর্বের সব সংখ্যা CaDiCaL-এ, যা দুইবার চালিয়ে একই সংখ্যা দিয়েছে।
৫ · Random 3SAT আর phase transition — কী প্রমাণিত, কী পর্যবেক্ষণ
পর্ব ৬৩-এ দেখেছেন, m = 4.26n-এ random 3SAT-এ n বাড়লে solver-এর কাজ সূচকীয়ের মতো বাড়ে। এবার n স্থির রেখে অনুপাত α = m/n বদলাই। প্রতিটি clause-এ তিনটি আলাদা চলক এলোমেলো বাছা হয়, প্রতিটির চিহ্ন এলোমেলো। α ছোট হলে প্রায় সব সূত্র satisfiable, বড় হলে প্রায় কোনোটিই নয়। প্রশ্ন: পতনটি কোথায়, আর কতটা তীক্ষ্ণ?
α > ln 2 / ln(8/7) ≈ 5.19 হলে, n → ∞-এ m = αn clause-এর random 3CNF satisfiable হওয়ার সম্ভাবনা → 0.
প্রমাণ (first moment method):
- একটি নির্দিষ্ট মান-বসানো a নিন। একটি random clause a-তে মিথ্যা শুধু যদি তিনটি literal-ই মিথ্যা হয়: সম্ভাবনা (1/2)3 = 1/8. Clause-গুলো স্বাধীনভাবে বাছা, তাই P(a model) = (7/8)m. — স্বাধীনতা
- X = model-এর সংখ্যা। Linearity of expectation: E[X] = 2n · (7/8)αn = (2 · (7/8)α)n. — 2nটি মান
- α > ln 2 / ln(8/7) হলে 2 · (7/8)α < 1, তাই E[X] → 0. — বীজগণিত
- Markov-এর অসমতা: P(φ satisfiable) = P(X ≥ 1) ≤ E[X] → 0. ∎
আসল সীমা এর চেয়ে অনেক নিচে, কারণ E[X] একটি “লটারি” প্রভাবে ফুলে থাকে: অল্প কিছু সূত্রে বিপুল সংখ্যক model, বাকিগুলোতে শূন্য। যা জানা (উৎসভেদে সংখ্যায় সামান্য পার্থক্য থাকতে পারে): Ehud Friedgut ১৯৯৯ সালে প্রমাণ করেন পতনটি তীক্ষ্ণ (যদিও অবস্থান n-এর ওপর নির্ভর করতে পারে, এমন রূপে); k = 3-এর জন্য প্রমাণিত নিচের সীমা প্রায় ৩.৫২ আর ওপরের সীমা প্রায় ৪.৪৯; পরিসংখ্যান-পদার্থবিদ্যার হিসাব (Mézard, Parisi, Zecchina, ২০০২) অবস্থান প্রায় ৪.২৬৭ বলে অনুমান করে; আর বড় k-এর জন্য সঠিক সীমা Jian Ding, Allan Sly আর Nike Sun ২০১৫ সালে প্রমাণ করেন। k = 3-এর সঠিক মান এখনো প্রমাণিত নয়। এটিই phase transition.
সত্যিকারের run. একই প্রকল্পে প্রতিটি (α, n)-এ ৪০টি সূত্র (seed স্থির), CaDiCaL; প্রতিটি পাওয়া model আমাদের verifier দিয়ে মেলানো।
সত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev23 / CaDiCaL 1.9.5, Python 3.12.13; মোট প্রায় ২৯ সেকেন্ড):
~/bazarghar-toc$ uv run python phase.py
python 3.12.13 | python-sat 1.9.dev23 | solver cadical195
ratio n=50: SAT% med.confl n=100: SAT% med.confl n=200: SAT% med.confl
3.0 100.0% 1 100.0% 3 100.0% 4
3.5 100.0% 4 100.0% 28 100.0% 120
3.8 97.5% 19 100.0% 75 100.0% 605
4.0 90.0% 26 95.0% 86 97.5% 1810
4.2 52.5% 59 62.5% 332 65.0% 11067
4.4 60.0% 42 32.5% 580 22.5% 16278
4.6 17.5% 64 7.5% 478 0.0% 12999
5.0 7.5% 52 0.0% 368 0.0% 8164
5.5 7.5% 41 0.0% 246 0.0% 4420
6.0 0.0% 38 0.0% 174 0.0% 2419
all models verified; 40 formulas per cell; total 29.3s
তিনটি জিনিস চোখে পড়ে। (১) SAT-এর ভাগ ৪.০ আর ৪.৬-এর মধ্যে পড়ে যায়, আর n বাড়লে পতন খাড়া হয়: ৪.৪-এ n = 50-এ ৬০%, n = 200-এ ২২.৫%; ৪.৬-এ n = 200-এ শূন্য। (২) Solver-এর কাজ (median conflict) পতনের জায়গায় সবচেয়ে বেশি: n = 200-এ ৪.৪-এ ১৬,২৭৮, অথচ ৩.০-এ মাত্র ৪ আর ৬.০-এ ২,৪১৯. কম α-এ model প্রচুর, সহজে মেলে; বেশি α-এ বিরোধ এত দ্রুত আসে যে UNSAT-এর প্রমাণ ছোট। (৩) ৫.১৯-এর নিচেই সব সূত্র UNSAT হয়ে গেছে, যা উপপাদ্য ৫.১-এর সঙ্গে সংগত কিন্তু তার চেয়ে অনেক শক্ত পর্যবেক্ষণ। সাবধান: ৪০টি নমুনা আর ছোট n থেকে threshold-এর অবস্থান “মাপা” যায় না; ছোট n-এ পতন ঝাপসা (n = 50-এ ৪.২-এ ৫২.৫% অথচ ৪.৪-এ ৬০%), যা নমুনার ওঠানামা।
৬ · যেখানে CDCL আটকে যায় — pigeonhole আর resolution-এর দেয়াল
উপপাদ্য ৩.১ একটি শক্তিশালী নেতিবাচক ফলের দরজা খোলে। Pigeonhole formula PHP(n + 1, n): n + 1টি পার্সেল, n-টি slot, প্রতিটি পার্সেল কোনো slot পায়, কোনো slot-এ দুটি নয়। এটি unsatisfiable, আর Armin Haken ১৯৮৫ সালে প্রমাণ করেন এর প্রতিটি resolution refutation n-এর সূচকীয় আকারের (পর্ব ৬২-এ এই সূত্রে solver-এর প্রমাণ-লগের বৃদ্ধি দেখেছেন)।
যেকোনো CDCL solver, যেকোনো branching heuristic, restart আর clause-মোছার নীতি নিয়ে, PHP(n + 1, n)-এ UNSAT উত্তর দিতে 2Ω(n)/n-এর কম বিরোধে পারে না (Haken-এর সীমার সঠিক ধ্রুবক বাদ রেখে)।
প্রমাণ: উপপাদ্য ৩.১ অনুযায়ী solver-এর পুরো run থেকে একটি resolution refutation পাওয়া যায়, যার ধাপ-সংখ্যা ≤ (বিরোধ-সংখ্যা) × n, কারণ প্রতিটি বিরোধে বড়জোর n-টি resolution ধাপ। Haken-এর ফল অনুযায়ী যেকোনো refutation-এ অন্তত 2Ω(n) ধাপ। তাই বিরোধ-সংখ্যা ≥ 2Ω(n)/n. ∎ (Preprocessing-এ resolution-এর চেয়ে শক্তিশালী যুক্তি, যেমন cardinality বা symmetry চেনা, যোগ করলে এই সীমা আর খাটে না।)
মানুষ এক লাইনে যুক্তি দেয়: “n + 1 > n”. Resolution গুনতে পারে না, কিন্তু linear অসমতা পারে। প্রতিটি পার্সেলের সারি যোগ করলে ∑ xp,h ≥ n + 1, আর প্রতিটি slot-এর কলাম যোগ করলে একই যোগফল ≤ n. পূর্ণসংখ্যার দরকারই নেই: ভগ্নাংশ মানেও এটি অসম্ভব। তাই একটি ILP solver-এর LP relaxation (অংশ ৭) এটিকে সঙ্গে সঙ্গে বাতিল করার কথা। একে প্রমাণ-তত্ত্বে বলে cutting planes-এর শক্তি; William Cook, Collette Coullard আর György Turán ১৯৮৭ সালে দেখান pigeonhole-এর polynomial আকারের cutting-plane প্রমাণ আছে (proof complexity-র একটি মৌলিক ফল)।
def php_ilp(n): # n+1 parcels, n slots, 0-1 variables
prob = pulp.LpProblem("php", pulp.LpMinimize)
x = {(p, h): pulp.LpVariable(f"x_{p}_{h}", cat="Binary")
for p in range(n + 1) for h in range(n)}
prob += pulp.lpSum([]) # feasibility only
for p in range(n + 1):
prob += pulp.lpSum(x[p, h] for h in range(n)) >= 1 # a slot for each
for h in range(n):
prob += pulp.lpSum(x[p, h] for p in range(n + 1)) <= 1 # one per slot
return prob
# for n in 6..10: php_cnf(n) -> Solver("cadical195"); php_ilp(n) -> PULP_CBC_CMD(threads=1)সত্যিকারের run (ডেস্কটপ, CaDiCaL 1.9.5 via python-sat 1.9.dev23; PuLP 3.3.2, MIT licence, যার সঙ্গে আসা CBC 2.10.3 solver-এর licence Eclipse Public License 1.0; PuLP-এর source-এ network কোড নেই, আর CBC একটি স্থানীয় প্রোগ্রাম হিসেবে চলে):
~/bazarghar-toc$ uv run python php_ilp.py
python 3.12.13 | python-sat 1.9.dev23 | pulp 3.3.2 | CBC 2.10.3
n= 6: SAT UNSAT 1044 conflicts 0.00s | ILP Infeasible nodes - 0.01s
n= 7: SAT UNSAT 7130 conflicts 0.03s | ILP Infeasible nodes - 0.01s
n= 8: SAT UNSAT 31719 conflicts 0.20s | ILP Infeasible nodes - 0.01s
n= 9: SAT UNSAT 267023 conflicts 2.49s | ILP Infeasible nodes - 0.01s
n=10: SAT UNSAT 2227032 conflicts 25.39s | ILP Infeasible nodes - 0.01s
CBC log (n=10): Problem is infeasible - 0.00 seconds
CDCL-এর বিরোধ প্রতি ধাপে প্রায় ৪ থেকে সাড়ে ৮ গুণ বেড়েছে: ১,০৪৪ থেকে ২২ লাখের বেশি, আর n = 10-এ ২৫ সেকেন্ড (একটি আগের চেষ্টায় n = 11 কয়েক মিনিটেও শেষ না হওয়ায় থামানো হয়েছিল)। CBC প্রতিটি ক্ষেত্রে ০.০১ সেকেন্ডে “Infeasible” বলেছে, আর তার log দেখায় সমস্যাটি পড়ার পরই প্রাথমিক LP ধাপে বাতিল হয়েছে, কোনো branch and bound ছাড়াই (তাই nodes-এর ঘরে কিছু নেই)। এর মানে এই নয় যে ILP SAT-এর চেয়ে সবসময় ভালো: অনেক সূত্রে উল্টোটা সত্য, আর cutting planes-এরও প্রমাণিত সূচকীয় নিম্নসীমা আছে। শিক্ষা হলো, প্রতিটি পদ্ধতির ভেতরে একটি প্রমাণ-পদ্ধতি লুকিয়ে আছে, আর তার দুর্বলতাই solver-এর দুর্বলতা।
৭ · ILP — linear শর্তে NP-hard সমস্যা
Integer linear program (ILP): চলক x ∈ ℤn, শর্ত Ax ≤ b, লক্ষ্য c·x সর্বনিম্ন। পূর্ণসংখ্যার শর্ত তুলে দিলে linear programming (LP), যা polynomial সময়ে সমাধানযোগ্য (Leonid Khachiyan ১৯৭৯, ellipsoid পদ্ধতি)। পূর্ণসংখ্যার শর্তটিই সব কঠিনতা আনে: 0-1 integer programming Karp-এর ১৯৭২ সালের ২১টি NP-complete সমস্যার একটি।
“এই 0-1 linear অসমতাগুলোর একটি সমাধান আছে কি?” (0-1 ILP feasibility) NP-complete.
প্রমাণ:
- NP-তে: certificate একটি 0-1 ভেক্টর; প্রতিটি অসমতা মেলানো polynomial সময়ের। — verifier
- 3SAT ≤p 0-1 ILP: প্রতিটি চলক xi-এর জন্য একটি 0-1 চলক, আর প্রতিটি clause-এর জন্য একটি অসমতা, যেখানে literal xi-এর জায়গায় xi আর ¬xi-এর জায়গায় (1 − xi): যেমন (x1 ∨ ¬x2 ∨ x3) ↦ x1 + (1 − x2) + x3 ≥ 1. আকার রৈখিক। — polynomial রূপান্তর
- ⇔: 0-1 মানে প্রতিটি literal-পদের মান ১ ঠিক যখন literal সত্য; তাই অসমতাটি সত্য ⇔ clause-এ অন্তত একটি literal সত্য। একটি satisfying assignment ঠিক একটি feasible 0-1 ভেক্টর, আর উল্টোটাও। — দুই দিক
- 3SAT NP-complete আর ≤p ক্রমসংক্রামী, তাই 0-1 ILP NP-hard; ধাপ ১ মিলিয়ে NP-complete. ∎
সাধারণ (অসীম-পরিসরের) পূর্ণসংখ্যা চলকে ILP NP-তে আছে কি না, তা সহজ নয়, কারণ সমাধানের সংখ্যাগুলো বিশাল হতে পারে; ছোট সমাধানের অস্তিত্বের প্রমাণ Borosh–Treybig আর Papadimitriou-র কাজে (১৯৭০–৮০-এর দশক) পাওয়া যায় বলে সাধারণত উল্লেখ করা হয়। আর চলকের সংখ্যা স্থির থাকলে ILP polynomial সময়ে সমাধানযোগ্য (Hendrik Lenstra, ১৯৮৩)।
ILP solver-এর কৌশল: LP relaxation সমাধান করে একটি নিম্নসীমা পাওয়া (minimisation-এ relaxation-এর মান ≤ আসল সর্বনিম্ন); সমাধানে কোনো চলক ভগ্নাংশ হলে তার ওপর দুই শাখা (≤ ⌊মান⌋ আর ≥ ⌈মান⌉), এটিই branch and bound; আর cutting plane যোগ করে relaxation-কে আঁটসাঁট করা। আসল সর্বনিম্ন আর relaxation-এর মানের ফারাককে বলে integrality gap.
সত্যিকারের run: তিন রাইডারে আট অর্ডার। প্রতিটি অর্ডার ঠিক একজন রাইডারকে; রাইডার r অর্ডার o নিলে যাত্রায় cr,o মিনিট আর তাঁর সময়ের tr,o মিনিট খরচ; প্রত্যেকের এই slot-এ সময়ের সীমা (৭০, ৬০, ৮০ মিনিট)। লক্ষ্য মোট যাত্রার মিনিট সবচেয়ে কম। এটি generalized assignment problem, যা NP-hard. সব সংখ্যা বানানো।
def build(relax=False):
prob = pulp.LpProblem("riders", pulp.LpMinimize)
cat = "Continuous" if relax else "Binary"
x = {(r, o): pulp.LpVariable(f"x_{r}_{o}", 0, 1, cat=cat) for r in R for o in O}
prob += pulp.lpSum(cost[r][o] * x[r, o] for r in R for o in O)
for o in O: # every order exactly one rider
prob += pulp.lpSum(x[r, o] for r in R) == 1
for r in R: # rider time limit
prob += pulp.lpSum(load[r][o] * x[r, o] for o in O) <= cap[r]
return prob, x
# then: greedy check, LP relaxation, ILP with CBC, brute force over 3^8সত্যিকারের run (ডেস্কটপ, PuLP 3.3.2 / CBC 2.10.3, Python 3.12.13):
~/bazarghar-toc$ uv run python riders.py
python 3.12.13 | pulp 3.3.2 | CBC 2.10.3 (bundled)
greedy (cheapest rider each): 109 min, loads {'R1': 67, 'R2': 65, 'R3': 40} feasible: False
LP relaxation : Optimal, objective 110.52 min, 0.01s
fractional variables: [('R2', 'Badda', 0.783), ('R3', 'Badda', 0.217)]
ILP (CBC) : Optimal, objective 116.00 min, 0.01s
plan: {'R1': ['Mirpur', 'Dhanmondi', 'Mohammadpur'], 'R2': ['Uttara', 'Gulshan'], 'R3': ['Motijheel', 'Badda', 'Jatrabari']}
brute force: 6561 assignments, 4 feasible, best 116 min (0.01s) | agrees with CBC: True
প্রতিটি অর্ডার তার সবচেয়ে সস্তা রাইডারকে দেওয়ার greedy-তে মোট ১০৯ মিনিট, কিন্তু R2-এর সময় ৬৫, সীমা ৬০: অবৈধ। LP relaxation ১১০.৫২ দিয়েছে, যেখানে বাড্ডার অর্ডারটি ৭৮.৩% R2 আর ২১.৭% R3-কে, যা বাস্তবে অর্থহীন; কিন্তু এটি একটি প্রমাণিত নিম্নসীমা। CBC-র পূর্ণসংখ্যা সমাধান ১১৬ মিনিট: বাড্ডা পুরোটা R3-কে। Integrality gap ১১৬ − ১১০.৫২ = ৫.৪৮ মিনিট। স্বাধীন brute force ৩৮ = ৬,৫৬১টি বণ্টনের সবগুলো দেখে শুধু ৪টি বৈধ পেয়েছে, আর সেরাটি ১১৬: CBC-র উত্তর সর্বোত্তম, যাচাই করা।
কখন SAT, কখন ILP? মোটা দাগে: শর্তগুলো যৌক্তিক আর সংযোগে ভরা (যদি-তাহলে, সব-আলাদা, হার্ডওয়্যার সার্কিট) হলে SAT; সংখ্যা, যোগফল, ধারণক্ষমতা আর খরচ বেশি হলে ILP. মাঝামাঝি আছে SMT solver (Boolean যুক্তি + গাণিতিক theory; DPLL(T) কাঠামো ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭-এ) আর MaxSAT ও pseudo-Boolean solver. চূড়ান্ত বিচারক আপনার নিজের instance-এ পরীক্ষা।
৮ · Local search — WalkSAT আর Schöning-এর random walk
সম্পূর্ণ solver খোঁজের গাছ ঘুরে। Local search অন্যভাবে ভাবে: একটি পূর্ণ মান-বসানো দিয়ে শুরু করে বারবার একটি চলক উল্টানো, যাতে মিথ্যা clause কমে। WalkSAT (Bart Selman, Henry Kautz আর Bram Cohen-এর ১৯৯০-এর দশকের কাজে পরিচিত): একটি মিথ্যা clause এলোমেলো বাছা; সম্ভাবনা p-তে তার একটি এলোমেলো চলক উল্টানো (noise), নইলে এমন চলক, যা উল্টালে সবচেয়ে কম সত্য clause মিথ্যা হয়। এটি একটি heuristic: model পেলে তা নিশ্চিত, কিন্তু না পেলে কিছুই প্রমাণ হয় না।
# WalkSAT: random walk + greedy flips; it can find models but never prove UNSAT
import random, statistics
rng = random.Random(73)
def rand3(n, m):
return [[v if rng.random() < 0.5 else -v for v in rng.sample(range(1, n + 1), 3)] for _ in range(m)]
def walksat(cnf, n, max_flips=2000, p=0.5):
a = [None] + [rng.random() < 0.5 for _ in range(n)]
true_lit = lambda l: a[abs(l)] == (l > 0)
occ = {v: [] for v in range(-n, n + 1)}
for c in cnf:
for l in c: occ[l].append(c)
for flips in range(max_flips):
unsat = [c for c in cnf if not any(map(true_lit, c))]
if not unsat: return flips
c = rng.choice(unsat)
def breaks(v): # clauses that become false if v flips
lit = v if a[v] else -v # the literal of v that is now true
return sum(1 for d in occ[lit] if sum(map(true_lit, d)) == 1)
if rng.random() < p: v = abs(rng.choice(c)) # noise move
else: v = min((abs(l) for l in c), key=breaks) # greedy move
a[v] = not a[v]
return None # gave up: SAT or UNSAT unknown
n, T = 40, 12
print(f"n = {n}, {T} formulas per ratio, at most 2000 flips each")
print("ratio solved median flips (solved ones)")
for ratio in (3.0, 3.6, 4.0, 4.26):
res = [walksat(rand3(n, round(ratio * n)), n) for _ in range(T)]
ok = [r for r in res if r is not None]
med = statistics.median(ok) if ok else "-"
print(f"{ratio:5} {len(ok):3}/{T} {med}")আসল আউটপুট (ব্রাউজারের Python):
n = 40, 12 formulas per ratio, at most 2000 flips each
ratio solved median flips (solved ones)
3.0 12/12 32.0
3.6 12/12 97.0
4.0 10/12 158.0
4.26 8/12 69.0
কম অনুপাতে WalkSAT কয়েক ডজন উল্টানোয় model পায়; ৪.০-এর দিকে বেশি লাগে। ব্যর্থ সূত্রগুলো কেমন? Scratch-এ একই ৪৮টি সূত্র CaDiCaL-এ চালিয়ে দেখা গেছে: ৪.০-এর ২টি আর ৪.২৬-এর ৪টি unsatisfiable, আর WalkSAT ঠিক বাকি সব satisfiable সূত্র সমাধান করেছে। কিন্তু WalkSAT নিজে এটা জানতে পারত না: ২,০০০ উল্টানোর পর থামা মানে শুধু “খুঁজে পাইনি”। ৪.২৬-এর median ৪.০-এর চেয়ে কম দেখানো ১২টি নমুনার ওঠানামা, কোনো নিয়ম নয়।
এলোমেলো হাঁটার তত্ত্ব আশ্চর্য রকম পরিষ্কার। Christos Papadimitriou ১৯৯১ সালে দেখান: 2SAT-এ “একটি মিথ্যা clause-এর একটি এলোমেলো চলক উল্টাও” নিয়মটি satisfiable সূত্রে প্রত্যাশিত O(n2) ধাপে model পায়। Uwe Schöning ১৯৯৯ সালে একই ধারণা 3SAT-এ নেন:
Algorithm: এলোমেলো মান দিয়ে শুরু করে 3n বার “একটি মিথ্যা clause-এর তিনটি চলকের একটি এলোমেলো উল্টানো”; পুরোটা প্রায় (4/3)n বার আবার। Satisfiable 3CNF-এ এটি উচ্চ সম্ভাবনায় model পায়, মোট সময় (4/3)n · poly(n).
প্রমাণের রূপরেখা: একটি model a* স্থির ধরুন, আর d = বর্তমান মান আর a*-এর মধ্যে মিলহীন চলকের সংখ্যা। একটি মিথ্যা clause a*-এ সত্য, তাই তার তিনটি চলকের অন্তত একটি a*-এর সঙ্গে মেলে না; এলোমেলো উল্টানোয় অন্তত 1/3 সম্ভাবনায় d এক কমে, বড়জোর 2/3-এ এক বাড়ে। শুরুতে d গড়ে n/2-এর কাছে, আর এই পক্ষপাতদুষ্ট হাঁটা 0-তে পৌঁছানোর সম্ভাবনা হিসাব করলে প্রতি চেষ্টায় সাফল্য অন্তত প্রায় (3/4)n/poly(n). তাই প্রায় (4/3)n চেষ্টাই যথেষ্ট। এটি 2n-এর চেয়ে সূচকীয়ভাবে ভালো, কিন্তু তবু সূচকীয়, আর ETH-এর সঙ্গে সম্পূর্ণ সংগত।
আরও গভীরে: CDCL কি resolution-এর চেয়ে দুর্বল? না: Knot Pipatsrisawat আর Adnan Darwiche (২০০৯ সালের দিকে) আর আলাদাভাবে Albert Atserias, Johannes Fichte ও Marc Thurley (২০১১) দেখান, restart-সহ CDCL সাধারণ resolution-কে polynomial ক্ষতিতে অনুকরণ করতে পারে, অর্থাৎ CDCL আর resolution প্রায় সমান শক্তির। Resolution-এর চেয়ে শক্তিশালী প্রমাণ-পদ্ধতির (extended resolution, cutting planes) ওপর দক্ষ solver বানানো আজও গবেষণার বিষয়। আর UNSAT উত্তর বিশ্বাস করতে আধুনিক solver DRAT-ধাঁচের প্রমাণ-ফাইল লেখে, যা স্বাধীন checker দিয়ে মেলানো যায়; ২০১৬ সালে Boolean Pythagorean triples সমস্যার এমন একটি প্রমাণ শত শত টেরাবাইটের ছিল বলে প্রকাশিত।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন আসে:
- DPLL-এর তিন নিয়ম লিখুন। Unit propagation, pure literal, branching আর backtracking; সঠিক আর সম্পূর্ণ, worst case 2n.
- CDCL DPLL থেকে কোথায় আলাদা? বিরোধ বিশ্লেষণ করে first UIP পর্যন্ত resolve, শেখা clause যোগ, শেখা clause-এর দ্বিতীয় সর্বোচ্চ level-এ backjump, আর restart.
- 3SAT থেকে 0-1 ILP. (x1 ∨ ¬x2 ∨ x3) ↦ x1 + (1 − x2) + x3 ≥ 1.
- Random 3SAT কোথায় কঠিন? α ≈ ৪.২৭-এর কাছে (পর্যবেক্ষণ); প্রমাণিত ঊর্ধ্বসীমা first moment থেকে ৫.১৯.
- কোন সূত্র CDCL-এর জন্য প্রমাণিতভাবে কঠিন? Pigeonhole, কারণ CDCL-এর UNSAT run একটি resolution প্রমাণ আর Haken-এর সূচকীয় সীমা খাটে।
৯ · AI-এর যুগে solver আর encoding
AI assistant এখন সহজেই একটি PySAT বা PuLP মডেল লিখে দেয়, আর সেটি চলেও। বিপদ সেখানেই: ভুল encoding চলে, শুধু ভুল প্রশ্নের উত্তর দেয়। সাধারণ ভুল: “বড়জোর একটি” লিখে “অন্তত একটি” ভুলে যাওয়া (তখন কোনো অর্ডারকেই slot না দিলেও সূত্র সত্য), DIMACS-এ চলক 0 থেকে গোনা, sequential counter-এ একটি clause বাদ দেওয়া, symmetry ভাঙতে গিয়ে আসল সমাধান কেটে ফেলা, solver-এর “UNSAT” দেখে “সমস্যাটি অসম্ভব” বলা অথচ encoding-এ বাড়তি শর্ত ছিল, আর “এই heuristic NP-complete সমস্যাকে polynomial সময়ে সমাধান করে” দাবি করা। তাত্ত্বিক দিকেও: phase transition-এর ৪.২৬-কে “প্রমাণিত” বলা, বা CDCL-কে “resolution-এর চেয়ে সূচকীয়ভাবে শক্তিশালী” বলা।
ভালো ব্যবহার: AI-কে encoding লিখতে দিন, কিন্তু প্রতিটি শর্তের ব্যাখ্যা চান, আর ছোট instance-এ brute force-এর সঙ্গে মেলানোর code নিজে চালান।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১SAT NP-complete, তবু হার্ডওয়্যার যাচাই আর সফটওয়্যার প্যাকেজ মেলানোর মতো কাজে solver লাখো চলকের সূত্র নিয়মিত সমাধান করে। এটি কি P বনাম NP-এর সঙ্গে সাংঘর্ষিক?
না, আর কেন নয়, তা বোঝা এই পর্বের মূল কথা। NP-completeness একটি worst-case দাবি: প্রতিটি algorithm-এর জন্য (P ≠ NP হলে) কিছু কঠিন instance থাকবে। এটি বলে না যে বাস্তবে যেসব instance আসে, সেগুলো কঠিন। বাস্তবের সূত্রে গঠন থাকে: একটি সার্কিটের সূত্র Tseitin encoding থেকে আসে, যেখানে বেশিরভাগ চলক কয়েকটি ইনপুট দিয়ে নির্ধারিত; unit propagation একটি অনুমান থেকে শত শত চলক বাধ্য করে। গবেষকেরা এর ব্যাখ্যায় “backdoor” (অল্প কিছু চলক, যাদের মান ঠিক করলে বাকিটা সহজ) আর “community structure”-এর মতো ধারণা প্রস্তাব করেছেন; এগুলো আংশিক ব্যাখ্যা, পূর্ণ তত্ত্ব নয়।
দ্বিতীয় কারণ প্রকৌশল। ২০০০-এর দশকের শুরু থেকে নিয়মিত SAT Competition হয়, যেখানে শিল্প, random আর হাতে বানানো কঠিন সূত্রের আলাদা ভাগে solver প্রতিযোগিতা করে। Chaff-এর watched literals আর VSIDS, MiniSat-এর ছোট পরিচ্ছন্ন নকশা, আর পরে CaDiCaL ও Kissat-এর মতো solver ধাপে ধাপে উন্নতি এনেছে। কিন্তু একই প্রতিযোগিতার random ভাগে, phase transition-এর কাছে, অল্প কয়েকশো চলকের সূত্রও কঠিন থাকে; আর pigeonhole-ধাঁচের সূত্রে অংশ ৬-এর উপসিদ্ধান্ত প্রমাণ করে যে কোনো CDCL heuristic সাহায্য করবে না।
তাই সঠিক অবস্থান তিন স্তরের: (১) তত্ত্ব: worst case সূচকীয় বলে বিশ্বাস করা হয় (ETH), আর resolution-ভিত্তিক solver-এর জন্য নির্দিষ্ট সূত্রে তা প্রমাণিত; (২) পর্যবেক্ষণ: গঠনযুক্ত বাস্তব instance প্রায়ই দ্রুত মেলে; (৩) কোনো নিশ্চয়তা নেই: কাল নতুন একটি encoding একই solver-কে আটকে দিতে পারে, যেমন অংশ ৪-এ symmetry না ভাঙলে একই প্রশ্নে বিরোধ প্রায় ৪৫০ গুণ বেশি লেগেছে। বাস্তবের solver-সাফল্য P = NP-এর প্রমাণ নয়, আবার NP-completeness solver ব্যবহারের বিরুদ্ধে যুক্তিও নয়।
মূল উপলব্ধি: NP-completeness worst-case-এর কথা বলে, আর solver-এর সাফল্য গঠনযুক্ত সাধারণ instance-এর; দুটি একসঙ্গে সত্য, আর কঠিন সূত্র (random, pigeonhole) এখনো solver-কে আটকে দেয়।
প্র ০২CDCL-এর প্রতিটি UNSAT উত্তর একটি resolution প্রমাণ। তাহলে কি solver-এর ক্ষমতা পুরোপুরি resolution-এর ক্ষমতায় বাঁধা? এর বাইরে যাওয়ার পথ কী?
উপপাদ্য ৩.১ এক দিক দেয়: CDCL resolution-এর চেয়ে শক্তিশালী হতে পারে না, কারণ তার প্রতিটি UNSAT run থেকে প্রায় সমান আকারের resolution refutation বের করা যায়। প্রশ্ন ছিল উল্টো দিক: resolution-এ ছোট প্রমাণ থাকলে CDCL কি তা খুঁজে পায়? DPLL পারে না; DPLL-এর গাছ tree-like resolution-এর সমান, আর কিছু সূত্রে tree-like আর সাধারণ resolution-এর মধ্যে সূচকীয় ফারাক জানা। ২০০৯ সালের দিকে Pipatsrisawat আর Darwiche, আর ২০১১ সালে Atserias, Fichte ও Thurley দেখান, যথেষ্ট restart-সহ CDCL (একটি আদর্শায়িত মডেলে, যেখানে অনুমানের পছন্দ “ভাগ্যবান” হতে পারে) সাধারণ resolution-কে polynomial ক্ষতিতে অনুকরণ করে। অর্থাৎ CDCL আর resolution মোটামুটি সমান শক্তির, আর restart-এর একটি তাত্ত্বিক ভূমিকা স্পষ্ট হয়।
এর বাইরে যেতে হলে শক্তিশালী প্রমাণ-পদ্ধতি লাগে। Cutting planes linear অসমতা যোগ আর ভাগ করে; pigeonhole-এ এর polynomial প্রমাণ আছে (অংশ ৬-এ CBC-র তাৎক্ষণিক উত্তর এই শক্তির ছায়া)। Pseudo-Boolean solver এই ধারণা নিয়ে কাজ করে। Extended resolution নতুন চলক সংজ্ঞায়িত করতে দেয় (Tseitin-এর মূল ধারণা), আর এতে pigeonhole-এর ছোট প্রমাণ আছে বলে Stephen Cook ১৯৭৬ সালে দেখান; কিন্তু কোন চলক সংজ্ঞায়িত করবেন, তা খোঁজা বাস্তবে কঠিন। Symmetry চেনা আর cardinality যুক্তি preprocessing-এ যোগ করা আরেকটি পথ।
গভীর স্তরে এটি পর্ব ৬২-এর প্রশ্নের সঙ্গে জড়িত: এমন কোনো প্রমাণ-পদ্ধতি কি আছে, যেখানে প্রতিটি unsatisfiable সূত্রের polynomial আকারের প্রমাণ আছে? থাকলে NP = coNP, যা খোলা প্রশ্ন আর বেশিরভাগের বিশ্বাসে মিথ্যা। তাই প্রতিটি নির্দিষ্ট প্রমাণ-পদ্ধতির জন্য কঠিন সূত্র খোঁজা proof complexity-র কর্মসূচি, আর প্রতিটি নতুন solver-কৌশল আসলে একটি প্রমাণ-পদ্ধতির নতুন খোঁজ-নীতি।
মূল উপলব্ধি: CDCL-এর শক্তি প্রায় ঠিক resolution-এর সমান; এর বাইরে যেতে cutting planes বা extended resolution-এর মতো শক্তিশালী প্রমাণ-পদ্ধতি লাগে, আর সব সূত্রে ছোট প্রমাণের আশা NP = coNP-এর প্রশ্নে আটকে।
প্র ০৩বাজারঘরের রাইডার-বণ্টনে ILP আর slot-বণ্টনে SAT ব্যবহার করা হলো। একই সমস্যা কি অন্যটিতে লেখা যেত? কোনটি কখন ভালো, আর integrality gap কেন জরুরি?
দুটিই NP-complete, তাই polynomial reduction দিয়ে একটিকে অন্যটিতে সবসময় লেখা যায় (উপপাদ্য ৭.১ SAT থেকে ILP-এর দিক দেখায়; উল্টো দিক Cook–Levin থেকে)। প্রশ্নটি তাই সম্ভব-অসম্ভবের নয়, দক্ষতার। Slot সমস্যা ILP-তে: xv,c ∈ {0, 1}, প্রতি অর্ডারে ∑c xv,c = 1, প্রতি বিরোধে xu,c + xv,c ≤ 1, আর “slot c ব্যবহৃত” চলক yc-এর যোগফল সর্বনিম্ন। এর LP relaxation কুখ্যাতভাবে দুর্বল: প্রতিটি xv,c = 1/k দিলে সব শর্ত মানে, তাই নিম্নসীমা প্রায় কিছুই বলে না, আর branch and bound-কে বিশাল গাছ ঘুরতে হয়। এই কারণে গবেষকেরা colouring-এর জন্য আলাদা ILP formulation (যেমন independent set-ভিত্তিক) ব্যবহার করেন।
উল্টো দিকে রাইডার সমস্যা SAT-এ লিখতে হলে “মিনিটের যোগফল ≤ ৭০”-কে Boolean সার্কিটে (adder) বা pseudo-Boolean encoding-এ ভাঙতে হয়, আর “সর্বনিম্ন খরচ” মানে বারবার সীমা কমিয়ে solver চালানো (বা MaxSAT). পর্ব ৬১-এ subset-sum-এর adder encoding এর একটি উদাহরণ; চলে, কিন্তু সংখ্যা বড় হলে LP-এর সীমার মতো কোনো সংখ্যাগত তথ্য solver পায় না।
Integrality gap জরুরি কারণ এটি ILP solver-এর “দৃষ্টিশক্তি”। রাইডার run-এ gap ৫.৪৮ মিনিট, ছোট; তাই LP-এর নিম্নসীমা প্রায় আসল উত্তরের কাছে, আর branch and bound দ্রুত শেষ হয়। পর্ব ৭১-এর approximation algorithm-গুলোও প্রায়ই এই gap-এর ওপর দাঁড়ানো: LP সমাধান করে গোল করা (rounding), আর প্রমাণ দেখায় গোল করার ক্ষতি gap-এর সীমার মধ্যে। বাস্তবের দিকনির্দেশনা DSA কোর্সের পর্ব ৬৫-এ।
মূল উপলব্ধি: SAT আর ILP পরস্পরে reduce হয়, কিন্তু দক্ষতা নির্ভর করে encoding-এর ওপর: যৌক্তিক গঠনে SAT, সংখ্যা আর খরচে ILP, আর ILP-এর শক্তি তার LP relaxation কতটা আঁটসাঁট, অর্থাৎ integrality gap কত ছোট, তার ওপর।
প্র ০৪Random 3SAT-এর threshold প্রায় ৪.২৬৭, এই সংখ্যাটি কোথা থেকে এল? First moment পদ্ধতি কেন ৫.১৯-এ আটকে যায়, আর সঠিক মান প্রমাণ এত কঠিন কেন?
১৯৯০-এর দশকের শুরুতে David Mitchell, Bart Selman আর Hector Levesque-এর পরীক্ষা, আর Peter Cheeseman ও সহকর্মীদের কাজ, দেখায় random 3SAT-এ DPLL-এর কাজ অনুপাত ৪.২-৪.৩-এর কাছে চূড়ায় ওঠে, আর ঠিক সেখানেই satisfiable সূত্রের ভাগ ৫০%-এর নিচে নামে। অংশ ৫-এর run একই ছবি দেয়। পরে পরিসংখ্যান-পদার্থবিদ্যার ভাষা আসে: সূত্রকে একটি “spin glass” হিসেবে দেখে, Marc Mézard, Giorgio Parisi আর Riccardo Zecchina ২০০২ সালে “cavity method” দিয়ে threshold প্রায় ৪.২৬৭ বলে হিসাব করেন, আর একই তত্ত্ব থেকে survey propagation নামে একটি algorithm আসে, যা threshold-এর খুব কাছের বড় সূত্রও সমাধান করতে পারে। এই হিসাব গাণিতিকভাবে কঠোর নয়, কিন্তু অসাধারণ নির্ভুল ভবিষ্যদ্বাণী দিয়েছে।
First moment কেন দুর্বল? E[X]-এ সব সূত্রের model গড় করা হয়। কিছু বিরল সূত্রে model-এর সংখ্যা বিপুল, আর তারাই গড়কে টেনে তোলে; অথচ সাধারণ একটি সূত্রে model নেই। ৪.৫ থেকে ৫.১৯-এর মধ্যে E[X] সূচকীয়ভাবে বড়, তবু প্রায় সব সূত্র unsatisfiable. উন্নত কৌশল (যেমন শুধু “স্থানীয়ভাবে সর্বোচ্চ” model গোনা) ওপরের সীমা প্রায় ৪.৪৯-এ নামিয়েছে। নিচের সীমার জন্য second moment পদ্ধতি লাগে (E[X]2/E[X2] ≤ P(X > 0)); Dimitris Achlioptas আর Cristopher Moore ২০০২ সালের দিকে দেখান, বড় k-এ এটি সঠিক ক্রমের সীমা দেয়, কিন্তু k = 3-এ দুর্বল। k = 3-এর প্রমাণিত নিচের সীমা প্রায় ৩.৫২ algorithm বিশ্লেষণ থেকে আসে: একটি সরল algorithm ওই অনুপাত পর্যন্ত উচ্চ সম্ভাবনায় model পায়।
Ding, Sly আর Sun ২০১৫ সালে পদার্থবিদ্যার ভবিষ্যদ্বাণীকে বড় k-এর জন্য কঠোরভাবে প্রমাণ করেন। k = 3-এ ফাঁক এখনো খোলা।
মূল উপলব্ধি: ৪.২৬৭ একটি পদার্থবিদ্যা-ভিত্তিক অনুমান, পরীক্ষায় সমর্থিত কিন্তু k = 3-এ অপ্রমাণিত; first moment-এর ৫.১৯ প্রমাণিত কিন্তু ঢিলা, কারণ বিরল model-সমৃদ্ধ সূত্র গড়কে ফুলিয়ে তোলে।
প্র ০৫Schöning-এর (4/3)n algorithm brute force-এর চেয়ে সূচকীয়ভাবে ভালো, তবু সূচকীয়। 3SAT-এর জন্য সবচেয়ে ভালো জানা সময় কত, আর ETH এই দৌড়ে কী বলে?
2n থেকে নামার প্রথম পরিচিত বড় ধাপ Burkhard Monien আর Ewald Speckenmeyer-এর ১৯৮৫ সালের branching algorithm, যা প্রায় 1.618n দেয়। কৌশল: একটি মিথ্যা হতে পারা clause (a ∨ b ∨ c) ধরে তিনটি শাখা, “a সত্য”, “a মিথ্যা, b সত্য”, “a, b মিথ্যা, c সত্য”, যা সব শাখা মিলে ২৩ − ১ = ৭টির বদলে চলক-সংখ্যা দ্রুত কমায়। ১৯৯৮ সালে Ramamohan Paturi, Pavel Pudlák, Michael Saks আর Francis Zane PPSZ algorithm দেন: চলকগুলো এলোমেলো ক্রমে নিয়ে, প্রতিটির মান যদি ছোট resolution-এ বাধ্য হয় তবে বাধ্য মান, নইলে এলোমেলো। Schöning-এর ১৯৯৯ সালের random walk (প্রায় 1.334n) সরলতায় অনন্য, আর পরে derandomize-ও করা হয়েছে। বর্তমানে জানা সেরা randomized সীমাগুলো PPSZ-এর উন্নত বিশ্লেষণ থেকে, প্রায় 1.307n-এর কাছে (সাম্প্রতিক কাজে আরও সামান্য উন্নতি দাবি করা হয়েছে; সঠিক দশমিক উৎসভেদে ভিন্ন)।
লক্ষ করুন উন্নতির ধরন: ভিত্তি 2 থেকে 1.3-এর দিকে, কখনো 1-এ নয়। ETH (পর্ব ৬৩) ঠিক এটাই অনুমান করে: এমন একটি c > 1 আছে, যার নিচে 3SAT-এর ভিত্তি নামানো যাবে না। কেউ যদি cn-এর ভিত্তি যেকোনো ধ্রুবকের কাছে নামিয়ে দিতে পারতেন, ETH মিথ্যা হতো, যদিও তাতে P = NP আসত না। SETH আরও সূক্ষ্ম: k বাড়লে k-SAT-এর সেরা ভিত্তি 2-এর দিকে যায় কি না; PPSZ-এর বিশ্লেষণে ভিত্তি প্রায় 21 − Θ(1/k), যা SETH-এর সঙ্গে সংগত।
WalkSAT আর Schöning-এর algorithm একটি মৌলিক সীমা ভাগ করে: তারা কখনো UNSAT প্রমাণ করে না। (4/3)n চেষ্টার পরও model না পেলে উত্তর “উচ্চ সম্ভাবনায় unsatisfiable”, যা পর্ব ৬৯-এর one-sided error-এর মতো। নিশ্চিত “না” পেতে সম্পূর্ণ পদ্ধতি লাগে।
মূল উপলব্ধি: 3SAT-এর exact algorithm-এর ভিত্তি 2 থেকে প্রায় 1.3-এ নেমেছে, কিন্তু ETH অনুমান করে এটি কখনো 1-এর কাছে যাবে না; আর random walk-ভিত্তিক algorithm শুধু model খুঁজতে পারে, UNSAT প্রমাণ করতে পারে না।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের সূত্র বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা (encoding): বাজারঘরের একটি গুদামে আজ চারটি shift; একজন কর্মী ঠিক একটি shift নেবেন। চলক x1–x4 (“shift i”) আর sequential counter-এর সহায়ক চলক s1–s3 দিয়ে “ঠিক একটি” শর্তের পুরো CNF লিখুন। কয়টি clause হলো? x1 = x3 = 1 কেন অসম্ভব, unit propagation-এর ধাপে দেখান।
“অন্তত একটি”: (x1 ∨ x2 ∨ x3 ∨ x4). “বড়জোর একটি” (k = 4, 3k − 4 = 8টি): (¬x1 ∨ s1); (¬x2 ∨ s2), (¬s1 ∨ s2), (¬x2 ∨ ¬s1); (¬x3 ∨ s3), (¬s2 ∨ s3), (¬x3 ∨ ¬s2); (¬x4 ∨ ¬s3). মোট ৯টি clause, ৭টি চলক। (Pairwise-এ হতো 1 + 6 = 7টি clause, ৪টি চলক; k = 4-এ pairwise ছোট।)
x1 = 1 আর x3 = 1 বসালে: (¬x1 ∨ s1) unit → s1 = 1; (¬s1 ∨ s2) unit → s2 = 1; এখন (¬x3 ∨ ¬s2)-এর দুটি literal মিথ্যা: বিরোধ। অর্থাৎ si “আগের কোনো shift নেওয়া হয়েছে” খবরটি সামনে বয়ে নেয়, আর x3 সেই খবর পেয়ে আটকে যায়। (amo_encodings.py-র brute force k = 4-এ দেখায় অনুমোদিত x-বিন্যাস ঠিক ৫টি।)
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “Pure literal নিয়মে আমরা φ-এর একটি literal ℓ সত্য বসাই। তাই নতুন সূত্রটি φ-এর সঙ্গে equivalent, আর DPLL φ-এর সব model গুনতে চাইলে pure literal নিয়ম নিরাপদে ব্যবহার করা যায়।” ভুলটি কোথায়? একটি ছোট উদাহরণ দিন।
Pure literal নিয়ম satisfiability রক্ষা করে (উপপাদ্য ২.২-এর ধাপ ৩), কিন্তু equivalence নয়: যেসব model-এ ℓ মিথ্যা, সেগুলো বাদ পড়ে। উদাহরণ φ = (x1 ∨ x2). দুটি literal-ই pure. x1 = 1 বসালে বাকি সূত্র ফাঁকা, আর model গুনলে পাওয়া যায় x1 = 1-এর দুটি (x2 = 0 বা 1); কিন্তু φ-এর model তিনটি: 10, 01, 11. x1 = 0, x2 = 1 মডেলটি হারিয়ে গেছে।
তাই model গোনা (#SAT) বা সব সমাধান খোঁজার কাজে pure literal নিয়ম চলে না; unit propagation চলে, কারণ তা কোনো model হারায় না (ধাপ ২)। একই কারণে সমাধান গোনার solver আলাদা কৌশল ব্যবহার করে।
-
Trace (আউটপুট অনুমান): ψ = (x1 ∨ x2) ∧ (x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (¬x1 ∨ ¬x3). DPLL চালান (unit propagation-সহ, pure literal ছাড়া, সবচেয়ে ছোট চলক আগে, আগে সত্য)। প্রতিটি শাখায় কী বাধ্য হয় আর কোথায় বিরোধ? Call-গাছে কয়টি node? একটি CDCL solver x1 = 1-এর বিরোধ থেকে কী শিখত?
শুরুতে unit নেই। x1 = 1: প্রথম দুটি clause সত্য; (¬x1 ∨ x3) unit → x3 = 1; (¬x1 ∨ ¬x3) মিথ্যা: বিরোধ। x1 = 0: শেষ দুটি সত্য; (x1 ∨ x2) unit → x2 = 1; (x1 ∨ ¬x2) মিথ্যা: বিরোধ। দুই শাখাই ব্যর্থ, তাই ψ unsatisfiable; মোট ৩টি node: মূল, x1 = 1 আর x1 = 0 শাখা। dpll_trail.py-র dpll function এই ψ-তে চালিয়ে scratch-এ মেলানো: ফল None, nodes 3.
CDCL: বিরোধী clause (¬x1 ∨ ¬x3), শেষে বসা x3-এর কারণ (¬x1 ∨ x3); x3-এ resolve করলে (¬x1). Level ১-এর literal একটি, তাই শেখা clause (¬x1) আর backjump level ০-তে, যেখানে x1 = 0 বাধ্য। তারপর x2 বাধ্য হয়ে level ০-তে বিরোধ, আর বিশ্লেষণ ফাঁকা clause পর্যন্ত যায়: (x1 ∨ ¬x2) আর (x1 ∨ x2) থেকে (x1), তারপর (x1) আর (¬x1) থেকে □. এটিই ψ-এর resolution refutation.
-
হিসাব: Random 4SAT-এ (প্রতিটি clause-এ চারটি আলাদা চলক, চিহ্ন এলোমেলো) first moment পদ্ধতিতে অনুপাত α-এর কোন মানের ওপরে সূত্র প্রায় নিশ্চিতভাবে unsatisfiable? সাধারণ k-SAT-এর সূত্রটি লিখুন, আর k বাড়লে এটি মোটামুটি কত হয়?
একটি নির্দিষ্ট মান একটি random k-clause মিথ্যা করে 2−k সম্ভাবনায়, তাই E[X] = 2n(1 − 2−k)αn. এটি → 0 যখন α > ln 2 / (−ln(1 − 2−k)). k = 4-এ: ln 2 / ln(16/15) = 0.6931 / 0.0645 ≈ 10.74. (k = 3-এ একই সূত্র 5.19 দেয়, অংশ ৫.)
বড় k-এ −ln(1 − 2−k) ≈ 2−k, তাই সীমা ≈ 2k ln 2. পরীক্ষায় 4SAT-এর threshold প্রায় ৯.৯-এর কাছে বলে উল্লেখ করা হয় (ঊর্ধ্বসীমার নিচে, যেমন হওয়ার কথা), আর বড় k-এ Ding–Sly–Sun-এর প্রমাণিত মান 2k ln 2 − (1 + ln 2)/2 + o(1)-এর কাছে, অর্থাৎ first moment বড় k-এ প্রায় সঠিক। (দশমিকগুলো scratch-এ Python দিয়ে হিসাব করা।)
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমCDCL solver-এ একটি অনুমান থেকে পরের অনুমান পর্যন্ত ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- একটি চলকে অনুমান করা আর নতুন decision level খোলা
- Unit propagation দিয়ে বাধ্য মান ছড়ানো
- একটি clause-এর সব literal মিথ্যা: বিরোধ ধরা পড়া
- বিরোধী clause থেকে first UIP পর্যন্ত resolve করে clause শেখা
- শেখা clause-এর দ্বিতীয় সর্বোচ্চ level-এ backjump, যেখানে clause-টি unit হয়ে একটি মান বাধ্য করে
আংশিক মান x1 = 1, x2 = 0-এর নিচে clause (¬x1 ∨ x2 ∨ x5) সম্পর্কে কোনটি সঠিক?
- Clause-টি মিথ্যা, তাই বিরোধ
- Clause-টি ইতিমধ্যে সত্য
- Clause-টি unit, তাই x5 = 1 বাধ্য
- x5 pure literal, তাই ইচ্ছামতো বসানো যায়
একটি CDCL solver level ৫-এ বিরোধ থেকে শিখল (¬a ∨ b ∨ ¬c), যেখানে a level ৫-এ, b level ২-এ আর c level ৪-এ বসেছিল। Solver কোন level-এ ফিরবে?
- Level ৪, কারণ সবসময় এক ধাপ পিছিয়ে যেতে হয়
- Level ৪, কারণ এটি শেখা clause-এর দ্বিতীয় সর্বোচ্চ level
- Level ২, কারণ b সবচেয়ে পুরোনো
- Level ০, কারণ প্রতিটি বিরোধের পর restart হয়
n চলক আর m = αn clause-এর random 3CNF সম্পর্কে কোন বক্তব্যটি প্রমাণিত?
- α > 5.19 হলে সূত্রটি প্রায় নিশ্চিতভাবে unsatisfiable
- Threshold ঠিক ৪.২৬৭, প্রমাণিত
- α < 4 হলে প্রতিটি সূত্র satisfiable
- সব α-তে random 3SAT polynomial সময়ে সমাধানযোগ্য
Pigeonhole সূত্র PHP(n + 1, n) CDCL SAT solver-এর জন্য কেন প্রমাণিতভাবে কঠিন?
- সূত্রটির আকার n-এর সূচকীয়
- CDCL-এর branching heuristic খারাপ বলে; ভালো heuristic-এ সহজ
- সূত্রটি satisfiable কিন্তু model বিরল
- CDCL-এর প্রতিটি UNSAT run একটি resolution প্রমাণ, আর Haken দেখান pigeonhole-এর resolution প্রমাণ সূচকীয়
3SAT ≤p 0-1 ILP reduction-এ clause (x1 ∨ ¬x2 ∨ x3) কোন অসমতায় যায় (xi ∈ {0, 1})?
- x1 − x2 + x3 ≥ 1
- x1 + (1 − x2) + x3 ≥ 1
- x1 + (1 − x2) + x3 ≥ 3
- x1 + (1 − x2) + x3 ≤ 1
WalkSAT একটি সূত্রে ১০ লাখ উল্টানোর পরও model পেল না। এ থেকে কী বলা যায়?
- সূত্রটি unsatisfiable, প্রমাণিত
- সূত্রটির সমস্যা NP-এর বাইরে
- কিছুই নিশ্চিত নয়; satisfiable কি না জানতে একটি সম্পূর্ণ solver লাগবে
- Noise p বাড়ালে অবশ্যই model পাওয়া যাবে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- সমাধানের জন্য reduction-এর দিক X ≤p SAT বা X ≤p ILP; solver-এর প্রতিটি উত্তর স্বাধীন checker-এ মেলান, আর UNSAT-কে encoding-এর ভুলের সম্ভাবনা মাথায় রেখে পড়ুন।
- DPLL (unit propagation, pure literal, branching) সঠিক আর সম্পূর্ণ। CDCL বিরোধ থেকে first UIP পর্যন্ত resolve করে clause শেখে আর দ্বিতীয় সর্বোচ্চ level-এ backjump করে।
- শেখা clause resolution-এর ফল, তাই CDCL-এর UNSAT run একটি resolution প্রমাণ; pigeonhole-এ Haken-এর সূচকীয় সীমা CDCL-এর ওপরও খাটে, অথচ LP relaxation একে সঙ্গে সঙ্গে বাতিল করে।
- Encoding-এ at-most-one (pairwise k(k − 1)/2 বনাম sequential counter 3k − 4) আর symmetry breaking বিশাল পার্থক্য আনতে পারে। Random 3SAT-এ কঠিনতম এলাকা α ≈ ৪.২৭ (পর্যবেক্ষণ); প্রমাণিত first-moment সীমা ৫.১৯.
- 0-1 ILP NP-complete; LP relaxation একটি নিম্নসীমা দেয়, আর integrality gap solver-এর দৃষ্টিশক্তি। WalkSAT আর Schöning-এর (4/3)n random walk model পায়, কিন্তু UNSAT কখনো প্রমাণ করে না।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬০ · Cook–Levin theorem — SAT কেন NP-completeফিরে দেখুনDIMACS ফাইল, Tseitin রূপান্তর আর প্রথম solver run.
- পর্ব ৬২ · coNP, NP-hard আর search বনাম decisionফিরে দেখুনResolution, UNSAT-এর certificate আর pigeonhole-এর প্রমাণ-লগ।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৭৪-এ interactive proof.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৭ — SAT আর SMT solverপাশের ট্র্যাকZ3 দিয়ে software যাচাই, DPLL(T) আর bounded model checking.
- DSA · পর্ব ৬৫ — NP-hard সমস্যা বাস্তবেপাশের ট্র্যাকছোট input, FPT, approximation, local search আর solver বাছাই।