NP-completeness ও Cook-Levin Theorem — একটা সমস্যা যা সবাইকে বহন করে

আগে এটা বুঝি

১৯৬০-এর দশকের শেষে computer scientist-রা একটা অস্বস্তিকর প্যাটার্ন লক্ষ্য করছিলেন। Boolean satisfiability (SAT), graph coloring, Hamiltonian path, vertex cover, subset sum, integer programming, traveling salesman — সম্পূর্ণ ভিন্ন ভিন্ন ক্ষেত্র থেকে আসা এই সমস্যাগুলোর প্রতিটার জন্যই সবচেয়ে মেধাবী গবেষকরা বছরের পর বছর চেষ্টা করেও কোনো polynomial-time algorithm খুঁজে পাননি। অথচ প্রতিটার জন্যই certificate যাচাই তুচ্ছরকম সহজ।

এটা কি কাকতালীয়? নাকি এই সমস্যাগুলো গোপনে একই সমস্যা, ভিন্ন ভিন্ন পোশাকে?

১৯৭১ সালে Stephen Cook একটা বিস্ময়কর উত্তর দিলেন — আর ঠিক একই সময়ে, পর্দার আড়ালে সোভিয়েত ইউনিয়নে, Leonid Levin স্বাধীনভাবে একই ফলাফলে পৌঁছালেন (পশ্চিমা world-এ জানতে আরো কয়েক বছর লেগেছিল, Iron Curtain-এর কারণে)। উত্তরটা হলো: হ্যাঁ, এরা গোপনে সম্পর্কিত — এবং সেই সম্পর্কটা প্রমাণযোগ্য, নির্দিষ্ট, আর যান্ত্রিকভাবে ব্যবহারযোগ্য।

SAT-কে একটা “universal translator” হিসেবে ভাবুন। প্রতিটা NP সমস্যাকে SAT-এর ভাষায় অনুবাদ করা যায় — polynomial সময়ে, কোনো তথ্য না হারিয়ে। এর মানে: যদি কখনো কেউ SAT-এর জন্য একটা polynomial algorithm খুঁজে পান, প্রতিটা NP সমস্যা — গ্রাফ কালারিং থেকে শুরু করে প্রোটিন ফোল্ডিং পর্যন্ত — মুহূর্তে polynomial সময়ে সমাধানযোগ্য হয়ে যাবে। এটাই P বনাম NP-এর পুরো ওজনটা একটা মাত্র সমস্যার কাঁধে তুলে দেয়।

আজ আমরা দেখব এই “অনুবাদ” যন্ত্রটা — যাকে বলে polynomial-time reduction — ঠিক কীভাবে কাজ করে, আর কীভাবে এই একটা যন্ত্র দিয়ে গত ৫০ বছরে হাজার হাজার সমস্যা NP-complete প্রমাণিত হয়েছে।

মূল ধারণা

Reduction — সমস্যা থেকে সমস্যায় যাওয়ার সেতু

একটা polynomial-time (Karp) reduction A ≤_p B-কে সংজ্ঞায়িত করা হয়: একটা function f আছে যা A-এর যেকোনো instance x-কে B-এর একটা instance f(x)-এ রূপান্তর করে, যেন

x \in A \iff f(x) \in B

এবং f নিজে polynomial time-এ গণনাযোগ্য।

স্বজ্ঞাতভাবে: “A সমাধান করতে চাইলে, ইনপুটটাকে f দিয়ে বদলে B-এর একটা solver-কে দিন — উত্তর সরাসরি চলে আসবে।” A ≤_p B পড়ুন “A B-এর চেয়ে সহজ বা সমান কঠিন” (B-এর জন্য একটা polynomial algorithm থাকলে সেটা দিয়ে A-ও সমাধান হয়ে যায় — শুধু f প্রয়োগ করে তারপর B-এর solver চালিয়ে)।

দিক নিয়ে সবচেয়ে বেশি ভুল হয়

A ≤_p B মানে “A কে B-তে রূপান্তর করা যায়” — A সমাধান করার জন্য B-এর একটা solver ধার করা যায়। এটা বলছে না B সহজ; এটা বলছে A-ই সহজ বা সমান কঠিন (B-এর তুলনায়)।

তাই: A-কে NP-complete প্রমাণ করতে হলে জানা একটা NP-complete সমস্যাকে A-তে reduce করুন (\text{known} \le_p A), A-কে জানা সমস্যায় নয়। দিকটা উল্টে ফেললে পুরো প্রমাণ অর্থহীন হয়ে যায় — এটাই ছাত্রদের সবচেয়ে সাধারণ ভুল।

NP-hard এবং NP-complete

NP-hard: একটা সমস্যা L NP-hard যদি NP-এর প্রতিটা সমস্যা L-এ polynomial-time reduce করা যায়:

\forall A \in \mathbf{NP} : A \le_p L

লক্ষ্য করুন — L নিজেকে NP-তে থাকতে হবে এমন কোনো শর্ত নেই। L আরো কঠিন হতে পারে (PSPACE-hard বা তার চেয়েও কঠিন সমস্যাও NP-hard, কারণ NP ⊆ PSPACE)।

NP-complete: L NP-complete যদি দুটো শর্ত একসাথে সত্য:

L \in \mathbf{NP} (নিজে NP-তে আছে — অর্থাৎ যাচাই করাও সহজ)
L NP-hard (প্রতিটা NP সমস্যা এতে reduce হয়)

NP-complete সমস্যাগুলোই NP-এর “সবচেয়ে কঠিন” সদস্য — তারা NP-এর ভেতরেই আছে, কিন্তু বাকি সবাইকে বহন করছে।

                    ┌─────────────────────────────┐
                    │          NP-hard             │
                    │   (NP-এর সবকিছু এখানে         │
                    │    reduce হয়; এর বাইরেও        │
                    │    অনেক কঠিন সমস্যা থাকতে পারে)│
                    │        ┌─────────────┐        │
        ┌───────────┼────────┤ NP-complete │        │
        │    NP     │        │ (এই দুই সেটের │        │
        │           │        │ intersection) │        │
        │           │        └─────────────┘        │
        │   (P সহ)  │                                │
        └───────────┼────────────────────────────────┘
                     │
             TQBF, generalized-chess (এইসব শুধু
             NP-hard, NP-এর বাইরে — PSPACE-hard)

NP, NP-hard, NP-complete-এর সম্পর্ক — NP-complete হলো দুই সেটের intersection।

Reduction-এর transitivity — কেন এক ইট দিয়ে দালান তৈরি হয়

Reduction-এর সবচেয়ে গুরুত্বপূর্ণ property: transitivity।

A \le_p B \ \wedge\ B \le_p C \implies A \le_p C

প্রমাণ সহজ — যদি f A-কে B-তে বদলায় আর g B-কে C-তে বদলায়, তাহলে g \circ f (আগে f, তারপর g) A-কে সরাসরি C-তে বদলায়, আর দুইটা polynomial function-এর composition-ও polynomial।

এই একটা property-ই পুরো NP-completeness-এর “domino” কাঠামোটা সম্ভব করে। একবার SAT-কে NP-complete প্রমাণ করা গেলে (Cook-Levin, পরের অংশে), শুধু একটা করে reduction \text{SAT} \le_p X দেখালেই X-ও NP-hard প্রমাণিত (আর X \in NP দেখাতে পারলে NP-complete)। কারণ: NP-এর যেকোনো A-এর জন্য A \le_p \text{SAT} (SAT-এর NP-hardness থেকে), আর \text{SAT} \le_p X (নতুন reduction থেকে), তাই transitivity দিয়ে A \le_p X। A যথেচ্ছ ছিল, তাই X-ও NP-hard।

এইভাবে একটা মাত্র “প্রথম” NP-complete সমস্যা (SAT) থেকে, প্রতিটা নতুন প্রমাণ শুধু একটা reduction যোগ করে — পুরো ৫০ বছরের প্রমাণকাজ আবার শুরু করতে হয় না। এখন পর্যন্ত ৩০০০-এর বেশি সমস্যা এই শৃঙ্খলে NP-complete প্রমাণিত।

ভেতরে কী ঘটছে

Cook-Levin theorem — বিবৃতি

Cook-Levin Theorem (1971): SAT — একটা Boolean formula (CNF আকারে দেওয়া) satisfiable কি না — NP-complete।

এটাই সেই “প্রথম ইট”। তাৎপর্য: SAT শুধু NP-তে (certificate = satisfying assignment, O(n)-এ যাচাই) তা নয় — প্রতিটা NP সমস্যা SAT-এ polynomial সময়ে reduce করা যায়। SAT-এর জন্য কোনো polynomial algorithm খুঁজে পেলেই P = NP প্রমাণিত হয়ে যাবে।

প্রমাণ sketch — computation tableau

প্রমাণের কৌশলটা চমৎকার: যেকোনো NP সমস্যার verifier-এর computation-কে সরাসরি একটা Boolean formula হিসেবে “লিখে ফেলা”।

ধরুন L \in \mathbf{NP}, একটা verifier TM V আছে যা certificate c সহ input x (দৈর্ঘ্য n) পেয়ে p(n) ধাপে সিদ্ধান্ত নেয়। V-এর একটা computation history-কে একটা tableau — p(n) × p(n) আকারের একটা গ্রিড — হিসেবে কল্পনা করুন: i-তম সারি হলো V-এর i-তম ধাপের পরে tape-এর পুরো অবস্থা।

          cell 0   cell 1   cell 2   ...   cell p(n)
step 0:   [x_1]    [x_2]    [ _ ]    ...   [ _ ]      ← initial config
step 1:   [x_1]    [q_5]    [ _ ]    ...   [ _ ]      ← head সরল, state বদলাল
step 2:   [x_1]    [a]      [q_2]    ...   [ _ ]
  ...       ...      ...      ...    ...     ...
step p(n): [.]      [.]      [.]     ...  [accept]   ← শেষ সারি — accept state থাকতেই হবে

Computation tableau — প্রতিটা সারি একটা মুহূর্তের tape state, প্রতিটা সেল একটা Boolean variable-এর সেট দিয়ে এনকোড করা।

প্রতিটা সেল (i, j)-এর জন্য একগুচ্ছ Boolean variable x_{i,j,s} তৈরি করা হয় — “step i-তে, cell j-এ, প্রতীক/state s আছে কি না” (sাধারণত alphabet + state-এর প্রতিটা সম্ভাব্য মানের জন্য একটা variable)। মোট variable সংখ্যা O(p(n)^2 \cdot |\Gamma|) — যেহেতু p(n) polynomial আর alphabet ধ্রুবক আকারের, এটাও polynomial।

তারপর একটা বড় CNF formula \phi_x বানানো হয় নিচের clause-গুচ্ছ দিয়ে (প্রতিটা গুচ্ছ polynomial সংখ্যক clause):

প্রতিটা সেলে ঠিক একটা মান — প্রতিটা (i,j)-এর জন্য “অন্তত একটা” আর “সর্বোচ্চ একটা” symbol/state clause
Initial row সঠিক — সারি 0 অবশ্যই x আর c-এর (যেটাও variable হিসেবে ধরা হয় — এখানেই \exists c অংশটা formula-র কাঠামোতে ঢুকে যায়) সঠিক এনকোডিং
প্রতিটা 2×3 window বৈধ transition মেনে চলে — V-এর transition function অনুযায়ী প্রতিটা স্থানীয় পরিবর্তন সঠিক কি না (এটাই সবচেয়ে বেশি clause তৈরি করে, কিন্তু প্রতিটা window ধ্রুবক আকারের বলে সংখ্যা এখনো O(p(n)^2))
শেষ সারিতে accept state আছে — একটা single clause যা বলে “কোনো না কোনো সেলে accept-state symbol আছে”

দাবি: \phi_x satisfiable \iff কোনো certificate c দিয়ে V x-কে accept করে \iff x \in L।

কারণ: \phi_x-এর যেকোনো satisfying assignment আসলে একটা বৈধ, accepting computation history এনকোড করে (শর্ত ১-৪ ঠিক এটাই নিশ্চিত করে) — আর সেই history-র সারি 0-এর অংশ থেকে certificate c সরাসরি পড়া যায়।

গঠনের সময় polynomial: \phi_x-এর variable ও clause সংখ্যা O(p(n)^2) (ধ্রুবক-factor সহ), আর প্রতিটা clause ধ্রুবক সময়ে লেখা যায় — তাই পুরো formula polynomial সময়ে গণনাযোগ্য। এটাই reduction-এর সংজ্ঞা পূরণ করে: L \le_p \text{SAT}, আর L ছিল যেকোনো NP সমস্যা — তাই SAT NP-hard। আগে থেকেই জানি SAT \in NP, তাই SAT-এর NP-completeness প্রমাণিত ∎

এই প্রমাণের গভীর বার্তা

Cook-Levin theorem আসলে বলছে: কম্পিউটেশন নিজেই একটা Boolean formula-য় এনকোড করা যায় — “কী গণনা হচ্ছে” প্রশ্নটাকে “কোন formula satisfiable” প্রশ্নে রূপান্তর করা যায়, কোনো তথ্য না হারিয়ে। এই observation-টাই পরবর্তীতে circuit complexity, cryptographic proof system (zero-knowledge proof), আর এমনকি modern SNARK-ভিত্তিক blockchain প্রযুক্তির (যেখানে “আমি একটা গণনা সঠিকভাবে করেছি” তা প্রমাণ করতে গণনাটাকে প্রথমে একটা Boolean/arithmetic circuit-এ রূপান্তর করা হয়) ভিত্তি হয়ে দাঁড়িয়েছে।

উদাহরণ

Reduction ১ — SAT থেকে 3-SAT

SAT-এ clause-এর দৈর্ঘ্য যেকোনো হতে পারে; 3\text{-}SAT-এ প্রতিটা clause-এ ঠিক ৩টা literal থাকতেই হবে। দেখাই \text{SAT} \le_p 3\text{-}SAT।

কৌশল: যেকোনো clause-কে দৈর্ঘ্য অনুযায়ী রূপান্তর করুন, প্রয়োজনে নতুন auxiliary variable যোগ করে।

ধরুন একটা clause (l_1 \vee l_2 \vee l_3 \vee l_4 \vee l_5) — ৫টা literal। নতুন variable y_1, y_2 যোগ করে এটাকে ভাঙুন:

(l_1 \vee l_2 \vee y_1) \wedge (\neg y_1 \vee l_3 \vee y_2) \wedge (\neg y_2 \vee l_4 \vee l_5)

কেন সমতুল্য? যদি মূল clause satisfiable হয় (কোনো l_i true), তাহলে y_1, y_2-কে উপযুক্তভাবে সেট করে (মূল l_i-এর অবস্থান অনুযায়ী) সবগুলো নতুন clause satisfy করা যায় — যেমন l_1 true হলে y_1 = \text{true} দিয়ে প্রথম clause সরাসরি, বাকিগুলো y_1, y_2 দিয়ে “chain” এর মতো পরের দিকে ঠেলে দেওয়া যায়। উল্টো দিকে, যদি সব l_i false হয়, তাহলে y_1, y_2-এর কোনো মানেই তিনটা নতুন clause একসাথে satisfy করা সম্ভব নয় (এটা truth table দিয়ে সরাসরি যাচাইযোগ্য)।

সাধারণভাবে, k-literal clause-কে k-2 টা 3-literal clause-এ ভাঙা যায় k-3 টা নতুন variable দিয়ে — মোট formula আকার শুধু রৈখিকভাবে বাড়ে। 1- বা 2-literal clause-এর জন্যও সহজ প্যাডিং আছে (dummy literal পুনরাবৃত্তি করে ৩-এ আনা)।

ধাপ	Clause
মূল	`(l₁ ∨ l₂ ∨ l₃ ∨ l₄ ∨ l₅)`
ভাঙার পর	`(l₁ ∨ l₂ ∨ y₁) ∧ (¬y₁ ∨ l₃ ∨ y₂) ∧ (¬y₂ ∨ l₄ ∨ l₅)`
variable বৃদ্ধি	`+2` (`y₁, y₂`)
clause বৃদ্ধি	`1 → 3`

একটা ৫-literal clause ভাঙার ধাপ — প্রতিটা নতুন clause ঠিক ৩টা literal রাখে।

যেহেতু প্রতিটা clause স্বাধীনভাবে (ধ্রুবক সময়ে) রূপান্তরিত হয়, পুরো formula-র রূপান্তর polynomial সময়ে — \text{SAT} \le_p 3\text{-SAT} প্রতিষ্ঠিত। (3\text{-SAT} \in NP তুচ্ছ — certificate একই রকম assignment। তাই 3\text{-SAT} নিজেও NP-complete।)

Reduction ২ — 3-SAT থেকে Independent Set

\text{INDEPENDENT-SET}: একটা graph G আর সংখ্যা k দেওয়া আছে — G-তে k-টা node আছে কি যাদের মধ্যে কোনো edge নেই (কোনো দুটো পরস্পর প্রতিবেশী নয়)?

Reduction: একটা 3\text{-SAT} instance \phi (m-টা clause, প্রতিটায় ৩টা literal) দেওয়া থাকলে:

প্রতিটা clause-এর জন্য একটা triangle — clause (l_1 \vee l_2 \vee l_3)-এর প্রতিটা literal একটা node, আর একই clause-এর তিনটা node পরস্পর edge দিয়ে যুক্ত (triangle) — এই তিনটা থেকে সর্বোচ্চ একটাই independent set-এ থাকতে পারে (কারণ যেকোনো দুইটা edge দিয়ে যুক্ত)।
Complementary literal-দের মধ্যে edge — x_i আর \neg x_i (যেকোনো clause-এ থাকুক না কেন) সব জায়গায় edge দিয়ে যুক্ত — নিশ্চিত করে একটা variable আর তার negation একসাথে independent set-এ থাকতে না পারে।
k = m (clause সংখ্যা)।

Clause 1 triangle:        Clause 2 triangle:
   x₁ ── x₂                  ¬x₁ ── x₂
    \    /                     \    /
     ¬x₃                        x₃

আন্তঃ-clause complementary edges:
   x₁ (clause 1) ── ¬x₁ (clause 2)   [same variable, opposite sign]
  ¬x₃ (clause 1) ──  x₃ (clause 2)   [same variable, opposite sign]

satisfying assignment x₁=T, x₂=এমন কিছু, x₃=F হলে:
  clause 1-এ x₁ true → x₁ node বাছুন
  clause 2-এ x₃ true → x₃ node বাছুন
  {x₁ (clause1), x₃ (clause2)} — কোনো edge নেই এদের মধ্যে, |set|=2=k ✓

একটা concrete উদাহরণ — φ = (x₁ ∨ x₂ ∨ ¬x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃), k = 2।

Correctness — দুই দিক:

Satisfiable \implies independent set of size k: প্রতিটা clause-এ অন্তত একটা true literal আছে (satisfying assignment ধরে); প্রতিটা clause-এর triangle থেকে সেই true literal-এর node বেছে নিন — মোট m = k-টা node। একই triangle-এর ভেতরে দুটো বাছা হয়নি (প্রতি triangle থেকে ঠিক একটা)। আর দুই ভিন্ন triangle থেকে বাছা node দুটো একে অপরের negation হতে পারে না (কারণ দুটোই true হিসেবে বাছা হয়েছে, একই assignment-এর অধীনে — x_i true হলে \neg x_i সেই assignment-এ false, তাই সেটা বাছাই হতো না)। তাই কোনো complementary edge-ও ভেতরে নেই — সেটটা independent।

Independent set of size k \implies satisfiable: যেহেতু প্রতিটা triangle থেকে সর্বোচ্চ একটা node বাছা যায়, আর মোট k = m node পেতে হলে প্রতিটা triangle থেকে ঠিক একটা বাছতেই হবে। প্রতিটা বাছা node-কে true সেট করুন (তার variable/literal অনুযায়ী) — কোনো দ্বন্দ্ব হবে না কারণ complementary edge থাকার কারণে x_i আর \neg x_i দুটোই বাছা যায়নি। ফলাফল একটা সামঞ্জস্যপূর্ণ assignment যেখানে প্রতিটা clause-এ অন্তত একটা true literal — \phi satisfied।

রূপান্তরের আকার: O(m) node, O(m) edge — স্পষ্টতই polynomial। তাই 3\text{-SAT} \le_p \text{INDEPENDENT-SET}, আর যেহেতু \text{INDEPENDENT-SET} \in NP (certificate = node সেট, যাচাই O(k^2)), \text{INDEPENDENT-SET} NP-complete।

Reduction ৩ — Independent Set থেকে Vertex Cover (একটা বোনাস, প্রায় বিনামূল্যে)

\text{VERTEX-COVER}: G আর k দেওয়া আছে — k-টা node আছে কি যারা মিলে প্রতিটা edge-এর অন্তত একটা প্রান্ত ঢাকে?

পর্যবেক্ষণ: S একটা independent set \iff V \setminus S একটা vertex cover। (প্রমাণ: S independent মানে S-এর ভেতরে কোনো edge নেই — অর্থাৎ প্রতিটা edge-এর অন্তত একটা প্রান্ত S-এর বাইরে, V \setminus S-এ। এটাই vertex cover-এর সংজ্ঞা, হুবহু।)

তাই reduction তুচ্ছ: একই graph G নিন, k' = |V| - k সেট করুন। (G, k) \in \text{INDEPENDENT-SET} \iff (G, k') \in \text{VERTEX-COVER}। এটা O(1) সময়ে (শুধু একটা বিয়োগ) গণনাযোগ্য — এখনো পর্যন্ত সবচেয়ে সরল reduction যা আমরা দেখলাম, কিন্তু ঠিক ততটাই বৈধ।

একটা reduction chain — SAT থেকে Vertex Cover পর্যন্ত

SAT (Cook-Levin)প্রথম ইট — প্রতিটা NP সমস্যা এখানে reduce হয়
3-SATSAT ≤p 3-SAT — clause ভাঙা, auxiliary variable
Independent Set3-SAT ≤p IS — triangle per clause, complementary edges
Vertex CoverIS ≤p VC — complement নেওয়া, |V|-k

Transitivity অনুযায়ী \text{SAT} \le_p \text{VERTEX-COVER} সরাসরি বেরিয়ে আসে — কোনো আলাদা প্রমাণ ছাড়াই, শুধু চেইনটা জুড়ে দিয়ে।

নিজে চালিয়ে দেখুন

EXPERIMENT

একটা reduction সত্যিই কাজ করে কি না — random instance-এ যাচাই

Python 3· ২০ মিনিট

import itertools, random

def is_satisfiable(clauses, n_vars):
    """Brute-force SAT solver — শুধু যাচাইয়ের জন্য (ছোট n-এ)"""
    for bits in itertools.product([False, True], repeat=n_vars):
        if all(any((bits[abs(l)-1] if l > 0 else not bits[abs(l)-1])
                   for l in clause) for clause in clauses):
            return True
    return False

def reduce_3sat_to_independent_set(clauses):
    """প্রতিটা literal একটা node: (clause_idx, literal_position)"""
    nodes = [(ci, li) for ci, clause in enumerate(clauses) for li in range(len(clause))]
    edges = set()
    # triangle edges — একই clause-এর সব জোড়া
    for ci, clause in enumerate(clauses):
        for a, b in itertools.combinations(range(len(clause)), 2):
            edges.add(frozenset({(ci, a), (ci, b)}))
    # complementary edges — বিভিন্ন clause-এ বিপরীত literal
    for (ci, li), (cj, lj) in itertools.combinations(nodes, 2):
        if ci != cj and clauses[ci][li] == -clauses[cj][lj]:
            edges.add(frozenset({(ci, li), (cj, lj)}))
    return nodes, edges

def has_independent_set(nodes, edges, k):
    for subset in itertools.combinations(nodes, k):
        s = set(subset)
        if not any(e <= s for e in edges):
            return True
    return False

random.seed(42)
mismatches = 0
for trial in range(200):
    n_vars = random.randint(2, 4)
    m = random.randint(1, 4)
    clauses = [[random.choice([1, -1]) * random.randint(1, n_vars) for _ in range(3)]
               for _ in range(m)]

    sat = is_satisfiable(clauses, n_vars)
    nodes, edges = reduce_3sat_to_independent_set(clauses)
    ind = has_independent_set(nodes, edges, k=m)

    if sat != ind:
        mismatches += 1
        print(f"MISMATCH! clauses={clauses}  SAT={sat}  IndepSet(k={m})={ind}")

print(f"\n২০০টা random instance-এ mismatch: {mismatches}")
print("mismatch == 0 মানে reduction-টা এই sample-এ সামঞ্জস্যপূর্ণ (formal proof-এর বিকল্প নয়, কিন্তু sanity check)")

প্রত্যাশিত আউটপুট:

২০০টা random instance-এ mismatch: 0
mismatch == 0 মানে reduction-টা এই sample-এ সামঞ্জস্যপূর্ণ (formal proof-এর বিকল্প নয়, কিন্তু sanity check)

এটা প্রমাণ নয়

২০০টা (বা ২০ লক্ষটা) instance-এ mismatch না পাওয়া reduction-টা সঠিক তার প্রমাণ নয় — এটা শুধু একটা sanity check যা ভুল ধরতে সাহায্য করে (bug থাকলে সাধারণত দ্রুত ধরা পড়ে)। প্রকৃত correctness সবসময় আসে আগের অংশের মতো একটা গাণিতিক প্রমাণ থেকে (“দুই দিক” যুক্তি) — কখনো টেস্টিং দিয়ে নয়। এটা এই module-এর “formal methods” লেসনের কেন্দ্রীয় থিম — testing bug খুঁজে পায়, proof বাগ-হীনতা নিশ্চিত করে।

এটা কী প্রমাণ করে

3-SAT → Independent Set reduction-টা হাজারো random instance-এ satisfiability আর independent-set-এর অস্তিত্ব সবসময় একমত হয় — একটা reduction-এর correctness proof যা কাগজে করা হয়েছে, তা এখন পরীক্ষামূলকভাবেও যাচাই করা।

নিজে বানান

BUILD IT

একটা reduction pipeline — 3-SAT থেকে Vertex Cover

Python · ●●●●○

CNF clause পার্স করে internal representation বানান (literal-দের list-এর list)
SAT → 3-SAT converter লিখুন — auxiliary variable দিয়ে দীর্ঘ clause ভাঙা
3-SAT → Independent Set converter লিখুন — triangle + complementary edges
Independent Set → Vertex Cover converter লিখুন — complement নেওয়া
পুরো chain-টা end-to-end চালিয়ে verify করুন মূল SAT formula-র satisfiability আর শেষ Vertex Cover-এর অস্তিত্ব একমত

লক্ষ্য: reduction-চেইনটা শুধু কাগজে না, বাস্তবে কোড হিসেবে চালিয়ে দেখা — যেটা সরাসরি পরের “SAT Solver (DPLL)” প্রজেক্টের প্রস্তুতিও।

def sat_to_3sat(clauses):
    """যেকোনো দৈর্ঘ্যের CNF clause-কে 3-literal clause-এ রূপান্তর"""
    new_clauses = []
    next_var = max(abs(l) for c in clauses for l in c) + 1

    for clause in clauses:
        k = len(clause)
        if k == 3:
            new_clauses.append(clause)
        elif k < 3:
            # প্যাড করুন প্রথম literal পুনরাবৃত্তি করে
            padded = clause + [clause[0]] * (3 - k)
            new_clauses.append(padded)
        else:
            # ৫-literal উদাহরণের মতো ভাঙুন
            ys = [next_var + i for i in range(k - 3)]
            next_var += (k - 3)
            new_clauses.append([clause[0], clause[1], ys[0]])
            for i in range(1, k - 3):
                new_clauses.append([-ys[i - 1], clause[i + 1], ys[i]])
            new_clauses.append([-ys[-1], clause[-2], clause[-1]])
    return new_clauses


def vertex_cover_from_3sat(clauses):
    """সম্পূর্ণ chain: 3-SAT → Independent Set → Vertex Cover"""
    import itertools
    nodes = [(ci, li) for ci, clause in enumerate(clauses) for li in range(len(clause))]
    edges = set()
    for ci, clause in enumerate(clauses):
        for a, b in itertools.combinations(range(len(clause)), 2):
            edges.add(frozenset({(ci, a), (ci, b)}))
    for (ci, li), (cj, lj) in itertools.combinations(nodes, 2):
        if ci != cj and clauses[ci][li] == -clauses[cj][lj]:
            edges.add(frozenset({(ci, li), (cj, lj)}))
    k_independent = len(clauses)
    k_cover = len(nodes) - k_independent
    return nodes, edges, k_cover


# একটা দীর্ঘ clause সহ উদাহরণ (৫-literal, তাই sat_to_3sat প্রকৃত কাজ করবে)
original = [[1, 2, 3, 4, 5], [-1, -2, 3]]
step1 = sat_to_3sat(original)
print("মূল SAT clauses     :", original)
print("3-SAT-এ রূপান্তরিত   :", step1)

nodes, edges, k = vertex_cover_from_3sat(step1)
print(f"\nVertex Cover instance: {len(nodes)} node, {len(edges)} edge, k={k}")

নিজে বাড়ান:

একটা brute-force Vertex Cover solver লিখে পুরো chain-এর শেষ প্রান্তে যাচাই করুন যে উত্তরটা মূল formula-র satisfiability-র সাথে মেলে
sat_to_3sat-এ auxiliary variable সংখ্যা গণনা করে দেখান এটা O(\sum_i (|c_i| - 3)) — মোট রৈখিক, formula আকারের সাপেক্ষে
একটা নতুন reduction লিখুন: \text{3-SAT} \le_p \text{CLIQUE} (ইঙ্গিত: \text{CLIQUE}(G, k) \iff \text{INDEPENDENT-SET}(\bar{G}, k), যেখানে \bar{G} হলো complement graph — edge আর non-edge উল্টানো)
Reduction chain-এর প্রতিটা ধাপের input/output আকার প্লট করুন m (clause সংখ্যা)-এর ফাংশন হিসেবে — নিশ্চিত করুন সবকটাই রৈখিক/polynomial বৃদ্ধি দেখাচ্ছে, exponential নয়

বাস্তব সিস্টেমে

NP-completeness প্রমাণ বাস্তবে কী পরিবর্তন করে

গবেষণা সময়ের সবচেয়ে বড় সিদ্ধান্ত — “থামব কখন”। একটা নতুন সমস্যার মুখোমুখি হলে (নতুন scheduling সমস্যা, নতুন resource allocation), প্রথম প্রশ্ন: এটা কি P-তে, নাকি সম্ভবত NP-complete? যদি ৩০ মিনিটে একটা known NP-complete সমস্যা (Vertex Cover, Independent Set, 3-SAT, Bin Packing, …) থেকে এতে reduction পাওয়া যায়, তাহলে জানা যায় exact polynomial algorithm খোঁজায় সময় নষ্ট না করে সরাসরি heuristic/ approximation-এ যাওয়াই বুদ্ধিমানের কাজ (পরের module-এর লেসনের বিষয়)। এটা গবেষণা-সময় বাঁচানোর একটা বিশাল ব্যবহারিক হাতিয়ার — একটা negative ফলাফলও (এটা কঠিন) কার্যকর তথ্য।

Compiler — instruction scheduling। একটা basic block-এর instruction-গুলোকে সীমিত সংখ্যক functional unit-এ সময়সূচি দেওয়া (দুইটা dependent instruction একসাথে চালানো যাবে না) — এটা job-shop scheduling-এর একটা রূপ, NP-complete। GCC/LLVM-এর মতো compiler তাই list scheduling-এর মতো heuristic ব্যবহার করে, exact optimal নয়।

Cryptographic hardness assumption। Zero-knowledge proof system-এর প্রথম generic নির্মাণ (Goldreich-Micali-Wigderson, ১৯৮৬) সরাসরি 3\text{-COLORING}-এর NP-completeness ব্যবহার করে — “আমি জানি একটা secret, কিন্তু secret-টা প্রকাশ না করে” প্রমাণ করতে, প্রথমে দাবিটাকে (reduction দিয়ে) একটা graph-coloring instance-এ রূপান্তর করা হয়, তারপর সেই coloring-এর knowledge প্রমাণ করা হয় zero-knowledge-এ। এই কৌশলটাই আধুনিক zk-SNARK-এর পূর্বসূরি।

Operations research — solver-এর ভেতরে। Commercial ILP (Integer Linear Programming) solver (Gurobi, CPLEX) কার্যত NP-hard সমস্যা সমাধান করে প্রতিদিন — কিন্তু তারা “সমাধান করে” branch-and-bound, cutting plane, আর decades-এর engineering দিয়ে, কোনো polynomial algorithm আবিষ্কার করে নয়। এরা জানে সমস্যাটা তাত্ত্বিকভাবে কঠিন, তাই তারা worst-case guarantee ছেড়ে practical performance-এর উপর মনোযোগ দেয় — ঠিক এই লেসনের শিক্ষা প্রয়োগ করে।

পরের প্রজেক্ট — SAT Solver (DPLL)। এই module-এরই একটা প্রজেক্ট হলো নিজের হাতে একটা DPLL-based SAT solver বানানো — unit propagation আর backtracking দিয়ে। এখন আপনি জানেন কেন এটা এত গুরুত্বপূর্ণ একটা সমস্যা: SAT শুধু আরেকটা NP-complete সমস্যা না, এটা প্রথম ইট, আর একটা ভালো SAT solver থাকলে (reduction দিয়ে) হাজার হাজার ভিন্ন সমস্যা একই solver দিয়ে সমাধান করা যায় — বাস্তবে modern hardware verification, package dependency resolution, আর AI planning-এর অনেক টুল ঠিক এই কৌশলই ব্যবহার করে: সমস্যাটাকে SAT-এ reduce করে একটা শক্তিশালী off-the-shelf SAT solver-এ পাঠিয়ে দেওয়া।

যে ভুলগুলো সবাই করে

“NP-hard মানেই NP-complete।”

না — NP\text{-hard} একটা strictly বড় class, NP\text{-complete} তার একটা উপসেট।

NP\text{-complete} = NP\text{-hard} \cap NP। একটা সমস্যা NP-hard হতে পারে অথচ NP-তে না থেকেও — অর্থাৎ এটা এত কঠিন যে এর certificate-ও polynomial সময়ে যাচাই করা যায় না।

উদাহরণ: TQBF (এই module-এর আগের লেসনের PSPACE-complete সমস্যা) NP-hard (কারণ NP \subseteq PSPACE, তাই NP-এর সব সমস্যা TQBF-এ reduce করা যায় — আসলে এটা PSPACE-hard, যা NP-hard-এর চেয়েও শক্তিশালী দাবি) কিন্তু TQBF \in NP-তে আছে কি না অজানা (বিশ্বাস করা হয় নেই, কারণ NP = PSPACE-এর কোনো প্রমাণ নেই)। এমনকি \text{Halting Problem}-এর মতো undecidable সমস্যাও NP-hard (আগের লেসনগুলোর undecidability-র জ্ঞান দিয়ে reduction বানানো যায়), যদিও এটা NP-এর ধারেকাছেও নেই — এটা কোনো TM-এই decide করা যায় না, তাই certificate যাচাইয়ের প্রশ্নই অবান্তর।

“একটা সমস্যা NP-complete প্রমাণ করতে হলে Cook-Levin-এর মতো tableau construction আবার নতুন করে করতে হয়।”

প্রায় কখনোই না — এটাই reduction transitivity-র পুরো পয়েন্ট।

Cook-Levin theorem-টা একবারই করা লাগে (SAT-এর জন্য)। তারপর থেকে যেকোনো নতুন সমস্যা X-কে NP-complete প্রমাণ করতে দুটো ধাপ যথেষ্ট:

X \in NP দেখান (সাধারণত সহজ — শুধু একটা verifier বর্ণনা করুন)
যেকোনো একটা জানা NP-complete সমস্যা \text{known} \le_p X দেখান

দ্বিতীয় ধাপে SAT থেকে সরাসরি reduce করার দরকার নেই — এই লেসনের 3\text{-SAT} \to \text{Independent Set} \to \text{Vertex Cover} চেইনের মতো, যেকোনো ইতিমধ্যে-প্রমাণিত NP-complete সমস্যা ব্যবহার করা যায়, যেটা reduction লেখাকে সহজতম করে তোলে। গবেষণা-পত্রে ৯৯% NP-completeness প্রমাণ এভাবেই হয় — একটা পরিচিত সমস্যা থেকে সরাসরি reduction, tableau-এ ফিরে যাওয়া ছাড়াই।

“যেহেতু একটা সমস্যা NP-complete, এর মানে সব instance-ই ব্যবহারিকভাবে সমাধান-অযোগ্য।”

না — NP-completeness একটা worst-case বিবৃতি, নির্দিষ্ট instance-এর নয়।

আধুনিক SAT solver (MiniSat, Glucose, CaDiCaL-এর মতো) লক্ষ লক্ষ variable-ওয়ালা বাস্তব-জগতের SAT instance (hardware verification-এর মতো ক্ষেত্র থেকে) নিয়মিত সমাধান করে, সেকেন্ডে বা মিনিটে — যদিও worst-case exponential (যদি P \ne NP)। কারণ বাস্তব instance-গুলোর কাঠামো থাকে (redundancy, locality, symmetry) যা clever heuristic (clause learning, branching heuristic — এই module-এর SAT Solver প্রজেক্টে যার একটা সরল সংস্করণ বানাবেন) কাজে লাগাতে পারে।

NP-completeness শুধু এই গ্যারান্টি দেয় না যে প্রতিটা instance-এর জন্য একটা algorithm আছে যা সব সময় দ্রুত কাজ করবে (worst-case-এ guaranteed polynomial bound নেই) — এটা বলে না যে কোনো instance-ই দ্রুত সমাধানযোগ্য নয়। “Approximation ও randomized complexity” লেসনে এই পার্থক্যটা আরো বিস্তারিত আসবে।

বুঝেছেন কি না দেখুন

A \le_p B সংজ্ঞায় দুইটা শর্ত আছে ফাংশন f-এর উপর। কী কী, আর NP-hardness সংজ্ঞায় A আর B-র ভূমিকা (কে “known”, কে “নতুন”) কীভাবে বসে?

স্মরণ

দুইটা শর্ত f-এর উপর:

সঠিকতা: x \in A \iff f(x) \in B
দক্ষতা: f polynomial সময়ে গণনাযোগ্য

X-কে NP-hard প্রমাণ করতে হলে জানা NP-hard/complete সমস্যা \text{known}-কে A হিসেবে নিন, আর নতুন সমস্যা X-কে B হিসেবে নিন: \text{known} \le_p X। এর মানে “known সমস্যা সমাধান করতে X-এর একটা solver ধার করা যায়” — অর্থাৎ X অন্তত \text{known}-এর মতোই কঠিন। যেহেতু \text{known} ইতিমধ্যে সবচেয়ে কঠিন (NP-hard), X-ও তাই।

উল্টো দিক (X \le_p \text{known}) দেখালে শুধু বোঝা যেত X \text{known}-এর চেয়ে সহজ বা সমান — এটা X-এর কাঠিন্য সম্পর্কে কিছুই বলে না, তাই ভুল দিক।

Cook-Levin proof-এর tableau construction-এ variable সংখ্যা O(p(n)^2 \cdot |\Gamma|)। যদি verifier V-এর সময়সীমা p(n)-এর বদলে 2^n হতো (অর্থাৎ V-কে exponential সময় দেওয়া হতো), তাহলে পুরো প্রমাণটার কোথায় ভাঙন ধরত?

যুক্তি

Tableau-র আকার নির্ভর করে computation-এর দৈর্ঘ্যের উপর — সারি সংখ্যা = V-এর সময়সীমা, কলাম সংখ্যাও তার সমানুপাতিক (tape-এর ব্যবহৃত অংশ, যা সময়সীমার বেশি হতে পারে না)।

যদি V-এর সময়সীমা 2^n হতো, tableau হতো 2^n \times 2^n, তাই variable সংখ্যা O(2^{2n}) — exponential, polynomial নয়।

এর মানে \phi_x গঠন করতেই exponential সময় লাগত, যা reduction-এর সংজ্ঞার (২) শর্ত (f polynomial সময়ে গণনাযোগ্য) ভাঙত। ফলাফলটা তখনও সত্য থাকত (formula তখনও satisfiability সমতুল্য হতো) কিন্তু এটা আর একটা বৈধ polynomial-time reduction থাকত না — শুধু “L-কে SAT-এ রূপান্তর করা যায়” বলাটাই যথেষ্ট নয়, রূপান্তরটা দ্রুত হতে হবে, নাহলে NP-hardness-এর দাবিটাই অর্থহীন (SAT নিজে হয়তো EXPTIME-hard হয়ে যেত এই দুর্বল সংজ্ঞায়, যা তুচ্ছ এবং অকার্যকর একটা ফলাফল)।

এটাই ব্যাখ্যা করে কেন verifier-এর polynomial-time বাধ্যবাধকতা NP-এর সংজ্ঞায় এত গুরুত্বপূর্ণ — শুধু “certificate ছোট” যথেষ্ট নয়, “verify দ্রুত”-ও লাগে, আর পুরো Cook-Levin যন্ত্রটা এই দুই শর্তের উপরেই দাঁড়িয়ে।

Clause (l_1 \vee l_2 \vee l_3 \vee l_4) (৪-literal) দেওয়া হলো। লেসনে দেখানো কৌশল ব্যবহার করে এটাকে 3-literal clause-এ ভাঙুন, আর দেখান কেন এটা সমতুল্য।

প্রয়োগ

একটা নতুন variable y যোগ করে ভাঙুন:

(l_1 \vee l_2 \vee y) \wedge (\neg y \vee l_3 \vee l_4)

সমতুল্যতা — এক দিক: ধরুন মূল clause satisfied, অর্থাৎ কোনো l_i true।

যদি l_1 বা l_2 true হয়: y = \text{true} সেট করুন। প্রথম clause সরাসরি satisfied (l_1 বা l_2 দিয়ে)। দ্বিতীয় clause-ও satisfied কারণ \neg y = \text{false}, কিন্তু y=\text{true} মানে amortization দরকার — আসলে দ্বিতীয় clause-এ \neg y false হলেও l_3 \vee l_4 কিছু বলে না, তাই বরং সঠিক নিয়ম: y কে সেট করুন যেন উভয় clause satisfied থাকে। যেহেতু l_1/l_2 প্রথমটা satisfy করে, y যেকোনো মান নিতে পারে যদি \neg y \vee l_3 \vee l_4 আলাদাভাবে satisfied থাকে — তাই y = \text{false} নিন, তাহলে \neg y = \text{true}, দ্বিতীয় clause-ও সরাসরি satisfied।
যদি l_3 বা l_4 true হয় (আর l_1, l_2 false): y = \text{true} নিন। প্রথম clause: l_1 \vee l_2 \vee y = F \vee F \vee T = \text{true} ✓। দ্বিতীয় clause: \neg y \vee l_3 \vee l_4 = F \vee (l_3 \vee l_4) = \text{true} ✓ (যেহেতু l_3 বা l_4 true)।

দুই ক্ষেত্রেই y-এর একটা উপযুক্ত মান পাওয়া যায় যা দুটো নতুন clause-ই satisfy করে।

অন্য দিক: ধরুন দুইটা নতুন clause satisfied, কিন্তু মূল clause (l_1 \vee l_2 \vee l_3 \vee l_4) false — অর্থাৎ সব l_i false। তাহলে প্রথম clause: F \vee F \vee y = y — সত্য হতে y = \text{true} লাগবে। দ্বিতীয় clause: \neg y \vee F \vee F = \neg y — সত্য হতে y = \text{false} লাগবে। দুটো একসাথে সম্ভব নয় (y একই সাথে true আর false হতে পারে না) — বৈপরীত্য। তাই যদি নতুন clause দুটো satisfied হয়, মূল clause-ও অবশ্যই satisfied হতে হবে।

সুতরাং দুই clause-এর conjunction ঠিক তখনই satisfiable (উপযুক্ত y সহ) যখন মূল clause satisfiable — reduction সঠিক ∎

ধরুন আপনি একটা নতুন সমস্যা আবিষ্কার করলেন — \text{SPARSE-SCHEDULE}: n-টা কাজ, প্রতিটা কাজের একটা deadline আছে, আর m-টা machine আছে (machine-গুলো parallel কাজ করে); প্রশ্ন — সব কাজ deadline-এর আগে শেষ করার একটা assignment (কোন কাজ কোন machine-এ) আছে কি? আপনি সন্দেহ করছেন এটা NP-complete। কীভাবে এগোবেন প্রমাণ করতে (উচ্চ-স্তরের পরিকল্পনা, কোড নয়)?

ডিজাইন

দুই ধাপের পরিকল্পনা:

ধাপ ১ — \text{SPARSE-SCHEDULE} \in NP দেখান। একটা certificate প্রস্তাব করুন: প্রতিটা কাজের machine-assignment আর সময়সূচি। Verifier: প্রতিটা কাজ তার নির্ধারিত machine-এ, নির্ধারিত সময়ে চলছে কি না, আর সেই সময় deadline-এর আগে কি না — এটা O(n) বা O(n \log n) সময়ে (কাজগুলো সময় অনুযায়ী sort করে) যাচাইযোগ্য, স্পষ্টতই polynomial।

ধাপ ২ — একটা জানা NP-complete সমস্যা এতে reduce করুন। এখানেই আসল কাজ। প্রথমে ভাবুন সমস্যাটার “আকৃতি” কোন পরিচিত সমস্যার মতো — এখানে “সীমিত সম্পদে (machine) কাজ ভাগ করা, সময়সীমা মেনে” শোনাচ্ছে \text{PARTITION} বা \text{BIN-PACKING}-এর মতো (দুটোই classic NP-complete)। বিশেষভাবে, m = 2 machine আর সব deadline সমান ধরলে সমস্যাটা প্রায় হুবহু \text{PARTITION}-এর মতো দেখায় (কাজের সময়কাল-গুলোকে দুই machine-এ ভাগ করা যাতে দুই দিকের যোগফল সমান/সীমার মধ্যে)।

তাই কৌশল: \text{PARTITION}-এর একটা instance (সংখ্যার সেট S) নিয়ে, প্রতিটা সংখ্যাকে একটা কাজের duration হিসেবে ব্যবহার করুন, deadline = \lceil \sum S / 2 \rceil (বা যথাযথ মান), m = 2 machine সেট করুন। দেখান S দুই সমান-যোগফল অংশে ভাগ করা যায় \iff এই schedule-instance সমাধানযোগ্য — ঠিক এই লেসনের 3\text{-SAT} \to \text{Independent Set} প্রমাণের মতো দুই-দিকের যুক্তি লিখুন।

গুরুত্বপূর্ণ নকশা-নীতি: reduction যত সম্ভব সরল পরিচিত সমস্যা থেকে নিন (এখানে \text{PARTITION}, \text{SAT} থেকে সরাসরি না গিয়ে) — reduction transitivity-র সুবিধা নেওয়া মানেই কম কাজ, কম ভুলের সুযোগ। এটাই বাস্তব গবেষণায় NP-completeness প্রমাণের স্বাভাবিক ওয়ার্কফ্লো: নতুন সমস্যার “আকৃতি” চিনে, সবচেয়ে কাছাকাছি পরিচিত NP-complete সমস্যা বেছে নেওয়া, তারপর reduction লেখা।

Independent Set → Vertex Cover reduction-টা (k' = |V| - k) ছিল O(1) সময়ে — কোনো নতুন node/edge তৈরি না করেই। এই reduction-টা কি তাহলে “দুর্বল” প্রমাণ, নাকি একইভাবে বৈধ? ব্যাখ্যা করুন।

যুক্তি

সম্পূর্ণ বৈধ, এবং এর সরলতা কোনো দুর্বলতা নয়।

Polynomial-time reduction-এর সংজ্ঞায় কোনো শর্ত নেই যে রূপান্তর “জটিল” হতে হবে বা নতুন গঠন তৈরি করতে হবে। শর্ত শুধু দুটো: (১) সঠিকতা (x \in A \iff f(x) \in B) আর (২) polynomial সময় (O(1) তো polynomial-এরই একটা বিশেষ, দ্রুততম case)।

এই reduction-এর সঠিকতা সম্পূর্ণ কঠোরভাবে প্রমাণিত — S independent \iff V \setminus S vertex cover, এটা set complement-এর একটা সরাসরি property, কোনো ফাঁক নেই।

আসলে সবচেয়ে সুন্দর reduction প্রায়ই সবচেয়ে সরল — কারণ সেগুলোই প্রমাণ করা সহজ, আর error-এর সুযোগ সবচেয়ে কম। জটিল reduction (যেমন 3\text{-SAT} \to \text{Independent Set}, যেখানে triangle বানানো, complementary edge যোগ করা লাগে) দরকার হয় যখন দুই সমস্যার “গঠন” স্বাভাবিকভাবে একরকম নয়। যখন দুটো সমস্যা গোপনে একই কাঠামোর দুটো রূপ মাত্র (যেমন Independent Set আর Vertex Cover — দুটোই আসলে “node সেট বাছাই” সমস্যা, শুধু বিপরীত শর্তে), তখন reduction তুচ্ছ হয়ে যায়। এই observation-টাই জটিলতা তত্ত্বে “সমস্যা-পরিবার” চেনার একটা গুরুত্বপূর্ণ দক্ষতা — কোন দুইটা সমস্যা আসলে “একই জিনিস, ভিন্ন ভাষায়” তা চেনা।

এরপর কী

আমরা এখন জানি SAT (আর transitivity দিয়ে হাজার হাজার আরো সমস্যা) NP-complete — NP-এর সবচেয়ে কঠিন সদস্য, যাদের একটার polynomial সমাধান পেলেই সবগুলোর সমাধান পাওয়া যাবে।

কিন্তু এখনো মূল প্রশ্নটা অমীমাংসিত রয়ে গেছে: আসলে কি এমন কোনো polynomial algorithm সম্ভব? পরের লেসনে আমরা সরাসরি এই প্রশ্নের মুখোমুখি হব — P = NP প্রমাণিত হলে বাস্তবে কী ঘটবে (cryptography, optimization, গণিত নিজেই), কেন বেশিরভাগ গবেষক বিশ্বাস করেন P \ne NP, আর কেন এই প্রশ্নটা প্রমাণ করা এত অস্বাভাবিক রকম কঠিন — এমনকি প্রমাণ-পদ্ধতি নিজেই কেন এখানে বাধা পায়।

NP-completeness ও Cook-Levin Theorem — একটা সমস্যা যা সবাইকে বহন করে

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Reduction — সমস্যা থেকে সমস্যায় যাওয়ার সেতু

NP-hard এবং NP-complete

Reduction-এর transitivity — কেন এক ইট দিয়ে দালান তৈরি হয়

ভেতরে কী ঘটছে

Cook-Levin theorem — বিবৃতি

প্রমাণ sketch — computation tableau

উদাহরণ

Reduction ১ — SAT থেকে 3-SAT

Reduction ২ — 3-SAT থেকে Independent Set

Reduction ৩ — Independent Set থেকে Vertex Cover (একটা বোনাস, প্রায় বিনামূল্যে)

নিজে চালিয়ে দেখুন

একটা reduction সত্যিই কাজ করে কি না — random instance-এ যাচাই

নিজে বানান

একটা reduction pipeline — 3-SAT থেকে Vertex Cover

বাস্তব সিস্টেমে

NP-completeness প্রমাণ বাস্তবে কী পরিবর্তন করে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Reduction — সমস্যা থেকে সমস্যায় যাওয়ার সেতু

NP-hard এবং NP-complete

Reduction-এর transitivity — কেন এক ইট দিয়ে দালান তৈরি হয়

⚙ভেতরে কী ঘটছেUnder the hood

Cook-Levin theorem — বিবৃতি

প্রমাণ sketch — computation tableau

▶উদাহরণExample

Reduction ১ — SAT থেকে 3-SAT

Reduction ২ — 3-SAT থেকে Independent Set

Reduction ৩ — Independent Set থেকে Vertex Cover (একটা বোনাস, প্রায় বিনামূল্যে)

⌘নিজে চালিয়ে দেখুনExperiment

একটা reduction সত্যিই কাজ করে কি না — random instance-এ যাচাই

⚒নিজে বানানBuild it yourself

একটা reduction pipeline — 3-SAT থেকে Vertex Cover

◉বাস্তব সিস্টেমেReal-world usage

NP-completeness প্রমাণ বাস্তবে কী পরিবর্তন করে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী