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

Cook–Levin theorem — SAT কেন NP-complete

The Cook–Levin Theorem — SAT in NP, the Tableau Proof with Legal 2 × 3 Windows, a Real SAT Solver on the Tableau Formula, and SAT ≤p 3SAT

Taught in Bangla, this lesson proves the Cook–Levin theorem: SAT is in NP and every NP language reduces to it in polynomial time. It builds the tableau variables and the four parts φcell, φstart, φaccept and φmove, explains legal 2 × 3 windows and the O(n^2k) formula size, and splits clauses to show SAT ≤p 3SAT. In-page Python (Pyodide) checks windows and clause splitting, and a real CaDiCaL run via PySAT on a toy NTM's tableau formula (6,016 variables, 35,329 clauses) returns SATISFIABLE or UNSATISFIABLE.

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

  • SAT, CNF আর 3SAT-এর নিখুঁত সংজ্ঞা, আর verifier দিয়ে SAT ∈ NP-এর প্রমাণ
  • Tableau কী, চলক xi,j,s কী বোঝায়, আর φcell, φstart, φaccept, φmove চার অংশ কীভাবে লেখা হয়
  • Legal 2 × 3 window চেনা, আর কেন শুধু ছোট জানালা দেখেই পুরো গণনার সঠিকতা নিশ্চিত হয়
  • পুরো Cook–Levin প্রমাণ: সূত্রের আকার O(n2k), polynomial সময়ে লেখা, আর “⇔”-এর দুই দিক
  • Clause ভেঙে SAT ≤p 3SAT, Tseitin-এর কৌশল, আর একটি সত্যিকারের SAT solver দিয়ে সব যাচাই

১ · SAT — প্রশ্নটি কী, আর কেন তা NP-তে

আগের তিন পর্বে আমরা তিনটি ভিত পেয়েছি। পর্ব ৫৭-এ class P, পর্ব ৫৮-এ class NP (polynomial সময়ে যাচাই করা যায় এমন “হ্যাঁ”-এর সাক্ষ্য), আর পর্ব ৫৯-এ polynomial-time reduction ও NP-complete-এর সংজ্ঞা। কিন্তু একটি ফাঁক রয়ে গেছে: কোনো সমস্যা যে আদৌ NP-complete হতে পারে, তার প্রথম উদাহরণ কোথায়? প্রথমটি পেতে হলে NP-এর সব language-কে একসঙ্গে একটি সমস্যায় reduce করতে হবে, অথচ সেগুলোর বেশিরভাগ আমরা কখনো দেখিইনি। এই পর্বের উপপাদ্য ঠিক সেই কাজটি করে।

বাজারঘরের ডেলিভারি-ব্যবস্থাপক রাতে পরের দিনের রুটিন বানান। প্রতিটি সিদ্ধান্ত একটি হ্যাঁ/না সুইচ: “রাইডার রহিম সকালে উত্তরা যাবেন কি না”, “রাইডার সুমি দুপুরে কাজ করবেন কি না”। নিয়মগুলো লেখা হয় “অথবা” দিয়ে জোড়া শর্তে: “উত্তরায় সকালে অন্তত একজন যাবেন”, “রহিম আর সুমি একসঙ্গে ছুটিতে থাকবেন না”। প্রশ্ন একটাই: সব নিয়ম একসঙ্গে মানা যায় এমন কোনো সুইচ-বিন্যাস আছে কি? এটাই SAT. Cook–Levin বলে, এই সাদামাটা প্রশ্নটি NP-এর যেকোনো প্রশ্নকে ভেতরে ধরে রাখতে পারে।

এবার নিখুঁত ভাষায়। একটি Boolean সূত্র তৈরি হয় সত্য/মিথ্যা মানের চলক (x, y, …) আর তিনটি সংযোজক দিয়ে: ∧ (এবং), ∨ (অথবা), ¬ (না)। চলকে মান বসানোকে বলে assignment; যে assignment-এ পুরো সূত্র সত্য হয়, সেটি সূত্রটিকে satisfy করে। উদাহরণ: φ1 = (x ∨ ¬y) ∧ (¬x ∨ y) ∧ (x ∨ y). x = 1, y = 1 দিলে তিনটি বন্ধনীই সত্য, তাই φ1 satisfiable. অন্যদিকে (x) ∧ (¬x) কোনো মানেই সত্য নয়।

কয়েকটি শব্দ পরে বারবার লাগবে। একটি চলক বা তার negation হলো literal (যেমন x বা ¬y). কয়েকটি literal ∨ দিয়ে জুড়লে একটি clause. কয়েকটি clause ∧ দিয়ে জুড়লে সূত্রটি CNF-এ (conjunctive normal form) আছে বলা হয়; ওপরের φ1 একটি CNF. Discrete Mathematics কোর্সের পর্ব ৭৭-এ SAT solver দিয়ে software যাচাই দেখানো হয়েছে; এখানে আমরা প্রশ্নটির তাত্ত্বিক কাঠিন্য প্রমাণ করব।

সংজ্ঞা ১.১ (তিনটি language)

SAT = {⟨φ⟩ : φ একটি satisfiable Boolean সূত্র}.
CNF-SAT = {⟨φ⟩ : φ একটি satisfiable CNF সূত্র}.
3SAT = {⟨φ⟩ : φ একটি satisfiable CNF, যার প্রতিটি clause-এ ঠিক তিনটি literal}.

পর্ব ৫৯-এর সংজ্ঞা মনে করুন। A ≤p B মানে একটি polynomial সময়ে গণনাযোগ্য function f আছে, যাতে সব w-এর জন্য w ∈ A ⇔ f(w) ∈ B (polynomial-time reduction). B NP-hard যদি NP-এর প্রতিটি L-এর জন্য L ≤p B; আর B NP-complete যদি B NP-hard এবং B ∈ NP. দিকের নিয়মটি পর্ব ৫২-এর মতোই: A ≤p B আর B ∈ P হলে A ∈ P; A NP-hard হলে B NP-hard.

উপপাদ্য ১.২ (Cook–Levin theorem)

SAT NP-complete. অর্থাৎ (ক) SAT ∈ NP, আর (খ) প্রতিটি L ∈ NP-এর জন্য L ≤p SAT.

অংশ (ক) সহজ, তাই আগে সেটি সেরে নিই। পর্ব ৫৮-এর verifier-সংজ্ঞা অনুযায়ী দেখাতে হবে: প্রতিটি “হ্যাঁ”-instance-এর একটি ছোট certificate আছে, যা polynomial সময়ে মিলিয়ে নেওয়া যায়।

প্রমাণ (SAT ∈ NP):

  1. Certificate c = চলকগুলোর একটি assignment. চলকের সংখ্যা ≤ |φ|, তাই |c| ≤ |φ|: দৈর্ঘ্য polynomial. — ছোট সাক্ষ্য
  2. Verifier V = “input ⟨φ, c⟩-এর ওপর: c-এর মান φ-এ বসান, ভেতরের বন্ধনী থেকে বাইরের দিকে মান হিসাব করুন; পুরো সূত্র সত্য হলে গ্রহণ, নইলে বর্জন।” প্রতিটি সংযোজক একবার করে হিসাব হয়, তাই সময় |φ|-এর polynomial (সরল বাস্তবায়নেও O(|φ|2)). — দ্রুত যাচাই
  3. φ satisfiable হলে একটি satisfying assignment c আছে, আর V(⟨φ, c⟩) গ্রহণ করে। φ satisfiable না হলে কোনো c-তেই সূত্র সত্য হয় না, তাই V কখনো গ্রহণ করে না। — সঠিকতা
  4. অতএব SAT ∈ NP. সমতুল্যভাবে, একটি NTM প্রতিটি চলকের মান “অনুমান” করে তারপর V চালাতে পারে (পর্ব ৪৬-এর guess and verify). ∎

অংশ (খ)-ই আসল কাজ। এর জন্য আমরা NP-এর সংজ্ঞার দ্বিতীয় রূপটি নেব: L ∈ NP ⇔ একটি nondeterministic Turing machine L-কে polynomial সময়ে decide করে (দুই সংজ্ঞার সমতা পর্ব ৫৮-এ)। আমরা L সম্পর্কে আর কিছুই জানি না; জানি শুধু যে এমন একটি যন্ত্র N আছে। প্রমাণটিকে তাই N-এর নিয়ম-তালিকা δ দেখে যান্ত্রিকভাবে সূত্র লিখতে হবে।

ইতিহাস: Stephen Cook-এর “The complexity of theorem-proving procedures” প্রবন্ধ ১৯৭১ সালের ACM STOC সম্মেলনে উপস্থাপিত হয়। তিনি দেখান, polynomial সময়ের একটি nondeterministic যন্ত্রের যেকোনো গণনা propositional সূত্রে লেখা যায়; তাঁর reduction-এর ধারণা ছিল oracle-ভিত্তিক (আজকের ভাষায় Turing reduction-এর polynomial রূপ), আর মূল প্রবন্ধ tautology-র প্রশ্নের ভাষায় লেখা ছিল বলে জানা যায়। সোভিয়েত ইউনিয়নে Leonid Levin স্বাধীনভাবে “সার্বজনীন অনুসন্ধান সমস্যা” নিয়ে একই ধরনের ফল পান, যা ১৯৭৩ সালে প্রকাশিত হয়; তিনি এর আগেই আলোচনায় ফলটি জানিয়েছিলেন বলে উল্লেখ আছে। তাই আজ নামটি Cook–Levin. পরের বছর Richard Karp একুশটি সমস্যা NP-complete দেখিয়ে বিষয়টিকে কেন্দ্রে নিয়ে আসেন (অংশ ৮)। Cook ১৯৮২ সালে আর Karp ১৯৮৫ সালে Turing Award পান।

২ · প্রমাণের পরিকল্পনা — গণনাকে একটি ছকে লেখা

ধরি L ∈ NP, আর N একটি nondeterministic Turing machine, যার প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ nk − 3 ধাপের মধ্যে থামে, আর যে L decide করে (k একটু বড় নিলেই সবসময় এমন বলা যায়)। Input w দেওয়া আছে। আমাদের লক্ষ্য একটি সূত্র φ, যাতে w ∈ L ⇔ φ satisfiable.

মূল ভাবনা: N w গ্রহণ করে মানে কোনো একটি শাখায় শুরুর configuration থেকে বৈধ ধাপে qaccept-এ পৌঁছানো যায়। সেই শাখার configuration-গুলো একটির নিচে আরেকটি লিখলে একটি ছক হয়। পর্ব ৫৪-এ ঠিক এমন computation history ডমিনোতে লেখা হয়েছিল; এখানে লেখা হবে Boolean চলকে। প্রতিটি configuration পর্ব ৪৩-এর রীতিতে u q v আকারে (configuration): tape-এর লেখা uv, state q, আর head v-এর প্রথম চিহ্নের ওপর।

ক্রিকেটের স্কোরার প্রতিটি বলের পরে স্কোরবোর্ডের পুরো অবস্থা খাতায় এক লাইনে লেখেন। পুরো ম্যাচের খাতা ঠিক আছে কি না যাচাই করতে কোনো দৈব জ্ঞান লাগে না: প্রথম লাইন ম্যাচ শুরুর অবস্থা কি না, শেষে ফল লেখা আছে কি না, আর পাশাপাশি দুই লাইনের মধ্যে শুধু একটি বলের পরিবর্তন হয়েছে কি না। শেষ যাচাইটিও স্থানীয়: একটি বলে বদলায় শুধু রান, বল-সংখ্যা আর হয়তো একজন ব্যাটার। Tableau ঠিক এই খাতা, আর φ এই তিন রকম যাচাইয়ের Boolean রূপ।

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

N-এর w-এর ওপর একটি tableau হলো nk × nk মাপের একটি ছক, যার প্রতিটি সারি N-এর একটি configuration, দুই প্রান্তে # চিহ্ন দিয়ে ঘেরা আর দরকারমতো ␣ দিয়ে ভরা। প্রথম সারি শুরুর configuration q0w1⋯wn, আর প্রতিটি সারি আগের সারি থেকে N-এর এক বৈধ ধাপে আসে। কোনো সারিতে qaccept থাকলে tableau-টি গ্রহণকারী।

তিনটি খুঁটিনাটি। প্রথমত, nk সারি যথেষ্ট, কারণ শাখাটি nk − 3 ধাপের মধ্যে থামে। দ্বিতীয়ত, nk কলামও যথেষ্ট: সেই সময়ে head সর্বোচ্চ ততগুলো ঘরেই যেতে পারে, আর # দুটির জায়গা আগেই রাখা হয়েছে। তৃতীয়ত, শাখা আগেই থেমে গেলে কী হবে? এই পর্বের রীতি: থামা configuration-এর পরের সারি হুবহু তার কপি। ফলে প্রতিটি tableau-তে ঠিক nkটি সারি থাকে। N-এর প্রতিটি গ্রহণকারী শাখা একটি গ্রহণকারী tableau দেয়, আর উল্টোটাও সত্য; তাই প্রশ্নটি দাঁড়ায়: গ্রহণকারী tableau আছে কি?

নিচের ছবি পুরো পর্বের খেলনা উদাহরণ। যন্ত্র B {0, 1}-এর ওপর সেই string-গুলো গ্রহণ করে, যাতে অন্তত একটি 1 আছে: প্রতিটি 1-এ সে “অনুমান” করে, এখানেই থামবে কি না। ছবিটি B-এর input 001-এর গ্রহণকারী tableau.

খেলনা যন্ত্র B-এর tableau, input 001

প্রতিটি সারি একটি configuration; কমলা ফ্রেমটি একটি 2 × 3 window.

Tableau of the toy NTM B on input 001 with one 2 by 3 window ১২৩৪৫৬৭৮ ১২৩৪৫ #q₀001␣␣# #0q₀01␣␣# #00q₀1␣␣# #001Y␣␣# #001Y␣␣# নীল সারি: শুরুর configuration (φ_start) সবুজ ঘর: Y = q_accept (φ_accept) কমলা ফ্রেম: একটি window (φ_move) প্রতিটি ঘরে ঠিক একটি চিহ্ন: φ_cell
ছবি ৬০.১ — B-এর input 001-এর গ্রহণকারী tableau: ৫টি সারি × ৮টি কলাম। কমলা ফ্রেমের ওপরে 0 q₀ 1, নিচে 0 1 Y: B-এর একটি বৈধ ধাপের ছোট টুকরো।

৩ · চলক আর তিনটি সহজ অংশ — φcell, φstart, φaccept

ধরি N = (Q, Σ, Γ, δ, q0, qaccept, qreject), আর C = Q ∪ Γ ∪ {#}: ছকের একটি ঘরে যেসব চিহ্ন বসতে পারে। প্রতিটি সারি i, কলাম j (দুটিই 1 থেকে nk) আর প্রতিটি চিহ্ন s ∈ C-এর জন্য একটি চলক:

xi,j,s = 1 ⇔ ছকের সারি i, কলাম j-এর ঘরে চিহ্ন s

মোট চলক nk · nk · |C| = O(n2k)টি; |C| শুধু N-এর ওপর নির্ভর করে, w-এর ওপর নয়, তাই এটি একটি ধ্রুবক। এখন চার অংশের তিনটি লেখা যাক।

φcell, প্রতিটি ঘরে ঠিক একটি চিহ্ন। প্রতিটি ঘরে অন্তত একটি চিহ্ন, আর কোনো দুটি আলাদা চিহ্ন একসঙ্গে নয়:

φcell = ⋀1 ≤ i, j ≤ nk [ (⋁s ∈ C xi,j,s) ∧ (⋀s, t ∈ C, s ≠ t (¬xi,j,s ∨ ¬xi,j,t)) ]

এখানে বড় ⋀ মানে “সবগুলোর ∧”, আর বড় ⋁ মানে “সবগুলোর ∨”। প্রথম বন্ধনী একটি লম্বা clause, দ্বিতীয়টি দুই-literal-এর অনেক clause; তাই φcell নিজেই CNF. এই অংশ satisfy করা প্রতিটি assignment মানে একটি সুনির্দিষ্ট ছক, প্রতিটি ঘরে একটিমাত্র চিহ্নসহ।

φstart, প্রথম সারি শুরুর configuration.

φstart = x1,1,# ∧ x1,2,q0 ∧ x1,3,w1 ∧ ⋯ ∧ x1,n+2,wn ∧ x1,n+3,␣ ∧ ⋯ ∧ x1,nk−1,␣ ∧ x1,nk,#

প্রতিটি পদ একটি এক-literal-এর clause. Input w শুধু এই অংশে ঢোকে; বাকি তিন অংশ শুধু N আর n-এর ওপর নির্ভর করে।

φaccept, কোথাও qaccept আছে।

φaccept = ⋁1 ≤ i, j ≤ nk xi,j,qaccept

একটি লম্বা clause. বাকি থাকে φmove, যা নিশ্চিত করবে প্রতিটি সারি আগের সারি থেকে বৈধ ধাপে আসে; সেটি অংশ ৪-এর বিষয়।

খেলনা যন্ত্রটি এবার formal ভাষায়। B = (Q, Σ, Γ, δ, q0, Y, X), যেখানে Q = {q0, Y, X} (Y = qaccept, X = qreject), Σ = {0, 1}, Γ = {0, 1, ␣}, আর

δ(q0, 0) = {(q0, 0, R)}, δ(q0, 1) = {(q0, 1, R), (Y, 1, R)}, δ(q0, ␣) = {(X, ␣, R)}

B শুধু ডানে চলে। কোনো 1-এ এসে সে দুই দিকে ভাগ হয়: হয় আরও এগোয়, নয় Y-তে গিয়ে গ্রহণ করে। প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ n + 1 ধাপের মধ্যে থামে। তাই খেলনা tableau-তে nk-এর জায়গায় নেওয়া হয় n + 2টি সারি আর n + 5টি কলাম (n + 3টি ঘর আর দুটি #); w = 001-এ ৫ × ৮ ছক, |C| = 7, মোট ২৮০টি x-চলক। কোডে q0-কে লেখা হবে q, ␣-কে _.

1φ_start: সারি ১ নির্দিষ্ট2φ_move: δ(q₀, 0) একমাত্র move3φ_move: δ(q₀, 1)-এ দুই পথ4φ_move: থামার পরে কপি5φ_accept: কোথাও Y6φ_cell: প্রতি ঘরে এক চিহ্ন
ছক
সারি ১
সারি ২
সারি ৩
সারি ৪
সারি ৫
  1. শুরুর সারি। φstart-এর ৮টি এক-literal clause সারি ১-কে বেঁধে দেয়: #, তারপর q0, তারপর input 001, দুটি ␣ আর শেষে #. এখানে কোনো স্বাধীনতা নেই।
  2. সারি ২. সারি ১-এ q0 পড়ছে 0; δ(q0, 0)-এর একটিই বিকল্প (q0, 0, R). φmove-এর window-গুলো তাই সারি ২-কে জোর করে # 0 q0 0 1 ␣ ␣ # বানায়।
  3. সারি ৩. আবার q0 পড়ছে 0, আবার একই একমাত্র move: # 0 0 q0 1 ␣ ␣ #. পুরো ছকে যেখানে state নেই, সেই ঘরগুলো শুধু নিচে কপি হয়।
  4. সারি ৪, অনুমানের জায়গা। q0 এখন পড়ছে 1, আর δ(q0, 1)-এ দুটি বিকল্প: # 0 0 1 q0 ␣ ␣ # অথবা # 0 0 1 Y ␣ ␣ #. দুটিই window-এর দিক থেকে বৈধ। প্রথমটি নিলে পরে ␣ পড়ে X-এ বর্জন হয়, আর কোনো সারিতে Y আসে না; তাই φaccept সত্য রাখতে হলে Y-ই নিতে হয়।
  5. সারি ৫, কপি। Y একটি থামা state, তাই এই পর্বের রীতিতে পরের সারি হুবহু কপি। ছকে এখন n + 2 = ৫টি সারি।
  6. যাচাই। সারি ৪-এর কলাম ৫-এ Y, তাই φaccept সত্য। প্রতিটি ঘরে ঠিক একটি চিহ্ন, তাই φcell সত্য। ৫ × ৮ = ৪০টি ঘর, প্রতিটিতে ৭টি চলক: ২৮০টি x-চলক, যার ঠিক ৪০টি সত্য। অংশ ৬-এ একটি সত্যিকারের SAT solver ঠিক এই ছকটিই ফিরিয়ে দেবে।

৪ · Legal window আর φmove — স্থানীয় যাচাইয়ে পুরো গণনা

এখন সবচেয়ে সূক্ষ্ম অংশ। “সারি i + 1 সারি i থেকে এক বৈধ ধাপে আসে” কথাটি সরাসরি লিখতে গেলে পুরো সারি দুটি একসঙ্গে দেখতে হয়। কিন্তু Turing machine-এর এক ধাপে বদলায় খুব অল্প: head-এর নিচের ঘর, state-এর অবস্থান, আর তার ঠিক পাশের ঘর। তাই ছোট জানালা দিয়ে দেখলেই চলে।

সংজ্ঞা ৪.১ (window আর legal window)

সারি i আর i + 1-এর একই তিনটি পাশাপাশি কলাম j − 1, j, j + 1 নিয়ে গড়া 2 × 3 টুকরোকে বলে (i, j)-window. একটি window legal, যদি এটি N-এর কোনো configuration আর তার এক-ধাপ পরের কোনো configuration (দুটিই # দিয়ে ঘেরা) থেকে একই কলামে কেটে নেওয়া যায়। অর্থাৎ window-টি δ-এর কোনো নিয়ম ভাঙে না।

এখন φmove লেখা যায়। একটি window legal হওয়ার শর্ত হলো, ছয়টি ঘরে কোনো একটি legal ছয়-চিহ্নের বিন্যাস (a1, …, a6) বসেছে:

φmove = ⋀1 ≤ i < nk, 1 < j < nk ⋁(a1,…,a6) legal (xi,j−1,a1 ∧ xi,j,a2 ∧ xi,j+1,a3 ∧ xi+1,j−1,a4 ∧ xi+1,j,a5 ∧ xi+1,j+1,a6)

Legal window-এর সংখ্যা শুধু N-এর ওপর নির্ভর করে (সর্বোচ্চ |C|6), তাই প্রতিটি window-এর সূত্র ধ্রুবক আকারের। এই অংশ CNF নয়: ভেতরে ∧-এর ∨. অংশ ৭-এ দেখব, একে কীভাবে CNF করা যায়।

B-এর কয়েকটি window ধাপে ধাপে বিচার করা যাক। মনে রাখুন, প্রশ্নটি সবসময় একই: এই ছয়টি চিহ্ন কি কোনো সত্যিকারের (configuration, পরের configuration) জোড়া থেকে আসতে পারে?

1δ(q₀, 0) = {(q₀, 0, R)}2δ(q₀, 1) = {(q₀, 1, R), (Y, 1, R)}3δ(q₀, ␣) = {(X, ␣, R)}4থামা state: পরের সারি কপি
2 × 3 window
ওপর
নিচ
রায়
  1. Y-এর বিকল্প। ওপরে # q0 1: সারির শুরুতে q0 পড়ছে 1. বিকল্প (Y, 1, R) নিলে 1 অপরিবর্তিত থাকে আর state এক ঘর ডানে যায়: নিচে # 1 Y. Legal.
  2. অন্য বিকল্প। একই ওপরের সারি, কিন্তু বিকল্প (q0, 1, R): নিচে # 1 q0. এটিও legal. দুটি legal window-এর মধ্যে কোনটি সত্যিকারের ছকে বসবে, তা ঠিক করে assignment; এভাবেই nondeterminism সূত্রে ঢোকে।
  3. ভুল লেখা। ওপরে q0 1 ␣, নিচে 0 Y ␣. δ(q0, 1)-এর কোনো বিকল্পই 1-এর জায়গায় 0 লেখে না। Illegal.
  4. পাশ থেকে আসা state. ওপরে 0 0 0, কোনো state নেই, অথচ নিচে q0 0 0. অবাক লাগলেও legal: window-এর ঠিক বাঁয়ে q0 ছিল, সে 0 পড়ে ডানে সরে window-এ ঢুকেছে। পাশের window-টি সেই move নিজে যাচাই করবে।
  5. মাঝখানে উদয়। ওপরে 0 0 0, নিচে 0 q0 0. এক ধাপে state সর্বোচ্চ এক ঘর সরে; window-এর বাইরে থেকে মাঝের ঘরে পৌঁছাতে হলে দুই ঘর সরতে হতো। Illegal.
  6. দূরের পরিবর্তন। ওপরে 0 1 ␣, নিচে 1 1 ␣: আশপাশে কোনো state নেই, তবু একটি ঘর বদলেছে। Head ছাড়া tape বদলায় না। Illegal.
  7. থামার পরে। ওপরে ␣ Y ␣, নিচে হুবহু একই। Y থামা state, আর আমাদের রীতিতে পরের সারি কপি। Legal. সব মিলিয়ে B-এর legal window ২৩৯টি, পরের কোড ব্লক তা গুনে দেখাবে।

এবার মূল দাবি, যার ওপর পুরো প্রমাণ দাঁড়িয়ে। এখানে “লেমা” মানে উপপাদ্যের পথে একটি সহায়ক উপপাদ্য।

লেমা ৪.২ (window লেমা)

সারি i একটি configuration হলে, আর সারি i ও i + 1-এর প্রতিটি window legal হলে, সারি i + 1-ও একটি configuration, যা সারি i থেকে N-এর এক বৈধ ধাপে আসে।

প্রমাণের রূপরেখা:

  1. সারি i-এর যে ঘর state-এর পাশে নয়, সেটি এমন একটি window-এর ওপরের মাঝের ঘর, যার ওপরের সারিতে কোনো state নেই। সংজ্ঞা অনুযায়ী এমন legal window-এ ওপরের মাঝের চিহ্ন নিচে অপরিবর্তিত থাকে (ধাপ ৪-এর window-এ মাঝের 0 অপরিবর্তিত)। — দূরের ঘর কপি হয়
  2. সারি i-এর state q, ধরি কলাম j-তে, আর head-এর নিচে চিহ্ন a. (i, j)-window-এর ওপরের মাঝে q; এর legal হওয়া মানে নিচের তিন ঘর δ(q, a)-এর কোনো একটি বিকল্প অনুযায়ী লেখা। — head-এর চারপাশ δ মানে
  3. পাশাপাশি window-গুলো দুটি করে কলাম ভাগ করে, আর নিচের সারির একই ঘর একই চলক। তাই আলাদা window আলাদা বিকল্প “বেছে” নিতে পারে না; সব মিলে নিচের সারি একটি বিকল্পের ঠিক ফল। — সামঞ্জস্য
  4. অতএব সারি i + 1 হলো সারি i-এর একটি বৈধ পরের configuration. (Sipser-এর বইয়ে এই দাবির পূর্ণ বিবরণ আছে।) ∎

নিচের Python ব্লক B-এর legal window-গুলো সংজ্ঞা ৪.১ অনুযায়ীই তৈরি করে: চার ঘরের সব সম্ভাব্য configuration নেয়, প্রতিটির পরের configuration হিসাব করে, আর দুটিকে # দিয়ে ঘিরে পাশাপাশি সব 2 × 3 টুকরো কেটে একটি set-এ রাখে। তারপর stepper-এর সাতটি window পরীক্ষা করে।

# Toy NTM B over {0,1}: accept if the input contains a 1 (guess "this 1")
from itertools import product, combinations
G, Q, HALT = ["0", "1", "_"], ["q", "Y", "X"], {"Y", "X"}   # Y accept, X reject
D = {("q", "0"): [("q", "0", "R")],
     ("q", "1"): [("q", "1", "R"), ("Y", "1", "R")],        # two choices
     ("q", "_"): [("X", "_", "R")]}
C = Q + G + ["#"]                                            # cell symbols
def succ(row):              # all next configurations; B only moves right
    p = next(k for k, s in enumerate(row) if s in Q)
    if row[p] in HALT: return [row]                          # halted: copy
    if p + 1 == len(row): return []
    return [row[:p] + [b, r] + row[p + 2:]
            for r, b, mv in D.get((row[p], row[p + 1]), [])]
def windows(W):             # legal 2x3 windows, cut from real (row, next row) pairs
    win = set()
    for p, q, tape in product(range(W), Q, product(G, repeat=W - 1)):
        row = list(tape[:p]) + [q] + list(tape[p:])
        for nxt in succ(row):
            a, b = ["#"] + row + ["#"], ["#"] + nxt + ["#"]
            win |= {("".join(a[j:j + 3]), "".join(b[j:j + 3])) for j in range(W)}
    return win
WIN = windows(4)
print("legal windows:", len(WIN))
for top, bot in [("#q1", "#1Y"), ("#q1", "#1q"), ("q1_", "0Y_"), ("000", "q00"),
                 ("000", "0q0"), ("01_", "11_"), ("_Y_", "_Y_")]:
    print(f"  {top} / {bot}:", "legal" if (top, bot) in WIN else "ILLEGAL")

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

legal windows: 239
  #q1 / #1Y: legal
  #q1 / #1q: legal
  q1_ / 0Y_: ILLEGAL
  000 / q00: legal
  000 / 0q0: ILLEGAL
  01_ / 11_: ILLEGAL
  _Y_ / _Y_: legal

B-এর ২৩৯টি legal window, আর সাতটি রায় stepper-এর সঙ্গে হুবহু মেলে। চার ঘরের সারি থেকে বানানো হলেও সংখ্যাটি সারি চওড়া করলে বদলায় না: scratch-এ পাঁচ, ছয় আর সাত ঘরের সারিতেও ২৩৯ পেয়েছি। এটাই “legal window-এর সংখ্যা শুধু N-এর ওপর নির্ভর করে” কথার একটি ছোট প্রমাণ-নমুনা। বেশিরভাগ window-এ কোনো state নেই, শুধু কপি; state-ওয়ালা অল্প কয়েকটি window-ই δ-এর আসল নিয়ম বহন করে।

৫ · পুরো প্রমাণ — আকার, polynomial সময় আর দুই দিক

সব টুকরো হাতে। φ = φcell ∧ φstart ∧ φaccept ∧ φmove. এখন উপপাদ্য ১.২-এর অংশ (খ)।

প্রমাণ (প্রতিটি L ∈ NP-এর জন্য L ≤p SAT):

  1. L ∈ NP, তাই একটি NTM N আছে, যা L decide করে আর প্রতিটি শাখায় nk − 3 ধাপের মধ্যে থামে। Reduction f: w ↦ φ, যেখানে φ ওপরের চার অংশ, n = |w|. — নির্মাণ
  2. আকার: ঘর n2kটি। φcell-এ প্রতি ঘরে ধ্রুবক সংখ্যক literal, মোট O(n2k); φstart-এ O(nk); φaccept-এ O(n2k); φmove-এ O(n2k)টি window, প্রতিটি ধ্রুবক আকারের। প্রতিটি চলকের নাম লিখতে O(log n) বিট লাগে, তাই |φ| = O(n2k log n): polynomial. — আকার
  3. সময়: f কয়েকটি নেস্টেড লুপে সূত্রটি লিখে যায়; legal window-এর তালিকা N থেকে একবার বানানো, আর তা w-এর ওপর নির্ভর করে না। মোট সময় |φ|-এর সমানুপাতিক, অর্থাৎ polynomial. — f polynomial সময়ে গণনাযোগ্য
  4. (⇒) w ∈ L হলে N-এর একটি গ্রহণকারী শাখা আছে। তার configuration-গুলো সারিতে লিখি (থামার পরে কপি), আর প্রতিটি ঘরের চিহ্ন s-এর জন্য xi,j,s = 1, বাকি সব 0. প্রতি ঘরে একটি চিহ্ন, প্রথম সারি শুরুর configuration, প্রতিটি window সত্যিকারের ধাপ থেকে কাটা বলে legal, আর কোথাও qaccept: চার অংশই সত্য। — গণনা থেকে assignment
  5. (⇐) φ satisfiable হলে একটি satisfying assignment নিন। φcell বলে, প্রতি ঘরে ঠিক একটি চিহ্ন: একটি ছক পাওয়া গেল। φstart বলে সারি ১ শুরুর configuration. লেমা ৪.২ আর induction দিয়ে প্রতিটি সারি আগের সারি থেকে বৈধ ধাপে আসে। φaccept বলে কোনো সারিতে qaccept. তাই ছকটি N-এর একটি গ্রহণকারী শাখা, আর w ∈ L. — assignment থেকে গণনা
  6. অতএব w ∈ L ⇔ f(w) ∈ SAT, আর f polynomial সময়ের: L ≤p SAT. অংশ ১-এর SAT ∈ NP মিলিয়ে SAT NP-complete. ∎

সাধারণ ভুল: “φ satisfiable কি না জানতে আমরা N চালাই” বা “f nondeterministically শাখা বেছে নেয়”। না। f একটি সাধারণ deterministic algorithm: N-কে কখনো চালায় না, কোনো শাখা বাছে না, শুধু নিয়ম দেখে সূত্র লেখে। কোন শাখা গ্রহণ করে, সেই “অনুমান” পুরোটাই সূত্রের satisfying assignment-এর ভেতরে লুকানো। ঠিক এ কারণে reduction polynomial অথচ SAT সমাধান সহজ নয়।

এবার B-এর জন্য পুরো সূত্র বানিয়ে ছোট একটি DPLL solver দিয়ে সমাধান করা যাক। এই ব্লক আগের ব্লকের WIN, C আর product ব্যবহার করে (একই namespace). φmove-কে CNF-এ রাখতে প্রতিটি (জায়গা, legal window) জোড়ার জন্য একটি সহায়ক চলক y নেওয়া হয়েছে: y সত্য হলে window-এর ছয়টি ঘর সেই চিহ্নের, আর প্রতি জায়গায় অন্তত একটি y সত্য। এটি অংশ ৭-এর Tseitin-কৌশলের একটি রূপ। Solver প্রথমে unit propagation চালায়, তারপর দরকার হলে একটি literal-এ অনুমান করে।

def encode(w):              # phi_cell, phi_start, phi_accept, phi_move -> CNF
    t = len(w) + 1; R, W = t + 1, t + 2; cols = W + 2       # B runs <= n+1 steps
    var = lambda i, j, s: (i * cols + j) * len(C) + C.index(s) + 1
    nv, cl = R * cols * len(C), []
    for i, j in product(range(R), range(cols)):              # cell: exactly one
        cl.append([var(i, j, s) for s in C])
        cl += [[-var(i, j, s), -var(i, j, u)] for s, u in combinations(C, 2)]
    start = "#q" + w + "_" * (W - 1 - len(w)) + "#"
    cl += [[var(0, j, s)] for j, s in enumerate(start)]      # start row
    cl.append([var(i, j, "Y") for i in range(R) for j in range(cols)])  # accept
    for i, j in product(range(R - 1), range(cols - 2)):      # move: y -> window
        ys = []
        for top, bot in sorted(WIN):
            nv += 1; ys.append(nv)
            cl += [[-nv, var(i + d // 3, j + d % 3, (top + bot)[d])] for d in range(6)]
        cl.append(ys)
    return cl, nv, R, cols, var
def dpll(cl, a):            # unit propagation, then branch on a free literal
    changed = True
    while changed:
        changed = False
        for c in cl:
            if any(a.get(abs(l)) == (l > 0) for l in c): continue
            free = [l for l in c if abs(l) not in a]
            if not free: return None                         # conflict
            if len(free) == 1: a[abs(free[0])] = free[0] > 0; changed = True
    lit = next((l for c in cl if not any(a.get(abs(k)) == (k > 0) for k in c)
                for l in c if abs(l) not in a), None)
    if lit is None: return a                                 # all clauses true
    return dpll(cl, {**a, abs(lit): lit > 0}) or dpll(cl, {**a, abs(lit): lit < 0})
for w in ["01", "00"]:
    cl, nv, R, cols, var = encode(w); a = dpll(cl, {})
    print(f"w = {w}: {nv} variables, {len(cl)} clauses ->", "SAT" if a else "UNSAT")
    for i in range(R if a else 0):
        print("   ", " ".join(s for j in range(cols) for s in C if a.get(var(i, j, s))))

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

w = 01: 3781 variables, 22149 clauses -> SAT
    # q 0 1 _ _ #
    # 0 q 1 _ _ #
    # 0 1 Y _ _ #
    # 0 1 Y _ _ #
w = 00: 3781 variables, 22149 clauses -> UNSAT

Input 01 (n = 2) থেকে ৪ × ৭ ছক: ১৯৬টি x-চলক আর ৩,৫৮৫টি সহায়ক y (১৫টি window-জায়গা × ২৩৯), মোট ৩,৭৮১টি চলক আর ২২,১৪৯টি clause. Solver-এর assignment থেকে ছাপা ছকটি B-এর দুই ধাপের গ্রহণকারী শাখা: q0 0 পেরিয়ে 1-এ এসে Y বেছে নেয়, তারপর কপি। Input 00-এ একই আকারের সূত্র unsatisfiable, কারণ B-এর একমাত্র শাখা X-এ বর্জন করে, আর কোনো ছকে Y বসানো যায় না। লক্ষ করুন, ছোট input-এও সূত্র হাজার হাজার clause-এর; “polynomial” মানে ছোট নয়, শুধু বৃদ্ধির হার নিয়ন্ত্রিত।

বৃদ্ধির হারটি সংখ্যায় দেখা যাক। নিচের JavaScript ব্লক একই গঠনের সূত্রের চলক আর clause গোনে: প্রথমে খেলনা run-এর ৫ × ৮ ছক (অংশ ৬-এর সত্যিকারের run-এর সঙ্গে মেলানোর জন্য), তারপর k = 2 ধরে n2 × n2 ছক।

// Size of the Cook-Levin CNF for a tableau with R rows and K columns
const C = 7, L = 239;          // cell symbols and legal windows of the toy NTM
function size(R, K) {
  const cells = R * K, pos = (R - 1) * (K - 2);      // window positions
  const cell = cells * (1 + C * (C - 1) / 2);        // at least one + at most one
  const start = K, accept = 1, move = pos * (6 * L + 1);
  return { vars: cells * C + pos * L, clauses: cell + start + accept + move,
           cell, start, accept, move };
}
console.log("toy run, w = 001, 5 x 8:", JSON.stringify(size(5, 8)));
console.log("   n | tableau n^2 x n^2 |    variables |      clauses | 2^n");
for (const n of [3, 5, 10, 20, 40]) {
  const s = size(n ** 2, n ** 2);
  console.log(String(n).padStart(4), "|", `${n ** 2} x ${n ** 2}`.padStart(17), "|",
    String(s.vars).padStart(12), "|", String(s.clauses).padStart(12), "|", 2 ** n);
}
const r = size(40 ** 2, 40 ** 2).clauses / size(20 ** 2, 20 ** 2).clauses;
console.log("clauses(n=40) / clauses(n=20) =", r.toFixed(2), " (2^4 = 16)");

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

toy run, w = 001, 5 x 8: {"vars":6016,"clauses":35329,"cell":880,"start":8,"accept":1,"move":34440}
   n | tableau n^2 x n^2 |    variables |      clauses | 2^n
   3 |             9 x 9 |        13951 |        82152 | 8
   5 |           25 x 25 |       136303 |       805896 | 32
  10 |         100 x 100 |      2388778 |     14142471 | 1024
  20 |         400 x 400 |     39073678 |    231401271 | 1048576
  40 |       1600 x 1600 |    628613278 |   3723036471 | 1099511627776
clauses(n=40) / clauses(n=20) = 16.09  (2^4 = 16)

প্রথম লাইনের সংখ্যাগুলো (৬,০১৬টি চলক, ৩৫,৩২৯টি clause, অংশ অনুযায়ী ৮৮০ + ৮ + ১ + ৩৪,৪৪০) অংশ ৬-এর সত্যিকারের run-এর সঙ্গে হুবহু মিলবে। টেবিলে n দ্বিগুণ করলে clause প্রায় ১৬ গুণ হয়, যা n4 = n2k বৃদ্ধির চিহ্ন (k = 2). ছোট n-এ সূত্র 2n-এর চেয়ে অনেক বড়, কারণ ধ্রুবক ২৩৯ আর ৭ বড়; কিন্তু n = 40-এ 2n এগিয়ে গেছে, আর তারপর ব্যবধান শুধু বাড়বে। এটাই polynomial আর exponential-এর পার্থক্য, যা পর্ব ৫৭-এর মূল কথা।

৬ · সত্যিকারের run — DIMACS ফাইল আর একটি SAT solver

ব্রাউজারের DPLL একটি শেখার খেলনা। বাস্তবের SAT solver, যেমন CaDiCaL, CDCL কৌশলে লাখো চলকের সূত্রও প্রায়ই দ্রুত মেটায়। Solver-রা সূত্র নেয় একটি প্রচলিত টেক্সট ফরম্যাটে, DIMACS CNF: শুরুতে p cnf লাইনে চলক আর clause-এর সংখ্যা, তারপর প্রতি লাইনে একটি clause, যেখানে চলক k মানে xk, −k মানে ¬xk, আর শেষে 0.

পরীক্ষাটি এমন: একটি uv প্রকল্পে ওপরের encoder-এর হুবহু এক যুক্তি দিয়ে (সাধারণ রূপে, বাঁয়ে সরার নিয়মও সামলায়) B-এর input 001 আর 000-এর সূত্র DIMACS ফাইলে লেখা হলো, তারপর ফাইল পড়ে PySAT-এর ভেতরের CaDiCaL 1.9.5 দিয়ে সমাধান। Satisfiable হলে solver-এর মডেল থেকে প্রতিটি ঘরের চিহ্ন পড়ে ছক ছাপা হয়, আর আলাদা কোডে মিলিয়ে দেখা হয় প্রতিটি সারি আগের সারি থেকে B-এর নিয়মে আসে কি না। শেষে দৈর্ঘ্য ০ থেকে ৪-এর সব ৩১টি input-এ মিলিয়ে দেখা হয়: SAT ⇔ B w গ্রহণ করে।

সত্যিকারের run (ডেস্কটপ, uv প্রকল্পে python-sat 1.9.dev23, ভেতরে CaDiCaL 1.9.5, Python 3.12.13; দুটিই MIT licence-এর। PySAT-এ কোনো usage-reporting বা telemetry নেই, installed package-এর code-এ network বা telemetry-র কোনো import খুঁজে না পেয়ে নিশ্চিত হয়েছি):

~/bazarghar-toc$ uv add python-sat
 + python-sat==1.9.dev23
~/bazarghar-toc$ uv run python run_tableau.py
python-sat 1.9.dev23 | solver: CaDiCaL 1.9.5

w = 001: tableau 5 rows x 8 cols, legal windows 239
  variables 6016 (cell vars 280), clauses 35329
  clauses per part: {'cell': 880, 'start': 8, 'accept': 1, 'move': 34440}
  solver says: SATISFIABLE
    # q 0 0 1 _ _ #
    # 0 q 0 1 _ _ #
    # 0 0 q 1 _ _ #
    # 0 0 1 Y _ _ #
    # 0 0 1 Y _ _ #
  every row follows the previous by B's rules: True

w = 000: tableau 5 rows x 8 cols, legal windows 239
  variables 6016 (cell vars 280), clauses 35329
  clauses per part: {'cell': 880, 'start': 8, 'accept': 1, 'move': 34440}
  solver says: UNSATISFIABLE

all w with |w| <= 4: SAT <=> B accepts w in 31/31 cases
~/bazarghar-toc$ head -4 tableau_001.cnf
c Cook-Levin tableau, toy NTM, rows=5 cols=8
p cnf 6016 35329
1 2 3 4 5 6 7 0
-1 -2 0

Input 001-এ solver SATISFIABLE বলেছে, আর তার মডেল থেকে পড়া ছকটি ছবি ৬০.১ আর অংশ ৩-এর stepper-এর হুবহু ছক: অর্থাৎ solver “জানে না” যে সে Turing machine-এর গণনা খুঁজছে, তবু সূত্রের গঠনই তাকে ঠিক সেই গণনা লিখতে বাধ্য করে। Input 000-এ UNSATISFIABLE: B-এর কোনো শাখা গ্রহণ করে না। শেষ লাইন দেখায়, ৩১টি input-এর প্রতিটিতে “সূত্র satisfiable” আর “B গ্রহণ করে” একই উত্তর দেয়, যা প্রমাণের ⇔-এর একটি সীমিত কিন্তু সত্যিকারের পরীক্ষা। ফাইলের প্রথম clause 1 2 3 4 5 6 7 0 হলো সারি ১, কলাম ১-এর “অন্তত একটি চিহ্ন” (φcell), আর -1 -2 0 বলে সেই ঘরে q0 আর Y একসঙ্গে নয়। ভুলে যাবেন না, ৩১টি ক্ষেত্রের মিল একটি পরীক্ষা, প্রমাণ নয়; প্রমাণ অংশ ৫-এ।

৭ · SAT থেকে 3SAT — clause ভাঙা আর Tseitin-এর কৌশল

প্রায় সব পরের reduction শুরু হয় 3SAT থেকে, কারণ প্রতিটি clause মাত্র তিন literal-এর হলে gadget বানানো সহজ (পর্ব ৫৯-এর 3SAT ≤p CLIQUE-এর মতো)। তাই দেখাতে হবে 3SAT-ও NP-complete. দুটি ধাপ।

ধাপ ১, φ-কে CNF করা। φcell, φstart আর φaccept আগে থেকেই CNF. φmove-এর প্রতিটি window-সূত্র ধ্রুবক আকারের ∧-এর ∨; distribution নিয়ম দিয়ে একে CNF করলে আকার বাড়ে, কিন্তু সেই বৃদ্ধিও শুধু N-এর ওপর নির্ভর করে, তাই ধ্রুবক। Sipser-এর বই এই পথে যায়। আমাদের কোডে ছিল আরেক পথ: প্রতিটি window-এর জন্য একটি নতুন চলক y. দুই পথেই CNF-SAT NP-complete.

সাধারণ সূত্রের জন্য সাবধান হতে হয়। (x1 ∧ y1) ∨ (x2 ∧ y2) ∨ ⋯ ∨ (xn ∧ yn)-কে distribution দিয়ে সমতুল্য CNF করলে 2nটি clause হয়: polynomial reduction-এর জন্য অচল। সমাধান Tseitin transformation (G. S. Tseitin-এর নামে, ১৯৬০-এর দশকের শেষের কাজ বলে পরিচিত): প্রতিটি উপ-সূত্রের জন্য একটি নতুন চলক, আর “নতুন চলক ⇔ উপ-সূত্র” শর্তের কয়েকটি ছোট clause. ফল রৈখিক আকারের CNF, যা মূল সূত্রের সমতুল্য নয় কিন্তু equisatisfiable: একটি satisfiable ⇔ অন্যটি satisfiable. Reduction-এর জন্য ঠিক এটুকুই দরকার।

ধাপ ২, clause ভাঙা। CNF-এর প্রতিটি clause-কে তিন-literal-এর clause-এ আনতে হবে।

লেমা ৭.১ (clause ভাঙা)

c = (l1 ∨ l2 ∨ ⋯ ∨ lk), k ≥ 4. নতুন চলক z1, …, zk−3 নিয়ে

c′ = (l1 ∨ l2 ∨ z1) ∧ (¬z1 ∨ l3 ∨ z2) ∧ ⋯ ∧ (¬zk−4 ∨ lk−2 ∨ zk−3) ∧ (¬zk−3 ∨ lk−1 ∨ lk).

তাহলে l-গুলোর প্রতিটি assignment-এর জন্য: c সত্য ⇔ z-এর এমন মান আছে যাতে c′ সত্য। k ≤ 3 হলে literal পুনরাবৃত্তি করে তিনটি করা হয়, যেমন (l1 ∨ l2) → (l1 ∨ l2 ∨ l1).

প্রমাণ:

  1. c′-এ k − 2টি clause, প্রতিটি ঠিক তিন literal-এর। clause নম্বর m-এ (m ≤ k − 3) zm আছে, আর m ≥ 2-এ ¬zm−1. — গঠন
  2. (⇒) ধরি li সত্য, আর li আছে clause নম্বর p-তে (p = max(1, i − 1), তবে k − 2-এর বেশি নয়)। zm = 1 নিন ঠিক তখন, যখন m < p. তাহলে p-এর আগের প্রতিটি clause তার zm-এ সত্য, clause p সত্য li-এ, আর পরের প্রতিটি clause তার ¬zm−1-এ সত্য, কারণ সেখানে z-এর মান 0. — একটি দিক
  3. (⇐) ধরি সব li মিথ্যা। প্রথম clause সত্য রাখতে z1 = 1 লাগবে; তাহলে দ্বিতীয়টিতে ¬z1 মিথ্যা, তাই z2 = 1; এভাবে শৃঙ্খলে zk−3 = 1. শেষ clause-এ তখন ¬zk−3, lk−1, lk তিনটিই মিথ্যা। তাই কোনো z-এ c′ সত্য নয়। — উল্টো দিক (contrapositive)
  4. প্রতিটি clause-এর z আলাদা, তাই সব clause ভাঙলে পুরো সূত্রের জন্যও: মূল CNF satisfiable ⇔ নতুন 3CNF satisfiable. নতুন সূত্রের আকার মূলের রৈখিক, আর লেখা polynomial সময়ের। ∎
1c  = x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x52c1 = x1 ∨ ¬x2 ∨ z13c2 = ¬z1 ∨ x3 ∨ z24c3 = ¬z2 ∨ x4 ∨ ¬x5
মান
x1…x5
c
z1 z2
c1 c2 c3
  1. মূল clause. c-তে পাঁচটি literal, তাই এটি 3SAT-এর instance নয়। k = 5, তাই লাগবে k − 3 = ২টি নতুন চলক আর k − 2 = ৩টি clause.
  2. প্রথম টুকরো। c1 = x1 ∨ ¬x2 ∨ z1. z1-কে পড়ুন “বাকি অংশের কোথাও একটি সত্য literal আছে” এমন একটি প্রতিশ্রুতি হিসেবে।
  3. মাঝের টুকরো। c2 = ¬z1 ∨ x3 ∨ z2. প্রতিশ্রুতি z1 দেওয়া থাকলে হয় x3 সত্য, নয় প্রতিশ্রুতিটি z2 হয়ে আরও ডানে যায়।
  4. শেষ টুকরো। c3 = ¬z2 ∨ x4 ∨ ¬x5. প্রতিশ্রুতি এখানে এসে শেষ হয়: z2 সত্য হলে x4 বা ¬x5-কে সত্য হতেই হবে।
  5. সত্য উদাহরণ। x = (0, 1, 0, 1, 1): একমাত্র x4 সত্য, তাই c সত্য। x4 আছে টুকরো ৩-এ, তাই প্রমাণের নিয়মে z1 = z2 = 1. যাচাই: c1 সত্য z1-এ, c2 সত্য z2-এ, c3 সত্য x4-এ।
  6. মিথ্যা উদাহরণ। x = (0, 1, 0, 0, 1): c-এর পাঁচটি literal-ই মিথ্যা। c1 বাধ্য করে z1 = 1, তারপর c2 বাধ্য করে z2 = 1, আর তখন c3-এর তিনটি literal-ই মিথ্যা। z-এর চারটি সম্ভাব্য মানের কোনোটিতেই তিন টুকরো একসঙ্গে সত্য নয়।

লেমার দাবি প্রতিটি assignment-এর জন্য, তাই ছোট k-এ তা সব assignment ঘুরে পরীক্ষা করা যায়। নিচের ব্লক stepper-এর উদাহরণ চালায়, তারপর k = 1 থেকে 8 পর্যন্ত প্রতিটি দৈর্ঘ্যের একটি clause নিয়ে x-এর সব 2k মানে মিলিয়ে দেখে: c সত্য ⇔ কোনো z-এ সব টুকরো সত্য।

from itertools import product
def to3(c, nv):             # split one clause; new variables are nv+1, nv+2, ...
    if len(c) <= 3: return [(c * 3)[:3]], nv                 # pad by repeating
    out, z = [[c[0], c[1], nv + 1]], nv + 1
    for lit in c[2:-2]:
        out.append([-z, lit, z + 1]); z += 1
    out.append([-z, c[-2], c[-1]])
    return out, z
true = lambda cl, val: any(val[abs(l)] == (l > 0) for l in cl)
print("x1 v -x2 v x3 v x4 v -x5  ->", to3([1, -2, 3, 4, -5], 5)[0])
val = {1: False, 2: True, 3: False, 4: True, 5: True}         # only x4 helps
for z1, z2 in product([False, True], repeat=2):
    ok = all(true(p, {**val, 6: z1, 7: z2}) for p in to3([1, -2, 3, 4, -5], 5)[0])
    print(f"  x4 only, z1={z1:d} z2={z2:d}: all three true = {ok}")
for k in range(1, 9):       # every assignment: clause true <=> some z works
    c = [v if v % 2 else -v for v in range(1, k + 1)]        # x1 v -x2 v x3 ...
    pieces, top = to3(c, k)
    agree = 0
    for xs in product([False, True], repeat=k):
        val = dict(zip(range(1, k + 1), xs))
        some_z = any(all(true(p, {**val, **dict(zip(range(k + 1, top + 1), zs))})
                         for p in pieces)
                     for zs in product([False, True], repeat=top - k))
        agree += (true(c, val) == some_z)
    print(f"k = {k}: {len(pieces)} clause(s), {top - k} new var(s), "
          f"agree on {agree}/{2 ** k} assignments")

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

x1 v -x2 v x3 v x4 v -x5  -> [[1, -2, 6], [-6, 3, 7], [-7, 4, -5]]
  x4 only, z1=0 z2=0: all three true = False
  x4 only, z1=0 z2=1: all three true = False
  x4 only, z1=1 z2=0: all three true = False
  x4 only, z1=1 z2=1: all three true = True
k = 1: 1 clause(s), 0 new var(s), agree on 2/2 assignments
k = 2: 1 clause(s), 0 new var(s), agree on 4/4 assignments
k = 3: 1 clause(s), 0 new var(s), agree on 8/8 assignments
k = 4: 2 clause(s), 1 new var(s), agree on 16/16 assignments
k = 5: 3 clause(s), 2 new var(s), agree on 32/32 assignments
k = 6: 4 clause(s), 3 new var(s), agree on 64/64 assignments
k = 7: 5 clause(s), 4 new var(s), agree on 128/128 assignments
k = 8: 6 clause(s), 5 new var(s), agree on 256/256 assignments

প্রথম লাইনে z1 = 6 আর z2 = 7 নম্বরের চলক, stepper-এর তিন টুকরোর হুবহু রূপ। শুধু x4 সত্য থাকলে চারটি z-মানের মধ্যে একটিই কাজ করে, z1 = z2 = 1, ঠিক প্রমাণের ধাপ ২-এর নিয়ম। শেষ আটটি লাইনে প্রতিটি k-এ k − 2টি টুকরো আর k − 3টি নতুন চলক (k ≤ 3-এ একটিই padded clause), আর প্রতিটি assignment-এ মিল। এখানে চিহ্নের একটি নির্দিষ্ট বিন্যাস নেওয়া হয়েছে; অন্য বিন্যাসে প্রমাণ একই থাকে, কারণ প্রমাণে literal-এর চিহ্নের কোনো ভূমিকা নেই।

শেষে আবার সত্যিকারের solver. একই uv প্রকল্পে ২,০০০টি এলোমেলো CNF (৪ থেকে ১২টি চলক, ১ থেকে ৭ literal-এর clause, স্থির seed) বানিয়ে ভাঙা হলো, আর মূল ও নতুন দুটি সূত্রই CaDiCaL দিয়ে সমাধান করা হলো:

সত্যিকারের run (একই প্রকল্প, python-sat 1.9.dev23, CaDiCaL 1.9.5):

~/bazarghar-toc$ uv run python to3sat.py
2000 random CNFs: same SAT/UNSAT answer 2000/2000; satisfiable 1429; 3CNF model also satisfies original 1429/1429
split [1, -2, 3, 4, -5] -> [[1, -2, 6], [-6, 3, 7], [-7, 4, -5]]

২,০০০টির প্রতিটিতে দুই সূত্রের উত্তর এক: ১,৪২৯টি satisfiable, বাকি ৫৭১টি unsatisfiable. আর প্রতিটি satisfiable ক্ষেত্রে 3CNF-এর মডেল থেকে শুধু মূল চলকগুলো নিলেই মূল সূত্র সত্য হয়, অর্থাৎ নতুন চলক শুধু সাহায্যকারী, উত্তর বদলায় না।

উপপাদ্য ৭.২

CNF-SAT আর 3SAT দুটিই NP-complete.

প্রমাণ: ১. দুটিই NP-তে: SAT-এর মতো একই verifier. ২. প্রতিটি L ∈ NP-এর জন্য L ≤p CNF-SAT: ধাপ ১-এর CNF রূপসহ Cook–Levin নির্মাণ। ৩. CNF-SAT ≤p 3SAT: লেমা ৭.১. ৪. ≤p transitive: f আর g যথাক্রমে p(n) আর q(n) সময়ের হলে g(f(w))-এর সময় p(n) + q(p(n)), যা আবার polynomial. তাই প্রতিটি L ≤p 3SAT. ∎

কেন 2SAT নয়? একই কৌশলে clause-কে দুই literal-এ ভাঙা যায় না: দুই-literal-এর টুকরোয় “প্রতিশ্রুতি” পরের দিকে নেওয়ার জায়গা থাকে না (অনুশীলন ২-এ একটি ভুল চেষ্টা)। আর 2SAT polynomial সময়ে সমাধান করা যায়, implication graph দিয়ে (পর্ব ৬১-এ)। SAT থেকে 2SAT-এ polynomial reduction পাওয়া গেলে P = NP প্রমাণ হতো; তাই P ≠ NP হলে এমন reduction নেই, তবে সেটিও এখনো প্রমাণিত নয়।

৮ · প্রথম NP-complete সমস্যার পরে — Karp, ফলাফল আর সীমা

Cook–Levin-এর আসল শক্তি তার পরে আসা সহজতায়। নতুন সমস্যা X NP-complete প্রমাণ করতে আর কখনো tableau লাগে না। দুটি কাজই যথেষ্ট: X ∈ NP দেখানো, আর কোনো পরিচিত NP-complete সমস্যা (যেমন 3SAT) থেকে X-এ polynomial reduction. কারণ ≤p transitive: প্রতিটি L ≤p 3SAT ≤p X. লক্ষ করুন দিক: পরিচিত কঠিন সমস্যা বাঁয়ে, নতুন সমস্যা ডানে।

Richard Karp ১৯৭২ সালের “Reducibility among combinatorial problems” প্রবন্ধে ঠিক এই পথে ২১টি পরিচিত সমস্যা NP-complete দেখান (Karp-এর ২১টি সমস্যা): clique, vertex cover, set cover, Hamiltonian circuit, chromatic number, knapsack, তিন-literal-এর SAT ইত্যাদি। এতে বোঝা গেল, NP-completeness দুর্লভ কোনো কৌতূহল নয়: অপারেশনস রিসার্চ, graph তত্ত্ব আর logic-এর বহু পুরোনো, বহু চেষ্টায়ও না-মেটা সমস্যা আসলে একই সমস্যার ছদ্মবেশ। Karp-এর reduction-এর ধারণা, polynomial-time mapping reduction, আজ Karp reduction নামেও পরিচিত। পুরো পরিবার, 3SAT থেকে CLIQUE, VERTEX-COVER, HAMPATH, SUBSET-SUM আর 3-COLOR পর্যন্ত, পরের পর্ব ৬১-এ।

যা প্রমাণিত

SAT, CNF-SAT আর 3SAT NP-complete. তাই এদের যেকোনো একটি P-তে থাকলে P = NP, আর P ≠ NP হলে কোনোটিই P-তে নেই।

যা অজানা

SAT-এর polynomial algorithm আছে কি না, অর্থাৎ P বনাম NP. বেশিরভাগ গবেষক মনে করেন P ≠ NP, কিন্তু তা প্রমাণিত নয় (পর্ব ৬৩)।

বাস্তবে যা ঘটে

SAT solver শিল্পের বহু বড় instance দ্রুত মেটায়, কারণ বাস্তব সূত্রের গঠন থাকে। এটি worst case-এর কাঠিন্যের সঙ্গে বিরোধ নয়; পর্ব ৭৩-এ বিস্তারিত।

একটি ব্যবহারিক শিক্ষা

NP-এর যেকোনো সমস্যা SAT-এ লেখা যায়। বাজারঘরের রাইডার-রুটিনের মতো সমস্যা তাই সরাসরি CNF-এ লিখে solver-এ দেওয়া একটি গুরুত্বপূর্ণ প্রকৌশল-কৌশল, যদিও বাস্তবে tableau নয়, সরাসরি এনকোডিং ব্যবহার হয়।

অ্যালগরিদমের দিক থেকে একই গল্প DSA কোর্সের পর্ব ৬৪-এ আছে; সেখানে reduction দেখা হয় প্রোগ্রাম হিসেবে, এখানে Turing machine আর প্রমাণের ভাষায়।

আরও গভীরে: Cook–Levin নির্মাণ এত সরল যে reduction-টি polynomial সময়ের চেয়ে অনেক দুর্বল যন্ত্রেও গণনা করা যায়, যেমন logarithmic জায়গায় (পর্ব ৬৪–৬৬-এর বিষয়)। Levin-এর প্রবন্ধে একটি “সার্বজনীন অনুসন্ধান” algorithm-ও ছিল, যা সব program পর্যায়ক্রমে চালিয়ে যেকোনো NP অনুসন্ধানে সবচেয়ে ভালো সম্ভাব্য সময়ের ধ্রুবক গুণের মধ্যে থাকে বলে পরিচিত; ধ্রুবকটি বিশাল। Tableau-র ধারণার সবচেয়ে গভীর উত্তরসূরি ১৯৯০-এর দশকের শুরুর PCP theorem (পর্ব ৭১), যা দেখায় NP-এর প্রমাণ এমনভাবে লেখা যায় যে মাত্র কয়েকটি এলোমেলো জায়গা পড়েই যাচাই সম্ভব।

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

  • Cook–Levin theorem বিবৃত করুন। SAT NP-complete: SAT ∈ NP আর প্রতিটি L ∈ NP-এর জন্য L ≤p SAT.
  • প্রমাণের রূপরেখা দিন। nk × nk tableau, চলক xi,j,s, φcell ∧ φstart ∧ φaccept ∧ φmove, legal 2 × 3 window, আকার O(n2k).
  • Window 2 × 3 কেন, 2 × 2 কেন নয়? এক ধাপে state এক ঘর সরে আর পাশের ঘর বদলাতে পারে; মাঝের ঘর আর দুই পাশ একসঙ্গে না দেখলে move যাচাই হয় না।
  • 3SAT NP-complete কীভাবে? 3SAT ∈ NP, আর k-literal-এর clause k − 3টি নতুন চলকে k − 2টি তিন-literal clause-এ ভেঙে CNF-SAT ≤p 3SAT.
  • নতুন সমস্যার NP-completeness প্রমাণের ছক? X ∈ NP, আর 3SAT ≤p X (উল্টো দিকে নয়), দুই দিকের ⇔ আর polynomial সময়সহ।

৯ · AI-এর যুগে Cook–Levin আর reduction নিয়ে কাজ

AI assistant এই বিষয়ে কয়েকটি ভুল বারবার করে। প্রথমত, reduction-এর দিক উল্টানো: “X NP-complete দেখাতে X-কে SAT-এ reduce করি” লিখে দেওয়া। এতে প্রমাণ হয় শুধু X ∈ NP-এর কাছাকাছি কিছু, কাঠিন্য নয়। দ্বিতীয়ত, tableau-র মাপ বা window-এর আকার ভুল বলা (2 × 2 window, বা সূত্রের আকার O(nk)). তৃতীয়ত, ইতিহাস বানানো: Cook আর Levin-এর সাল, প্রবন্ধের নাম, বা “Cook ২১টি সমস্যা দেখিয়েছিলেন”-এর মতো মিশ্রণ। চতুর্থত, ভাঙা clause-এ z-এর চিহ্ন ভুল বসানো, যা ছোট উদাহরণেই ধরা পড়ে। আর সবচেয়ে গুরুতর: “SAT solver দ্রুত চলে, তাই SAT আসলে সহজ” বা “P = NP প্রমাণিত হয়েছে”-এর মতো দাবি।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Reduction উল্টো দিকে (X ≤p SAT দিয়ে X-কে NP-hard বলা)লিখে দেখুন: পরিচিত NP-complete সমস্যা বাঁয়ে, নতুন সমস্যা ডানে আছে কি না
ভুল window, ভুল আকার, φ-এর কোনো অংশ বাদচার অংশ আর O(n2k) হিসাব নিজে গুনুন; ছোট যন্ত্রে encoder চালিয়ে clause গুনে মেলান
Clause ভাঙায় z-এর চিহ্ন বা শৃঙ্খল ভুলsplit_clause.py-এর মতো সব assignment ঘুরিয়ে “c সত্য ⇔ কোনো z কাজ করে” পরীক্ষা করুন
সূত্র “equivalent” বলা, যেখানে আসলে শুধু equisatisfiableনতুন চলক এলে equivalence থাকে না; একটি সত্য assignment নিয়ে দেখুন z-এর মান ছাড়া সূত্রের মানই নেই
বানানো ইতিহাস বা খোলা প্রশ্নকে মীমাংসিত বলাSipser, Arora–Barak বা মূল প্রবন্ধের নাম আর সাল নিজে মিলিয়ে নিন; P বনাম NP এখনো খোলা

AI-কে কাজে লাগানোর ভালো উপায়: নির্মাণ, দুই দিকের প্রমাণ, ছোট উদাহরণ আর একটি যাচাই-কোড একসঙ্গে চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্বে Cook–Levin theorem শিখছি (Sipser-এর রীতি)। ১. SAT ∈ NP-এর প্রমাণ verifier দিয়ে দাও, certificate-এর দৈর্ঘ্য আর যাচাইয়ের সময়সহ। ২. Tableau-র চার অংশ φ_cell, φ_start, φ_accept, φ_move-এর সূত্র লেখো, আর প্রতিটির আকার O(...) দিয়ে হিসাব করো। ৩. 2 × 3 legal window কেন যথেষ্ট, তার যুক্তি দাও; একটি legal আর একটি illegal window-এর উদাহরণ দাও। ৪. (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ∨ x6) clause-কে 3CNF-এ ভাঙো, আর একটি Python কোড দাও যা সব assignment ঘুরিয়ে দেখায় মূল clause সত্য ⇔ কোনো z-এ সব টুকরো সত্য। ৫. কোনো ইতিহাস বা সাল নিয়ে নিশ্চিত না হলে বলো, আর কোনো রেফারেন্স বানিয়ো না।

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

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

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

প্র ০১পুরো গণনার সঠিকতা কেন শুধু 2 × 3 মাপের ছোট জানালা দেখেই নিশ্চিত করা যায়? এই “স্থানীয়তা” Turing machine-এর কোন বৈশিষ্ট্য থেকে আসে, আর অন্য কোথায় একই ধারণা কাজে লাগে?

Turing machine-এর প্রতিটি ধাপ সংজ্ঞাগতভাবেই স্থানীয়। Head একটি ঘর পড়ে, সেখানে লেখে, আর এক ঘর সরে; বাকি tape অপরিবর্তিত থাকে। তাই এক configuration থেকে পরেরটিতে পার্থক্য সবসময় একটি ছোট এলাকায় সীমিত, আর সেই এলাকার মাপ যন্ত্রের ওপর নির্ভর করে না। 2 × 3 window ঠিক সেই এলাকা ধরার মতো চওড়া: মাঝের ঘরে state থাকলে তার দুই পাশ, যেখানে লেখা আর সরা ঘটে। পাশাপাশি window-গুলো দুটি করে কলাম ভাগ করে বলে আলাদা window আলাদা “গল্প” বলতে পারে না; স্থানীয় সামঞ্জস্য থেকেই বৈশ্বিক সঠিকতা আসে।

এই ধারণা তত্ত্বের বহু জায়গায় ফিরে আসে। পর্ব ৫৪-এর PCP প্রমাণে ডমিনোগুলো ঠিক এই স্থানীয় পরিবর্তন লিখেছিল, আর computation history দিয়ে CFG-এর universality-র প্রমাণে একটি PDA পাশাপাশি দুই configuration-এর ছোট অমিল খোঁজে। Tiling সমস্যায় (পর্ব ৫৫) প্রতিটি টালির শুধু পাশের টালির সঙ্গে মিল দেখা হয়, অথচ তাতেই পুরো গণনা লুকানো যায়। Circuit complexity-তে (পর্ব ৭০) একই tableau প্রতিটি ঘরের জন্য একটি ছোট circuit দিয়ে লেখা হয়, যা থেকে দেখা যায় polynomial সময়ের গণনা polynomial আকারের circuit-এ ধরে।

প্রকৌশলেও এর প্রতিধ্বনি আছে। Bounded model checking-এ একটি সফটওয়্যার বা hardware-এর k ধাপ একটি SAT সূত্রে লেখা হয়: প্রতি ধাপের জন্য চলকের একটি “সারি”, আর পাশাপাশি দুই সারির মধ্যে transition-এর নিয়ম। এটি আসলে বাস্তবের tableau. ঠিক যেমন ক্রিকেটের স্কোরখাতা প্রতি বলের পরিবর্তন মিলিয়ে পুরো ম্যাচ যাচাই করে, তেমনি স্থানীয় নিয়ম মানলে পুরো ইতিহাস ঠিক থাকে।

মূল উপলব্ধি: গণনার প্রতিটি ধাপ স্থানীয় বলেই পুরো গণনাকে ছোট, ধ্রুবক আকারের শর্তের ∧ দিয়ে লেখা যায়; Cook–Levin-এর সব শক্তি এই একটি পর্যবেক্ষণে।

প্র ০২Cook, Levin আর Karp-এর অবদান কীভাবে আলাদা? “একজন প্রথম NP-complete সমস্যা দেখালেন, আরেকজন দেখালেন সেগুলো সর্বত্র” কথাটি কতটা ঠিক?

Stephen Cook-এর ১৯৭১ সালের প্রবন্ধ দেখায়, nondeterministic polynomial সময়ের যেকোনো সমস্যা propositional logic-এর একটি প্রশ্নে রূপান্তর করা যায়। তাঁর reduction ছিল oracle-ভিত্তিক: একটি সমস্যা সমাধানে অন্যটিকে বহুবার প্রশ্ন করা চলে। তিনি কিছু সম্পর্কিত সমস্যার, যেমন subgraph isomorphism-এর, কাঠিন্যের কথাও আলোচনা করেন বলে জানা যায়। তবে প্রবন্ধটির তাৎক্ষণিক প্রভাব সীমিত ছিল, কারণ তখনো স্পষ্ট ছিল না এই শ্রেণিতে কত গুরুত্বপূর্ণ সমস্যা পড়ে।

Richard Karp ১৯৭২ সালে সেই প্রশ্নের উত্তর দেন। তিনি সরল, একবার-প্রশ্নের reduction (আজকের Karp reduction) দিয়ে SAT থেকে শুরু করে একুশটি সমস্যায় পৌঁছান, যাদের অনেকগুলো নিয়ে অপারেশনস রিসার্চ আর graph তত্ত্বের লোকেরা বছরের পর বছর লড়েছেন। এই তালিকাই NP-completeness-কে একটি কেন্দ্রীয় ধারণা বানায়, আর Garey ও Johnson-এর ১৯৭৯ সালের বই পরে শত শত সমস্যার তালিকা দেয়।

Leonid Levin তখনকার সোভিয়েত ইউনিয়নে স্বাধীনভাবে কাজ করছিলেন। রুশ গবেষণায় “perebor”, অর্থাৎ সব সম্ভাবনা ঘেঁটে দেখার প্রয়োজন এড়ানো যায় কি না, তা নিয়ে আগে থেকেই আগ্রহ ছিল বলে ইতিহাসবিদরা লেখেন। Levin অনুসন্ধান-সমস্যার ভাষায় কয়েকটি “সার্বজনীন” সমস্যা দেখান, যাদের মধ্যে tiling-এর মতো সমস্যা ছিল বলে উল্লেখ আছে; প্রকাশ ১৯৭৩ সালে, যদিও ফলটি আগেই আলোচনায় এসেছিল বলে জানা যায়। শীতল যুদ্ধের যুগে যোগাযোগ সীমিত থাকায় পশ্চিমে তাঁর কাজ পরিচিত হতে সময় লেগেছিল।

তাই “একজন প্রথমটি, আরেকজন সর্বত্র” কথাটি মোটামুটি ঠিক, তবে সরলীকৃত: Cook আর Levin দুজনেই প্রথম ধরনের ফল পান, আর Karp-এর অবদান শুধু তালিকা নয়, reduction-এর সেই সংজ্ঞা যা আজ মানক।

মূল উপলব্ধি: একটি তত্ত্ব কেন্দ্রীয় হয় দুই ধাপে: প্রথমে একটি সম্ভাবনার প্রমাণ, তারপর দেখানো যে তা বাস্তবের অসংখ্য সমস্যায় ঘটে; Cook–Levin প্রথমটি, Karp দ্বিতীয়টি।

প্র ০৩SAT NP-complete, তবু আধুনিক SAT solver লাখো চলকের শিল্প-সূত্র প্রায়ই সেকেন্ডে মেটায়। এতে কি P বনাম NP-এর কোনো সমাধানের ইঙ্গিত আছে?

না, আর পার্থক্যটি বোঝা জরুরি। NP-completeness একটি worst-case কথা: P ≠ NP হলে এমন কোনো algorithm নেই, যা সব সূত্রে polynomial সময়ে ঠিক উত্তর দেয়। এটি বলে না যে প্রতিটি নির্দিষ্ট সূত্র কঠিন। Hardware verification, planning বা scheduling থেকে আসা সূত্রে প্রচুর গঠন থাকে: অনেক clause ছোট, অনেক চলক অন্য চলক দিয়ে বাধ্য, আর বিরোধের কারণ প্রায়ই কয়েকটি চলকেই সীমিত। CDCL solver বিরোধ থেকে নতুন clause শেখে আর অনেক ধাপ পিছিয়ে লাফায়; এই গঠনই তাকে দ্রুত করে।

অন্যদিকে কঠিন সূত্রও সহজে বানানো যায়। এলোমেলো 3SAT-এ clause আর চলকের অনুপাত প্রায় 4.2-এর কাছাকাছি হলে সূত্র satisfiable আর unsatisfiable-এর সীমানায় থাকে, আর সেখানে solver-দের কষ্ট বেশি হয় বলে পরীক্ষায় দেখা যায়; সঠিক সীমানাটি নিয়ে গবেষণা হয়েছে, আর বড় k-এর জন্য তা প্রমাণিতও হয়েছে বলে জানা যায়। Pigeonhole সূত্রের মতো কিছু unsatisfiable সূত্রের যেকোনো resolution প্রমাণ exponential আকারের, যা Haken ১৯৮৫ সালে দেখান; CDCL solver মূলত resolution-এর ভেতরেই কাজ করে বলে এসব সূত্রে আটকে যায়।

বাজারঘরের দলের জন্য শিক্ষা দুই রকম। প্রথমত, NP-complete শুনে হাল ছেড়ে দেওয়ার কারণ নেই: রাইডার-রুটিন বা গুদামের বণ্টন solver-এ দিলে প্রায়ই চলে। দ্বিতীয়ত, গ্যারান্টি নেই: সমস্যা বড় হলে বা গঠন বদলালে হঠাৎ সময় বিস্ফোরিত হতে পারে, তাই timeout, সতর্কতা আর বিকল্প পথ রাখা উচিত। আর solver-এর গতি দিয়ে P = NP প্রমাণ হয় না, কারণ প্রমাণের জন্য সব input-এ polynomial সীমা দেখাতে হয়।

মূল উপলব্ধি: NP-completeness worst-case-এর কাঠিন্য বলে; বাস্তব সূত্রের গঠন solver-কে দ্রুত করে, কিন্তু তা কোনো সাধারণ polynomial গ্যারান্টি দেয় না।

প্র ০৪3SAT NP-complete, কিন্তু 2SAT polynomial. মাত্র এক literal-এর পার্থক্যে এত বড় ফারাক কেন? সহজ আর কঠিনের সীমানা নিয়ে গবেষণা কী বলে?

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

তিন-literal-এর clause (a ∨ b ∨ c)-এ একটি literal মিথ্যা হলেও বাকি দুটির মধ্যে বাছাই থেকে যায়। এই “অথবা”-র শাখা আর graph-এর পথে ধরা যায় না। Clause ভাঙার stepper-এ z চলক যে “প্রতিশ্রুতি” বহন করে, তার জন্য প্রতিটি টুকরোয় তিনটি জায়গা লাগে: আগের প্রতিশ্রুতি, একটি literal, আর পরের প্রতিশ্রুতি। দুই জায়গায় এই শৃঙ্খল চলে না, আর অনুশীলন ২ দেখায় সরল চেষ্টা কীভাবে ভেঙে পড়ে।

এই সীমানা একটি বড় তত্ত্বের অংশ। Thomas Schaefer ১৯৭৮ সালে Boolean constraint-এর একটি বড় পরিবারের জন্য দেখান, প্রতিটি সদস্য হয় P-তে, নয় NP-complete; মাঝামাঝি কিছু নেই। পরে অনেক বড় পরিসরের constraint সমস্যার জন্য একই রকম “dichotomy” অনুমান করা হয়, আর ২০১৭ সালের দিকে Bulatov আর Zhuk স্বাধীনভাবে তা প্রমাণ করেছেন বলে জানা যায়। অন্যদিকে Ladner-এর উপপাদ্য বলে, সাধারণ NP-তে P ≠ NP হলে মাঝামাঝি কঠিনতার সমস্যাও থাকে (পর্ব ৬৩); তাই dichotomy একটি বিশেষ কাঠামোর ফল, সব সমস্যার নয়।

মূল উপলব্ধি: 2SAT-এ প্রতিটি সিদ্ধান্তের ফল সরলরেখায় ছড়ায়, 3SAT-এ শাখা তৈরি হয়; সহজ আর কঠিনের সীমানা প্রায়ই এমন একটি কাঠামোগত পার্থক্যে।

প্র ০৫Cook–Levin-এর reduction polynomial, অথচ ছোট input-এও হাজার হাজার clause দেয়। তাহলে বাস্তবে কেউ কি সত্যিই tableau দিয়ে সমস্যা SAT-এ পাঠায়? তাত্ত্বিক polynomial আর ব্যবহারিক দক্ষতার সম্পর্ক কী?

সরাসরি tableau কেউ ব্যবহার করে না। অংশ ৫-এর JavaScript টেবিলেই দেখা গেছে, n = 10 আর k = 2-এ প্রায় এক কোটি চল্লিশ লাখ clause, যার বেশিরভাগ শুধু “দূরের ঘর কপি হয়” বলছে। Turing machine নিজেই একটি ধীর মডেল: একটি সাধারণ যোগ করতেও head-কে বহুবার আসা-যাওয়া করতে হয়, আর tableau সেই প্রতিটি ধাপের জন্য পুরো এক সারি চলক খরচ করে।

বাস্তবে সমস্যাকে সরাসরি SAT-এ এনকোড করা হয়। Sudoku-তে প্রতিটি (ঘর, অঙ্ক) জোড়ার জন্য একটি চলক, আর নিয়মগুলো সরাসরি clause. Hardware যাচাইয়ে circuit-এর প্রতিটি তারের জন্য একটি চলক, আর প্রতিটি gate-এর জন্য Tseitin-এর কয়েকটি clause. বাজারঘরের রাইডার-রুটিনে প্রতিটি (রাইডার, সময়, এলাকা) জোড়ার জন্য একটি চলক। এসব এনকোডিং tableau-র তুলনায় অনেক ছোট, কারণ তারা সমস্যার নিজের কাঠামো ব্যবহার করে। Discrete Mathematics কোর্সের পর্ব ৭৭-এ এমন বাস্তব এনকোডিং দেখানো হয়েছে।

তাহলে tableau-র মূল্য কোথায়? এটি একটি অস্তিত্বের প্রমাণ: প্রতিটি NP সমস্যার জন্য একটি polynomial এনকোডিং আছেই, আর তা যান্ত্রিকভাবে পাওয়া যায়। এই নিশ্চয়তা থেকেই বোঝা যায় SAT solver কেন এত সার্বজনীন tool: যে সমস্যার সমাধান যাচাই করা দ্রুত, তাকে সবসময় SAT-এ লেখা সম্ভব। Complexity তত্ত্বে “polynomial” শ্রেণিবিভাগের জন্য একটি স্থূল কিন্তু শক্ত মাপকাঠি; n4-এর সঙ্গে বিশাল ধ্রুবক ব্যবহারিকভাবে অচল হতে পারে, আর 2n/100 ছোট n-এ সহজ। পর্ব ৫৭-এর Cobham–Edmonds ধারণাও তাই একটি প্রস্তাব, প্রমাণিত নিয়ম নয়।

মূল উপলব্ধি: Tableau প্রমাণ করে যে polynomial এনকোডিং সবসময় আছে; বাস্তবের দক্ষ এনকোডিং খোঁজা আলাদা প্রকৌশল, যা সমস্যার নিজের কাঠামো কাজে লাগায়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। windows.py আর split_clause.py ব্লক বদলে নিজের উত্তর যাচাইও করতে পারেন।

  1. নির্মাণ: একটি nondeterministic Turing machine-এর Γ = {0, 1, ␣}, state q, r (r থামা state), আর একটিমাত্র নিয়ম δ(q, 0) = {(r, 1, L)}. বাঁ প্রান্তে বাঁয়ে সরার চেষ্টা করলে head জায়গায় থাকে। ওপরের সারি (ক) 1 q 0 আর (খ) q 0 1 হলে কোন কোন নিচের সারি নিয়ে window legal হয়, সব লিখুন।

    (ক) 1 q 0: q পড়ছে 0, 1 লিখে বাঁয়ে সরে। configuration …1 q 0… থেকে হয় …r 1 1…: state বাঁয়ের 1-এর আগে যায়, আর 0-এর জায়গায় 1. Window-এর তিন কলামে নিচে r 1 1. এটাই একমাত্র legal নিচের সারি।

    (খ) q 0 1: এবার q-এর বাঁয়ের ঘরটি window-এর বাইরে, আর সরার পরে সেই ঘরের চিহ্ন (ধরি c) q-এর পুরোনো কলামে আসে, state যায় তারও বাঁয়ে: নিচে c 1 1, যেখানে c ∈ {0, 1, ␣}, অর্থাৎ 0 1 1, 1 1 1, ␣ 1 1. আর q যদি সারির প্রথম ঘরে থাকে (বাঁয়ে #), head জায়গায় থাকে: নিচে r 1 1. মোট চারটি: 0 1 1, 1 1 1, ␣ 1 1, r 1 1. বাঁয়ের window-টি নিশ্চিত করবে c-এর আগে সত্যিই r বসেছে। (scratch-এ windows-এর মতো একটি generator দিয়ে এই চারটিই পেয়েছি।)

  2. প্রমাণে ভুল খুঁজুন: একজন লিখেছেন: “SAT ≤p 2SAT, তাই P = NP. প্রমাণ: প্রতিটি clause (a ∨ b ∨ c)-কে নতুন চলক z দিয়ে (a ∨ z) ∧ (¬z ∨ b) ∧ (¬z ∨ c)-এ বদলান; লম্বা clause একইভাবে। সবকটি টুকরো দুই literal-এর, আর রূপান্তর polynomial.” ভুলটি কোথায়? একটি নির্দিষ্ট assignment দিয়ে দেখান।

    ভুল: রূপান্তরটি satisfiability রক্ষা করে না, তাই এটি reduction-ই নয়। (¬z ∨ b) ∧ (¬z ∨ c) মানে “z সত্য হলে b আর c দুটিই সত্য”, অথচ দরকার ছিল “অন্তত একটি”।

    উদাহরণ: a = 0, b = 1, c = 0. মূল clause সত্য (b-তে)। নতুন সূত্রে (a ∨ z)-এর জন্য z = 1 লাগে; তখন (¬z ∨ c) = 0 ∨ 0 = মিথ্যা। z = 0 নিলে (a ∨ z) মিথ্যা। কোনো z-এ সত্য নয়। (a, b, c) = (0, 0, 1)-ও একই রকম প্রতি-উদাহরণ; scratch-এ আটটি মান ঘুরিয়ে ঠিক এই দুটিই অমিল পেয়েছি।

    শিক্ষা: প্রতিটি reduction-এ দুই দিক (⇒ আর ⇐) আলাদা করে প্রমাণ করতে হয়। আর 2SAT ∈ P বলে এমন সঠিক reduction পাওয়া গেলে P = NP হতো; সেটি কেউ পায়নি, তবে তা অসম্ভব বলে প্রমাণও হয়নি, কারণ সেটিই P বনাম NP প্রশ্ন।

  3. Trace আর গণনা: খেলনা যন্ত্র B (অংশ ৩) আর input w = 10. এই পর্বের রীতিতে ছকের মাপ কত (সারি n + 2, কলাম n + 5)? গ্রহণকারী tableau-র প্রতিটি সারি লিখুন। কতগুলো x-চলক, φcell-এ কতগুলো clause, আর কতগুলো window-জায়গা? গ্রহণকারী tableau কি একটিই?

    মাপ: n = 2, তাই ৪টি সারি আর ৭টি কলাম। সারি ১: # q0 1 0 ␣ ␣ #. প্রথম ঘরেই 1, আর এখানে Y বেছে নিলে সারি ২: # 1 Y 0 ␣ ␣ #. তারপর কপি: সারি ৩ আর ৪ একই।

    গণনা: ঘর ৪ × ৭ = ২৮, প্রতিটিতে ৭টি চলক: ১৯৬টি x-চলক। প্রতি ঘরে ১ + C(7, 2) = ১ + ২১ = ২২টি clause, তাই φcell-এ ২৮ × ২২ = ৬১৬টি। Window-জায়গা (৪ − ১) × (৭ − ২) = ১৫টি।

    একটিই কি? হ্যাঁ। অন্য শাখা q0 নিয়ে 0 পেরোয়, তারপর ␣ পড়ে X-এ বর্জন; সেখানে কোথাও Y নেই, তাই φaccept মিথ্যা। Scratch-এ CaDiCaL দিয়ে এই ছকটি পেয়ে তাকে নিষিদ্ধ করে আবার চালালে solver UNSAT বলেছে, অর্থাৎ দ্বিতীয় কোনো গ্রহণকারী ছক নেই।

  4. প্রমাণ: প্রমাণ করুন: (ক) ≤p transitive; (খ) 3SAT ∈ P হলে P = NP. প্রতিটি ধাপে কোন সংজ্ঞা বা উপপাদ্য ব্যবহার করছেন, লিখুন।

    (ক) ১. A ≤p B f দিয়ে, B ≤p C g দিয়ে; f-এর সময় p(n), g-এর q(n), দুটিই polynomial (সংজ্ঞা)। ২. h(w) = g(f(w)). f(w) লিখতে p(n) সময় লাগে বলে |f(w)| ≤ p(n), তাই g-এর সময় ≤ q(p(n)); মোট p(n) + q(p(n)), polynomial-এর composition polynomial. ৩. w ∈ A ⇔ f(w) ∈ B ⇔ g(f(w)) ∈ C. তাই A ≤p C. ∎

    (খ) ১. P ⊆ NP সবসময় সত্য (পর্ব ৫৮)। ২. L ∈ NP নিন। Cook–Levin আর উপপাদ্য ৭.২ থেকে L ≤p 3SAT, একটি f দিয়ে। ৩. 3SAT-এর polynomial decider D ধরে নিন। L-এর decider: w-এর ওপর f(w) গণনা করুন, তারপর D চালান। সময় p(n) + q(p(n)), polynomial (ক-এর একই হিসাব)। ৪. তাই L ∈ P, অর্থাৎ NP ⊆ P, আর P = NP. ∎ এটি দিকের নিয়মের প্রয়োগ: A ≤p B আর B ∈ P হলে A ∈ P.

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

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

ক্রমSAT NP-complete, Cook–Levin প্রমাণের এই ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. L ∈ NP নিন, আর একটি NTM N যা L-কে nk সময়ে decide করে
  2. Input w থেকে nk × nk tableau-র চলক xi,j,s ঠিক করুন
  3. φcell, φstart, φaccept আর legal window দিয়ে φmove লিখুন
  4. দেখান φ-এর আকার O(n2k log n) আর তা polynomial সময়ে লেখা যায়
  5. দুই দিকে প্রমাণ করুন: w ∈ L ⇔ φ satisfiable
  6. SAT ∈ NP মিলিয়ে সিদ্ধান্ত: SAT NP-complete

Cook–Levin theorem ঠিক কী বলে?

  • SAT polynomial সময়ে সমাধান করা যায়
  • SAT NP-hard, কিন্তু NP-তে নেই
  • SAT NP-তে আছে, আর NP-এর প্রতিটি language polynomial সময়ে SAT-এ reduce হয়
  • NP-এর প্রতিটি language exponential সময়ে SAT-এ reduce হয়

Cook–Levin প্রমাণে চলক xi,j,s সত্য হওয়ার মানে কী?

  • যন্ত্রটি ধাপ i-এ state j থেকে state s-এ যায়
  • Tableau-র সারি i, কলাম j-এর ঘরে চিহ্ন s বসেছে
  • সূত্রের clause i-এর literal j-এর মান s
  • Head ধাপ i-এ কলাম j-এ আছে আর s পড়ছে, আর কিছু নয়

একটি NTM-এর নিয়ম: δ(q, 0) = {(q, 0, R)}, δ(q, 1) = {(q, 1, R), (Y, 1, R)}, যেখানে Y গ্রহণের state. Tableau-র দুই সারির কোন 2 × 3 window legal? (ওপরের সারি / নিচের সারি)

  • 0 q 1 / 0 0 Y
  • 0 q 1 / 0 Y 1
  • 0 q 1 / q 0 1
  • 0 q 1 / 0 1 Y

একটি NTM nk সময়ে চলে। Cook–Levin নির্মাণে nk × nk tableau থেকে তৈরি সূত্রের আকার (চলকের নাম লেখার log n বিট বাদ দিলে) কত?

  • O(n2k)
  • O(nk)
  • O(2n)
  • O(n4k)

3SAT-এর জন্য clause (a ∨ b ∨ c ∨ d)-কে নতুন চলক z দিয়ে ভাঙার সঠিক রূপ কোনটি?

  • (a ∨ b ∨ z) ∧ (z ∨ c ∨ d)
  • (a ∨ b ∨ z) ∧ (¬z ∨ c ∨ ¬d)
  • (a ∨ b ∨ z) ∧ (¬z ∨ c ∨ d)
  • (a ∨ z) ∧ (¬z ∨ b)

একটি নতুন সমস্যা X NP-complete প্রমাণ করতে, X ∈ NP দেখানোর পরে কোন reduction দেখাতে হয়? (A ≤p B মানে A-কে polynomial সময়ে B-তে reduce করা।)

  • X ≤p SAT
  • 3SAT ≤p X
  • 2SAT ≤p X
  • X ≤p 2SAT

শব্দকোষ

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

মনে রাখুন

  1. Cook–Levin: SAT NP-complete. SAT ∈ NP (assignment-ই certificate), আর প্রতিটি L ∈ NP ≤p SAT.
  2. Tableau: nk × nk ছক, সারি = configuration; চলক xi,j,s; φ = φcell ∧ φstart ∧ φaccept ∧ φmove.
  3. Legal 2 × 3 window: এক ধাপের পরিবর্তন স্থানীয়, তাই সব window legal হলে প্রতিটি সারি আগের সারি থেকে বৈধ ধাপে আসে। আকার O(n2k), reduction polynomial.
  4. Clause ভাঙা: k literal → k − 2টি তিন-literal clause, k − 3টি নতুন চলক; equisatisfiable, তাই 3SAT NP-complete. সাধারণ সূত্রে Tseitin.
  5. নতুন X-এর জন্য: X ∈ NP আর 3SAT ≤p X. SAT-এর polynomial algorithm মানে P = NP, যা এখনো খোলা প্রশ্ন।

পরের পর্বে: 3SAT থেকে শুরু করে NP-complete সমস্যার পুরো পরিবার: clique, vertex cover, Hamiltonian path, subset sum আর 3-coloring, প্রতিটির gadget আর বাজারঘরের ডেলিভারি সমস্যায় তাদের ছদ্মবেশ।

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

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