এই পর্বে যা শিখবেন
- Certificate, verifier আর polynomial-time verifier-এর নিখুঁত সংজ্ঞা, আর সময় কেন |w| দিয়ে মাপা হয়
- HAMPATH, CLIQUE, SUBSET-SUM, COMPOSITES আর SAT-এর certificate আর verifier লেখা, ধাপ গুনে
- Verifier থেকে NTM আর NTM থেকে verifier, দুই দিকের পূর্ণ প্রমাণ
- P ⊆ NP ⊆ EXP-এর প্রমাণ, আর কোন সীমানা প্রমাণিত, কোনটি খোলা
- কোন সমস্যা সহজে NP-তে পড়ে না (HAMPATH-এর complement), আর NP নিয়ে প্রচলিত ভুল ধারণা
১ · খোঁজা কঠিন, মেলানো সহজ — certificate-এর ধারণা
বাজারঘরের delivery বিভাগ একটি প্রশ্ন নিয়ে বসেছে। ছয়টি জেলায় পার্সেল যাবে: কুমিল্লা, নারায়ণগঞ্জ, ঢাকা, গাজীপুর, টাঙ্গাইল আর ময়মনসিংহ। একটি ভ্যান কুমিল্লা থেকে ছাড়বে, প্রতিটি জেলায় ঠিক একবার যাবে, আর ময়মনসিংহে গিয়ে থামবে। যে দুই জেলার মধ্যে সরাসরি delivery রাস্তা আছে, শুধু সেগুলো ব্যবহার করা যাবে। প্রশ্ন: এমন রুট কি আছে?
ছয়টি জেলায় হাতে চেষ্টা করা যায়। কিন্তু ৬০টি জেলা হলে? প্রথম আর শেষ জেলা ঠিক থাকলে মাঝের ৫৮টির ক্রম 58! রকম, যা ৭৯ অঙ্কের একটি সংখ্যা। কোনো চতুর পদ্ধতি সব ক্ষেত্রে দ্রুত উত্তর দিতে পারে কি না, তা আজও কেউ জানে না। অথচ কেউ যদি একটি রুট লিখে এনে দেয়, “কুমিল্লা → নারায়ণগঞ্জ → ঢাকা → …”, তাহলে মেলানো খুবই সহজ: প্রতিটি জেলা একবার এসেছে কি না দেখা, আর পাশাপাশি দুটি জেলার মধ্যে রাস্তা আছে কি না দেখা। ৬০ জেলায় এটি মাত্র ৬০টির মতো ছোট পরীক্ষা।
পরীক্ষার হলে একটি কঠিন অঙ্ক সমাধান করতে আধা ঘণ্টা লাগতে পারে। কিন্তু পরীক্ষক যখন খাতা দেখেন, তাঁর কাজ অনেক সহজ: উত্তরটি সমীকরণে বসিয়ে দেখা যে মেলে কি না। Sudoku-ও তেমন: ফাঁকা বোর্ড ভরতে অনেক সময় লাগে, কিন্তু ভরা বোর্ড পেলে প্রতিটি সারি, কলাম আর বাক্স মিলিয়ে দেখতে এক মিনিটও লাগে না। ভরা বোর্ডটি হলো “হ্যাঁ, সমাধান আছে” দাবির প্রমাণ; এটিই certificate. যিনি মিলিয়ে দেখেন, তিনি verifier.
এই পর্বের পুরো বিষয় এই অসমতা: কিছু সমস্যায় উত্তর খুঁজে পাওয়া কঠিন মনে হয়, কিন্তু একটি প্রস্তাবিত উত্তর মিলিয়ে দেখা সহজ। যেসব সমস্যায় প্রতিটি “হ্যাঁ” উত্তরের এমন একটি ছোট, দ্রুত মেলানো যায় এমন প্রমাণ আছে, তাদের শ্রেণির নাম NP. নিচের ছবিতে বাজারঘরের delivery map আর একটি রুট-certificate.
বাজারঘরের delivery map আর একটি HAMPATH certificate
প্রতিটি রেখা একটি দুই-মুখী রাস্তা, যা দুটি directed edge-এর সমান। সবুজ তীরগুলো certificate ⟨C, N, D, G, T, M⟩: s = কুমিল্লা থেকে t = ময়মনসিংহ, প্রতিটি জেলা ঠিক একবার।
বাজারঘরের প্রশ্নটি পর্ব ০৫-এর ভাষায় একটি decision problem, আর তাই একটি language: HAMPATH = {⟨G, s, t⟩ : G একটি directed graph, যাতে s থেকে t পর্যন্ত একটি Hamiltonian path আছে}. ⟨G, s, t⟩ মানে graph আর দুটি vertex-এর একটি যুক্তিসংগত encoding, যেমন adjacency list. দুই-মুখী রাস্তাকে দুটি directed edge ধরলে বাজারঘরের map একটি directed graph. গ্রাফ-তত্ত্বের দিক থেকে Hamilton path-এর পরিচয় পাবেন ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬০-এ।
২ · Verifier আর NP-এর সংজ্ঞা
এবার ধারণাটিকে নিখুঁত করা যাক। আমরা Sipser-এর রীতি মানব, আর সময় মাপব single-tape deterministic Turing machine-এ; পর্ব ৫৭-এ দেখানো হয়েছে, যুক্তিসংগত সব deterministic মডেল পরস্পরের polynomial দূরত্বে, তাই “polynomial সময়” কথাটি মডেলের ওপর নির্ভর করে না।
Language L-এর একটি verifier হলো একটি deterministic decider V, যা ⟨w, c⟩ আকারের input নেয়, আর যার জন্য
L = {w : এমন একটি string c আছে, যাতে V ⟨w, c⟩ গ্রহণ করে}.
c-কে বলে certificate (বা witness, প্রমাণ)। V-এর polynomial-time verifier হওয়ার শর্ত: এমন polynomial p আর q আছে, যাতে V প্রতিটি ⟨w, c⟩-এ বড়জোর q(|w|) ধাপে থামে, আর শুধু |c| ≤ p(|w|) দৈর্ঘ্যের certificate গোনা হয়।
সংজ্ঞাটির তিনটি অংশ আলাদা করে পড়ুন। প্রথম, সম্পূর্ণতা (completeness): w ∈ L হলে অন্তত একটি ভালো c আছে, যা V-কে রাজি করায়। দ্বিতীয়, নির্ভরযোগ্যতা (soundness): w ∉ L হলে কোনো c-ই V-কে রাজি করাতে পারে না; প্রতারক যত চালাক certificate-ই আনুক, V বর্জন করে। তৃতীয়, দক্ষতা: certificate ছোট, আর V দ্রুত। সময় মাপা হয় শুধু |w| দিয়ে, |⟨w, c⟩| দিয়ে নয়; |c| ≤ p(|w|) বলে দুটি মাপ পরস্পরের polynomial, তাই আসলে পার্থক্য পড়ে না। কিন্তু |c|-এর সীমা না থাকলে একটি বিশাল certificate দিয়ে “polynomial” সময়ে প্রায় সবকিছু কেনা যেত; সেই কথা ভাবনার প্রশ্ন ১-এ।
L ∈ NP ⇔ একটি polynomial-time verifier V আর polynomial p আছে, যাতে প্রতিটি w-এর জন্য
w ∈ L ⇔ ∃c (|c| ≤ p(|w|) এবং V ⟨w, c⟩ গ্রহণ করে).
এখানে ∃ মানে “অন্তত একটি আছে”। সংজ্ঞায় একটি অসমতা লুকিয়ে আছে: “হ্যাঁ” উত্তরের ছোট প্রমাণ থাকতে হবে, কিন্তু “না” উত্তরের কোনো প্রমাণের কথা সংজ্ঞায় নেই। এই অসমতা অংশ ৭-এ ফিরবে।
সাবধান: verifier-কে certificate খুঁজতে হয় না। V শুধু হাতে পাওয়া c মেলায়। c কোথা থেকে এল, কে দিল, কত কষ্টে খুঁজল, তা সংজ্ঞার বাইরে। আরেকটি সাধারণ ভুল হলো এই ভাবনা: “V একটি ভুল c বর্জন করল, তাই w ∉ L”, যা ঠিক নয়; শুধু এই c কাজ করেনি। w ∉ L বলতে সব c বর্জিত হওয়া লাগে।
৩ · প্রথম উদাহরণ HAMPATH — একটি certificate ধাপে ধাপে যাচাই
HAMPATH-এর জন্য certificate হলো vertex-গুলোর একটি ক্রম c = ⟨v1, v2, …, vm⟩, যেখানে m = G-এর vertex সংখ্যা। Verifier VHP ⟨⟨G, s, t⟩, c⟩-এ এভাবে চলে:
- c-এর দৈর্ঘ্য m কি না, আর v1 = s ও vm = t কি না দেখা; না হলে বর্জন।
- i = 2, …, m-এর প্রতিটির জন্য: vi আগে এসেছে কি না দেখা, আর (vi−1, vi) G-এর একটি edge কি না দেখা; কোনোটি ব্যর্থ হলে বর্জন।
- সব পরীক্ষা পেরোলে গ্রহণ।
c-এর দৈর্ঘ্য m, যা input-এর দৈর্ঘ্যের চেয়ে কম, তাই p(n) = n যথেষ্ট। ধাপ ২-এর প্রতিটি পরীক্ষা adjacency list-এ একটি খোঁজ, যা Turing machine-এ input-এর ওপর কয়েকবার হেঁটে polynomial সময়ে হয়; সব মিলিয়ে O(n2)-এর মতো একটি polynomial সময় লাগে। নিচের stepper বাজারঘরের certificate ⟨C, N, D, G, T, M⟩ মেলায়।
1len(c) == |V| ?2c[0] == s আর c[-1] == t ?3i = 1 … m−1 প্রতিটির জন্য:4 c[i] নতুন? (আগে আসেনি)5 c[i−1] → c[i] রাস্তা আছে?6সব ঠিক: ACCEPT
| পরীক্ষা | |
| রাস্তা | |
| আগে দেখা | |
| checks |
- দৈর্ঘ্য। Certificate-এ ছয়টি নাম, আর graph-এ ছয়টি vertex. একটি কম বা বেশি হলে এখানেই বর্জন। Code-এ এই আর পরের পরীক্ষা মিলে প্রথম check.
- দুই প্রান্ত। প্রথম নাম C, অর্থাৎ s; শেষ নাম M, অর্থাৎ t. এটি না মিললে রুটটি অন্য কোনো প্রশ্নের উত্তর, এই প্রশ্নের নয়।
- i = 1. N আগে আসেনি, আর কুমিল্লা–নারায়ণগঞ্জ রাস্তা আছে। Check ২.
- i = 2. D নতুন; নারায়ণগঞ্জ–ঢাকা রাস্তা আছে। লক্ষ করুন, V কোনো বিকল্প খোঁজে না, শুধু দেওয়া ক্রমটি মেলায়।
- i = 3. G নতুন; ঢাকা–গাজীপুর রাস্তা আছে।
- i = 4. T নতুন; গাজীপুর–টাঙ্গাইল রাস্তা আছে।
- i = 5, গ্রহণ। M নতুন; টাঙ্গাইল–ময়মনসিংহ রাস্তা আছে। সব পরীক্ষা পেরিয়েছে: V গ্রহণ করে। মোট ৬টি check, অর্থাৎ m-এর সমান; ৬০ জেলায় হতো ৬০টি।
এবার তিনটি verifier একসঙ্গে Python-এ, প্রতিটি নিজের check গুনে। একই ব্লকে তুলনার জন্য brute force খোঁজাও আছে, যা verifier-কে বারবার ডেকে সব certificate চেষ্টা করে। Graph-টি ছবি ৫৮.১-এর; প্রতিটি অক্ষরের পাশে তার প্রতিবেশীরা।
from itertools import permutations, combinations, product
G = {"C": "ND", "N": "CD", "D": "NCG", "G": "DTM", "T": "GM", "M": "GT"}
def v_hampath(G, s, t, path): # certificate: an order of all vertices
ops = 1
if len(path) != len(G) or path[0] != s or path[-1] != t: return False, ops
for i in range(1, len(path)):
ops += 1 # one edge check + one repeat check
if path[i] in path[:i] or path[i] not in G[path[i - 1]]: return False, ops
return True, ops
def v_clique(G, k, c): # certificate: k vertices
ops = 1
if len(set(c)) != k: return False, ops
for a, b in combinations(c, 2):
ops += 1
if b not in G[a]: return False, ops
return True, ops
def v_subset(S, t, bits): # certificate: one bit per number
return len(bits) == len(S) and sum(x for x, b in zip(S, bits) if b == "1") == t, len(S)
print("HAMPATH C->M CNDGTM", v_hampath(G, "C", "M", "CNDGTM"))
print("HAMPATH C->M CDNGTM", v_hampath(G, "C", "M", "CDNGTM"))
print("CLIQUE k=3 GTM ", v_clique(G, 3, "GTM"))
print("CLIQUE k=3 DGT ", v_clique(G, 3, "DGT"))
S = (3, 5, 8, 11, 14)
print("SUBSET t=24 01110 ", v_subset(S, 24, "01110"))
print("SUBSET t=24 10101 ", v_subset(S, 24, "10101"))
def search_hampath(G, s, t): # brute force: every order of the middle
tried = 0
for mid in permutations([v for v in G if v not in (s, t)]):
tried += 1
if v_hampath(G, s, t, s + "".join(mid) + t)[0]: return s + "".join(mid) + t, tried
return None, tried
print("search C->M:", search_hampath(G, "C", "M"))
print("search C->N:", search_hampath(G, "C", "N"))
tries = [("".join(b), v_subset(S, 24, "".join(b))[0]) for b in product("01", repeat=5)]
print("subset search: tried", len(tries), "certificates, accepted", [b for b, ok in tries if ok])আসল আউটপুট (ব্রাউজারের Python):
HAMPATH C->M CNDGTM (True, 6)
HAMPATH C->M CDNGTM (False, 4)
CLIQUE k=3 GTM (True, 4)
CLIQUE k=3 DGT (False, 3)
SUBSET t=24 01110 (True, 5)
SUBSET t=24 10101 (False, 5)
search C->M: ('CNDGTM', 1)
search C->N: (None, 24)
subset search: tried 32 certificates, accepted ['01110']
প্রথম লাইন stepper-এর শেষ ধাপ: ৬টি check-এ গ্রহণ। দ্বিতীয় certificate CDNGTM-এ C → D আর D → N ঠিক আছে, কিন্তু নারায়ণগঞ্জ–গাজীপুর রাস্তা নেই, তাই ৪র্থ check-এ বর্জন। {G, T, M} একটি 3-clique (তিনটি জোড়াই যুক্ত), কিন্তু {D, G, T}-এ D–T রাস্তা নেই। পার্সেলের ওজন (3, 5, 8, 11, 14) কেজি থেকে 5 + 8 + 11 = 24 বেছে নেয় bit-string 01110. খোঁজার দিকে, C → M-এ brute force প্রথম চেষ্টাতেই পেয়েছে (ক্রমগুলো শুরু হয় N, D, G, T দিয়ে, যা ভাগ্যক্রমে উত্তর)। কিন্তু C → N-এ কোনো রুট নেই, আর তা বলতে মাঝের চারটি জেলার সব 4! = ২৪টি ক্রম দেখতে হয়েছে। Subset-এর জন্য সব 25 = ৩২টি bit-string দেখে একটিই মিলেছে।
ছোট উদাহরণে দুটি কাজই চোখের পলকে শেষ। পার্থক্য দেখা যায় n বাড়ালে। নিচের ব্লক n = ৪ থেকে ১০ পর্যন্ত এমন graph বানায়, যেখানে 0 থেকে n − 1 পর্যন্ত কোনো Hamiltonian path নেই (vertex n − 1-এর একমাত্র রাস্তা 0-এর সঙ্গে, যা নিজেই শুরু), আর brute force-কে সব (n − 2)! ক্রম দেখতে বাধ্য করে। Random generator-এর seed স্থির, তাই প্রতিবার একই graph.
import random
from itertools import permutations
from math import factorial
random.seed(58)
checks = 0
def v_hampath(G, s, t, path): # the same verifier, counting checks
global checks
checks += 1
if len(path) != len(G) or path[0] != s or path[-1] != t: return False
for i in range(1, len(path)):
checks += 1
if path[i] in path[:i] or path[i] not in G[path[i - 1]]: return False
return True
def no_path_graph(n): # random roads among 0..n-2; vertex n-1 has a road
G = {v: set() for v in range(n)} # only to 0, so no path 0 -> ... -> n-1
for u in range(n - 1):
for v in range(u + 1, n - 1):
if random.random() < 0.6: G[u].add(v); G[v].add(u)
G[0].add(n - 1); G[n - 1].add(0)
return G
print(" n max checks per verify orders tried checks in search found")
for n in range(4, 11):
G, checks = no_path_graph(n), 0
found = any(v_hampath(G, 0, n - 1, (0,) + m + (n - 1,))
for m in permutations(range(1, n - 1)))
tried = factorial(n - 2)
print(f"{n:2} {n:21} {tried:12} {checks:16} {found}")আসল আউটপুট (ব্রাউজারের Python):
n max checks per verify orders tried checks in search found
4 4 2 6 False
5 5 6 20 False
6 6 24 72 False
7 7 120 384 False
8 8 720 2678 False
9 9 5040 16250 False
10 10 40320 120387 False
একটি certificate মেলাতে বড়জোর n-টি check লাগে, যা n-এর সঙ্গে রৈখিক হারে বাড়ে। কিন্তু “কোনো রুট নেই” বলতে brute force-কে (n − 2)!-টি ক্রম দেখতে হয়েছে: n = ১০-এ ৪০,৩২০টি ক্রম আর এক লাখ বিশ হাজারের বেশি check. অনেক ক্রম প্রথম কয়েকটি check-এই বাদ পড়ে, তাই মোট check (n − 2)! × n-এর চেয়ে কম, তবু বৃদ্ধি factorial-এর। একটি সতর্কতা: এটি একটি নির্দিষ্ট (বোকা) algorithm-এর হিসাব, HAMPATH-এর কঠিনতার প্রমাণ নয়। চতুর algorithm (যেমন dynamic programming-এ মোটামুটি 2n · n2) অনেক ভালো করে, কিন্তু কোনো জানা algorithm সবচেয়ে খারাপ ক্ষেত্রে polynomial নয়।
৪ · NP-এর আরও সদস্য — CLIQUE, SUBSET-SUM, COMPOSITES আর SAT
একটি সমস্যা NP-তে, তা দেখানোর ছক সবসময় একই: (ক) certificate কী, তা বলুন; (খ) এর দৈর্ঘ্য input-এর polynomial, তা দেখান; (গ) verifier লিখুন আর তার সময় polynomial, তা দেখান; (ঘ) দুই দিক যুক্তি দিন: w ∈ L হলে ভালো c আছে, আর w ∉ L হলে কোনো c চলে না। নিচের সারণিতে পাঁচটি ক্লাসিক উদাহরণ।
| Language | “হ্যাঁ”-instance | Certificate | Verifier যা মেলায় |
|---|---|---|---|
| HAMPATH | ⟨G, s, t⟩, s থেকে t Hamiltonian path আছে | m vertex-এর একটি ক্রম | প্রান্ত, পুনরাবৃত্তি নেই, পরপর edge; O(m) খোঁজ |
| CLIQUE | ⟨G, k⟩, G-এ k আকারের clique আছে | k-টি vertex | k-টি আলাদা, আর k(k − 1)/2 জোড়ার প্রতিটি edge |
| SUBSET-SUM | ⟨S, t⟩, S-এর কিছু সংখ্যার যোগফল ঠিক t | প্রতিটি সংখ্যার জন্য একটি bit | বাছাই করা সংখ্যার binary যোগ, তারপর t-এর সঙ্গে তুলনা |
| COMPOSITES | ⟨n⟩, n > 1 যৌগিক | একটি p, 1 < p < n | একটি ভাগ: n mod p = 0? |
| SAT | ⟨φ⟩, Boolean সূত্র φ satisfiable | প্রতিটি চলকের মান | মান বসিয়ে φ-এর মান বের করা |
CLIQUE. CLIQUE = {⟨G, k⟩ : G-এ k-টি vertex আছে, যাদের প্রতিটি জোড়া edge দিয়ে যুক্ত}. Certificate k-টি vertex-এর নাম, দৈর্ঘ্য ≤ input-এর দৈর্ঘ্য। Verifier k(k − 1)/2 ≤ m2 জোড়া দেখে। দুই দিক: G-এ k-clique থাকলে সেটিই c; না থাকলে যেকোনো k-টি vertex-এর মধ্যে অন্তত একটি জোড়া যুক্ত নয়, আর V সেটি ধরবে। verifiers.py-তে {G, T, M} গৃহীত, {D, G, T} বর্জিত।
SUBSET-SUM. SUBSET-SUM = {⟨S, t⟩ : S = {x1, …, xm} সংখ্যার একটি collection, আর এমন একটি উপ-collection আছে যার যোগফল t}. সংখ্যাগুলো binary-তে লেখা। বাজারঘরের ভাষায়: একটি ট্রাকে ঠিক t কেজি ভরতে হবে, পার্সেল ভাঙা যাবে না। Certificate m-টি bit, আর verifier বড়জোর m-টি binary যোগ করে, প্রতিটি সংখ্যার bit-দৈর্ঘ্যের রৈখিক সময়ে; সব মিলিয়ে সময় input-দৈর্ঘ্যের polynomial-এ সীমিত থাকে। একটি ফাঁদ এখানে: subset sum-এর পরিচিত dynamic programming O(m · t) সময় নেয়, যা t-এর মানের polynomial, কিন্তু t-এর bit-দৈর্ঘ্যের নয়, কারণ t-এর মান তার দৈর্ঘ্যের সূচকীয়। এটি pseudo-polynomial সময়; তাই সেই DP দেখে SUBSET-SUM ∈ P বলা যায় না।
COMPOSITES. COMPOSITES = {⟨n⟩ : n = pq, যেখানে p, q > 1}. Certificate একটি গুণনীয়ক p; verifier একটি ভাগ করে, যা n-এর bit-দৈর্ঘ্য k-এর O(k2) bit-কাজ। এটি পর্ব ৪৬-এর guess and verify উদাহরণের verifier রূপ। মনে রাখুন, NP-তে থাকা মানে কঠিন হওয়া নয়: Agrawal, Kayal আর Saxena ২০০২ সালে দেখান যে মৌলিকতা polynomial সময়ে নির্ণয় করা যায়, তাই COMPOSITES ∈ P.
SAT. SAT = {⟨φ⟩ : φ একটি satisfiable Boolean সূত্র}. যেমন φ = (x ∨ y) ∧ (¬x ∨ z) ∧ (¬y ∨ ¬z). Certificate: x = 1, y = 0, z = 1. Verifier মান বসায়: x ∨ y = 1, ¬x ∨ z = 0 ∨ 1 = 1, ¬y ∨ ¬z = 1 ∨ 0 = 1; তিনটি clause-ই সত্য, তাই গ্রহণ। সূত্রের মান বের করা সূত্রের দৈর্ঘ্যের প্রায় রৈখিক কাজ। পর্ব ৬০ (Cook–Levin theorem) দেখাবে, SAT NP-এর সবচেয়ে কঠিন সমস্যাগুলোর একটি।
একটি সত্যিকারের library দিয়ে যাচাই। নিজের verifier-এর ভুল ধরতে একটি স্বাধীন উৎসের সঙ্গে মেলানো ভালো অভ্যাস। networkx (BSD-3-Clause licence) Python-এর পরিচিত graph library; এতে কোনো usage-reporting বা network কোড নেই। uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টি ৩০০টি random graph বানায় (৮টি vertex, প্রতিটি জোড়ায় edge-এর সম্ভাবনা 0.45, seed স্থির)। প্রতিটি graph-এ ২০টি random ক্রম আর brute force-এ পাওয়া বৈধ রুট (বড়জোর ৫টি) certificate হিসেবে দুইভাবে মেলানো হয়: আমাদের v_hampath দিয়ে, আর networkx-এর is_simple_path দিয়ে (সঙ্গে দৈর্ঘ্য আর দুই প্রান্তের পরীক্ষা)। 4-clique আছে কি না, তা আমাদের brute force আর networkx-এর নিজস্ব find_cliques দুইভাবে নির্ণয় করা হয়।
import networkx as nx
# v_hampath and v_clique: the same verifiers as in verifiers.py
rng = random.Random(58)
for g in range(graphs): # graphs = 300, n = 8
G = nx.gnp_random_graph(n, 0.45, seed=rng.randrange(10**9))
s, t, k = 0, n - 1, 4
tests = [tuple(rng.sample(range(n), n)) for _ in range(20)]
tests += [(s,) + m + (t,) for m in permutations(range(1, n - 1))
if v_hampath(G, s, t, (s,) + m + (t,))][:5] # real paths too
for p in tests:
certs += 1
ref = len(p) == n and p[0] == s and p[-1] == t and nx.is_simple_path(G, list(p))
agree_h += v_hampath(G, s, t, p) == ref; acc += ref
# ... yes_h: brute force over all orders, as in verifiers.py
mine = any(v_clique(G, k, c) for c in combinations(range(n), k))
ref = max(len(c) for c in nx.find_cliques(G)) >= k # networkx's own search
agree_c += mine == ref; yes_c += mineসত্যিকারের run (ডেস্কটপ, networkx 3.7, Python 3.12.13):
~/bazarghar-toc$ uv run python check_certs.py
python 3.12.13 | networkx 3.7
300 random graphs G(8, 0.45), s = 0, t = 7
HAMPATH certificates checked: 6445, verifier agrees with networkx: 6445 (445 valid)
graphs with an s-t Hamiltonian path (brute force): 139
4-clique exists: brute force + verifier agrees with nx.find_cliques on 300/300 graphs (100 yes)
৬,৪৪৫টি certificate-এর প্রতিটিতে দুই পদ্ধতি একমত, যার ৪৪৫টি বৈধ রুট আর বাকিগুলো বর্জিত random ক্রম। ৩০০টি graph-এর ১৩৯টিতে 0 থেকে 7 পর্যন্ত Hamiltonian path আছে। 4-clique-এর প্রশ্নে ৩০০টির সবকটিতে একমত, ১০০টিতে “হ্যাঁ”। মিল মানে আমাদের verifier সঠিক, এমন প্রমাণ নয়; কিন্তু হাজার হাজার ক্ষেত্রে একটি স্বাধীন implementation-এর সঙ্গে মিল একটি off-by-one বা ভুল-প্রান্তের bug ধরার জন্য যথেষ্ট শক্ত পরীক্ষা।
৫ · মূল উপপাদ্য — NP = polynomial সময়ের NTM
NP নামের ইতিহাস অন্য সংজ্ঞা থেকে। পর্ব ৪৬-এ nondeterministic Turing machine-এর running time ঠিক করা হয়েছিল: decider NTM-এর জন্য, দৈর্ঘ্য n-এর যেকোনো input-এ যেকোনো শাখার সর্বোচ্চ ধাপসংখ্যা, অর্থাৎ সবচেয়ে লম্বা শাখা, ভাগ্যবান শাখা নয়।
NTIME(t(n)) = {L : L-কে একটি O(t(n)) সময়ের nondeterministic single-tape Turing machine decide করে}.
NP = ⋃k NTIME(nk).
একইভাবে deterministic যন্ত্রে TIME(t(n)), আর P = ⋃k TIME(nk) (পর্ব ৫৭)।
একটি language-এর polynomial-time verifier আছে, যদি এবং কেবল যদি কোনো polynomial সময়ের NTM তাকে decide করে। অর্থাৎ সংজ্ঞা ২.২ আর সংজ্ঞা ৫.১ একই শ্রেণি NP দেয়।
ধারণাটি পর্ব ৪৬-এর guess and verify: NTM-এর অনুমান = certificate, আর deterministic অংশ = verifier. প্রমাণের দুই দিক আলাদা করে লেখা হলো।
প্রমাণ, দিক ১ (verifier ⇒ NTM): ধরুন V একটি verifier, যা q(n) সময়ে চলে আর |c| ≤ p(n) দৈর্ঘ্যের certificate নেয়; সাধারণতা না হারিয়ে c-কে {0, 1}-এর ওপর string ধরা যায়। N-এর বর্ণনা: “input w-এ, যেখানে |w| = n:
- Nondeterministic ভাবে দৈর্ঘ্য বড়জোর p(n)-এর একটি string c বাছাই করে tape-এ লেখা (প্রতিটি ধাপে তিনটি পছন্দ: 0 লেখা, 1 লেখা, বা থামা)।
- ⟨w, c⟩-এ V চালানো।
- V গ্রহণ করলে গ্রহণ; নইলে বর্জন।”
- সময়: ধাপ ১-এ প্রতিটি শাখা O(p(n)) ধাপ নেয়; ধাপ ২-এ বড়জোর q(n) ধাপ, সঙ্গে tape-এ ⟨w, c⟩ সাজানোর polynomial খরচ। তাই প্রতিটি শাখা polynomial সময়ে থামে, আর N একটি polynomial সময়ের decider. — polynomial-এর যোগ, গুণ আর বর্গ polynomial
- w ∈ L হলে এমন c আছে, |c| ≤ p(n), যা V গ্রহণ করে; N-এর যে শাখা ধাপ ১-এ ঠিক এই c লেখে, সেটি গ্রহণ করে। তাই N w গ্রহণ করে। — সম্পূর্ণতা
- N w গ্রহণ করলে কোনো শাখা গ্রহণ করেছে; সেই শাখা কোনো c লিখেছিল, |c| ≤ p(n), আর V ⟨w, c⟩ গ্রহণ করেছে। তাই w ∈ L. — নির্ভরযোগ্যতা ∎
নিচের stepper এই N-এর computation tree খোলে, SUBSET-SUM-এর ছোট instance S = (4, 7, 9), t = 16-এ। সরলতার জন্য certificate-এর দৈর্ঘ্য ঠিক m = 3 (প্রতিটি সংখ্যার একটি bit), তাই প্রতিটি অনুমান-ধাপে দুটি পছন্দ।
1পরের bit অনুমান: 0 বা 12m-টি bit হলে অনুমান শেষ3প্রতিটি পাতায় V চালানো4V গ্রহণ করলে সেই শাখা গ্রহণ
| গভীরতা | |
| শাখা | |
| মোট node |
- গভীরতা ০. Root: input ⟨(4, 7, 9), 16⟩ পড়া হয়েছে, certificate এখনো ফাঁকা (ε)।
- প্রথম অনুমান। প্রথম সংখ্যা 4 নেওয়া হবে কি না: দুটি শাখা, 0 আর 1. গাছে এখন ৩টি node.
- দ্বিতীয় অনুমান। 7-এর জন্য আবার ভাগ। চারটি শাখা: 00, 01, 10, 11; মোট node ৭.
- তৃতীয় অনুমান। 9-এর জন্য ভাগ। ৮টি পাতা, মোট 24 − 1 = ১৫টি node. প্রতিটি পাতা একটি সম্ভাব্য certificate. এ পর্যন্ত প্রতিটি শাখা মাত্র ৩ ধাপ চলেছে।
- যাচাই। প্রতিটি পাতায় deterministic V চলে। যোগফল 0, 9, 7, 16, 4, 13, 11, 20; শুধু 011 (7 + 9) লক্ষ্য 16 মেলায়। একটি শাখা গ্রহণ করেছে, তাই N গ্রহণ করে।
- “না”-এর ছবি। t = 15 হলে একই গাছ, কিন্তু কোনো পাতার যোগফল 15 নয়: সব ৮টি শাখা বর্জন করে, আর তখনই N বর্জন করে। প্রতিটি শাখা ছোট; বড় হলো শাখার সংখ্যা।
প্রমাণ, দিক ২ (NTM ⇒ verifier): ধরুন N একটি NTM, যা L decide করে আর প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ বড়জোর nk ধাপে থামে; b = N-এর সর্বোচ্চ branching factor. V-এর বর্ণনা: “input ⟨w, c⟩-এ, যেখানে c হলো {1, …, b}-এর ওপর একটি string:
- w-এ N-কে deterministic ভাবে চালানো: প্রতিটি ধাপে c-এর পরের চিহ্ন দেখে δ-এর সেই নম্বরের পছন্দ নেওয়া (পর্ব ৪৬-এর address-এর মতো)।
- পছন্দটি অবৈধ হলে, বা c ফুরিয়ে গেলে শাখা না থামলে, বর্জন।
- এই শাখা qaccept-এ পৌঁছালে গ্রহণ; qreject-এ পৌঁছালে বর্জন।”
- Certificate-এর দৈর্ঘ্য: একটি গ্রহণকারী শাখা বড়জোর nk ধাপের, তাই তার address-এর দৈর্ঘ্য ≤ nk = p(n). — running time-এর সংজ্ঞা: সব শাখা ≤ nk
- সময়: V N-এর একটিমাত্র শাখা চালায়, বড়জোর nk ধাপ, প্রতিটিতে c-এর একটি চিহ্ন পড়ে; multi-tape-এ O(nk), single-tape-এ polynomial সময়ে। — পর্ব ৪৫
- w ∈ L ⇒ N-এর কোনো শাখা গ্রহণ করে; তার address-ই c, আর V ⟨w, c⟩ গ্রহণ করে। — সম্পূর্ণতা
- V ⟨w, c⟩ গ্রহণ করে ⇒ c একটি বৈধ শাখার পছন্দ-ক্রম, যা qaccept-এ পৌঁছায়; তাই N w গ্রহণ করে, w ∈ L. — নির্ভরযোগ্যতা ∎
দিক ২-এর stepper পর্ব ৪৬-এর চেনা যন্ত্র নেয়: N1′, যা {w : w-এ পাশাপাশি দুটি 1 আছে} decide করে (q0-তে 0 পড়ে এগোনো; 1 পড়ে পছন্দ ১ এগোনো, পছন্দ ২ অনুমান “জোড়া এখানে”, অর্থাৎ q1; q1-এ 1 পড়ে গ্রহণ; বাকি সব বর্জন)। পর্ব ৪৬-এ 011-এর গ্রহণকারী শাখার address ছিল 121. এখানে সেটিই certificate.
1c-এর পরের চিহ্ন a পড়া2δ-এ a-তম পছন্দ নেই: বর্জন3a-তম পছন্দে N-এর এক ধাপ4qacc: গ্রহণ; c ফুরোলে বা qrej: বর্জন
| certificate | |
| configuration | |
| পছন্দ আছে |
- শুরু। V পায় w = 011 আর c = 121. N1′-এর শুরুর configuration [q0]011; c-এর প্রথম চিহ্নে আঙুল।
- চিহ্ন 1. δ(q0, 0)-এ একটিই move; প্রথমটি নেওয়া হলো: 0[q0]11.
- চিহ্ন 2. δ(q0, 1)-এ দুটি move; certificate বলছে দ্বিতীয়টি, অর্থাৎ অনুমান “জোড়া এখানে শুরু”: 01[q1]1. NTM-এর “ভাগ্যবান অনুমান” এখানে certificate-এর একটি অঙ্ক মাত্র।
- চিহ্ন 1, গ্রহণ। δ(q1, 1)-এর একমাত্র move: 011[qacc]␣. শাখাটি গ্রহণ করেছে, তাই V গ্রহণ করে। মোট ৩ ধাপ, |c| = 3 ≤ |w| + 1.
- খারাপ certificate ১. c = 111 হলে তিনবারই পছন্দ ১: যন্ত্র 011[q0]␣-এ পৌঁছায়, আর c ফুরিয়ে যায়, শাখা গ্রহণ করেনি: V বর্জন করে। কিন্তু 011 এখনো L-এ; একটি খারাপ c কিছুই প্রমাণ করে না।
- খারাপ certificate ২. c = 211: প্রথম ধাপেই δ(q0, 0)-এ দ্বিতীয় পছন্দ চাওয়া হলো, যা নেই। V বর্জন করে।
দুই দিকই এবার code-এ। প্রথম ব্লক যেকোনো verifier থেকে NTM-এর গাছ বানায় (দিক ১), আর দ্বিতীয় ব্লক NTM থেকে verifier বানায় (দিক ২) এবং দৈর্ঘ্য ৮ পর্যন্ত প্রতিটি string-এ “∃c, V গ্রহণ করে” আর সংজ্ঞাকে মেলায়।
# Verifier -> NTM: N guesses the certificate one bit per step,
# then runs the deterministic verifier V on (w, c). We expand N's tree by BFS.
def v_subset(w, bits): # w = (S, t); c = one bit per number
S, t = w
return sum(x for x, b in zip(S, bits) if b == "1") == t
def ntm_from_verifier(V, w, m, verbose=False): # m = certificate length
level, nodes = [""], 1 # a node = the bits guessed so far
for depth in range(1, m + 1): # guessing stage: 2 children per node
level = [c + b for c in level for b in "01"]
nodes += len(level)
if verbose: print(f"depth {depth}: {len(level)} branches", level[:8])
accepting = [c for c in level if V(w, c)] # verify stage at each leaf
return ("ACCEPT" if accepting else "REJECT"), nodes, accepting
print(ntm_from_verifier(v_subset, ((4, 7, 9), 16), 3, verbose=True))
print(ntm_from_verifier(v_subset, ((4, 7, 9), 15), 3))
print(ntm_from_verifier(v_subset, ((3, 5, 8, 11, 14), 24), 5))
for m in (10, 14, 18):
S = tuple(range(1, m + 1)); t = 2 * m + 1 # a "yes" instance
verdict, nodes, acc = ntm_from_verifier(v_subset, (S, t), m)
print(f"m={m:2}: {verdict}, tree nodes {nodes:8}, accepting leaves {len(acc)}")আসল আউটপুট (ব্রাউজারের Python):
depth 1: 2 branches ['0', '1']
depth 2: 4 branches ['00', '01', '10', '11']
depth 3: 8 branches ['000', '001', '010', '011', '100', '101', '110', '111']
('ACCEPT', 15, ['011'])
('REJECT', 15, [])
('ACCEPT', 63, ['01110'])
m=10: ACCEPT, tree nodes 2047, accepting leaves 33
m=14: ACCEPT, tree nodes 32767, accepting leaves 146
m=18: ACCEPT, tree nodes 524287, accepting leaves 507
প্রথম চার লাইন stepper-এর ধাপ ২–৫: ১৫টি node আর একমাত্র গ্রহণকারী পাতা 011. t = 15-এ সব পাতা বর্জিত। বাজারঘরের পাঁচ পার্সেলে (t = 24) ৬৩টি node আর একটি গ্রহণকারী পাতা, verifiers.py-র brute force-এর সঙ্গে মিলে যায়। শেষ তিন লাইনে S = (1, 2, …, m), t = 2m + 1: N-এর প্রতিটি শাখা মাত্র m-টি অনুমান আর একটি যোগ, কিন্তু গাছের node 2m+1 − 1, m = ১৮-এ পাঁচ লাখের বেশি। NTM-এর “সময়” একটি শাখার দৈর্ঘ্য; deterministic simulation-এর সময় গাছের আকার। (গ্রহণকারী পাতার সংখ্যা ৩৩, ১৪৬, ৫০৭ একটি আলাদা DP দিয়ে scratch-এ মেলানো।)
# NTM -> verifier: the certificate is the address of an accepting branch.
from itertools import product
B = "␣"
N1d = {("q0", "0"): [("q0", "0", "R")], # N1' from part 46: accept
("q0", "1"): [("q0", "1", "R"), ("q1", "1", "R")], # iff w has 11
("q0", B): [("qrej", B, "R")],
("q1", "1"): [("qacc", "1", "R")],
("q1", "0"): [("qrej", "0", "R")], ("q1", B): [("qrej", B, "R")]}
def V(N, w, c, verbose=False): # deterministic: follow the choices in c
q, tape, h = "q0", list(w + B), 0
for a in c:
if q in ("qacc", "qrej"): break
opts = N.get((q, tape[h]), [])
if int(a) > len(opts): return "reject (bad choice)"
q, tape[h], m = opts[int(a) - 1]
h = h + 1 if m == "R" else max(h - 1, 0)
if h == len(tape): tape.append(B)
if verbose: # u[q]v, trailing blanks trimmed
t = "".join(tape).rstrip(B).ljust(h + 1, B)
print(f" choice {a}: {t[:h]}[{q}]{t[h:]}")
return "accept" if q == "qacc" else "reject"
print("w=011, c=121:"); print(V(N1d, "011", "121", verbose=True))
print("w=011, c=111:", V(N1d, "011", "111"))
print("w=011, c=211:", V(N1d, "011", "211"))
def exists_cert(N, w): # p(n) = n + 1 bounds every branch of N1'
return any(V(N, w, "".join(c)) == "accept"
for k in range(len(w) + 2) for c in product("12", repeat=k))
words = ["".join(t) for k in range(9) for t in product("01", repeat=k)]
print(len(words), "strings; (exists c, |c| <= n+1, V accepts) == ('11' in w):",
all(exists_cert(N1d, w) == ("11" in w) for w in words))আসল আউটপুট (ব্রাউজারের Python):
w=011, c=121:
choice 1: 0[q0]11
choice 2: 01[q1]1
choice 1: 011[qacc]␣
accept
w=011, c=111: reject
w=011, c=211: reject (bad choice)
511 strings; (exists c, |c| <= n+1, V accepts) == ('11' in w): True
তিনটি configuration লাইন stepper-এর ধাপ ২–৪-এর সঙ্গে হুবহু এক, আর 111 ও 211 ধাপ ৫–৬. শেষ লাইনটি উপপাদ্যের দিক ২-এর ছোট পরীক্ষা: N1′-এর প্রতিটি শাখা বড়জোর n + 1 ধাপে থামে, তাই দৈর্ঘ্য ≤ n + 1-এর সব certificate দেখলেই যথেষ্ট; দৈর্ঘ্য ০ থেকে ৮-এর ৫১১টি string-এর প্রতিটিতে “কোনো c V-কে রাজি করায়” ঠিক তখনই সত্য, যখন w-এ 11 আছে। এই পরীক্ষাটি নিজেই সব certificate খুঁজে দেখে, তাই এটি সূচকীয়; verifier V নিজে একটি certificate-এ মাত্র কয়েক ধাপ চলে।
৬ · P ⊆ NP ⊆ EXP — প্রমাণ আর অজানা সীমানা
EXP = ⋃k TIME(2nk), অর্থাৎ deterministic যন্ত্র সূচকীয় সময়ে যা decide করে। EXP-এর সঙ্গে P আর NP-এর সম্পর্ক এই পর্বের দুটি সহজ কিন্তু মৌলিক উপপাদ্য।
P ⊆ NP ⊆ EXP.
প্রমাণ (P ⊆ NP):
- ধরুন L ∈ P, আর M একটি deterministic decider, যা L-কে nk সময়ে decide করে। — P-এর সংজ্ঞা
- V ⟨w, c⟩: “c উপেক্ষা করে w-এ M চালানো, M-এর উত্তরই উত্তর।” p(n) = 0, অর্থাৎ certificate ε. — গঠন
- w ∈ L ⇔ M w গ্রহণ করে ⇔ V ⟨w, ε⟩ গ্রহণ করে; আর V-এর সময় M-এর সময়ই। তাই V একটি polynomial-time verifier, L ∈ NP. (যন্ত্রের ভাষায় আরও সংক্ষেপে: প্রতিটি DTM একটি NTM, যার প্রতিটি δ-set-এ বড়জোর একটি move.) ∎
প্রমাণ (NP ⊆ EXP):
- ধরুন L ∈ NP, verifier V-এর সময় q(n) আর certificate-এর সীমা p(n), দুটিই polynomial; certificate {0, 1}-এর ওপর। — সংজ্ঞা ২.২
- Deterministic D: “w-এ, দৈর্ঘ্য ০ থেকে p(n)-এর প্রতিটি c-এ (shortlex ক্রমে) V ⟨w, c⟩ চালানো; কোনোটি গ্রহণ করলে গ্রহণ, সব শেষে বর্জন।” — brute force over certificates
- D সঠিক: w ∈ L ⇔ কোনো c, |c| ≤ p(n), V-কে রাজি করায় ⇔ D গ্রহণ করে। V decider বলে প্রতিটি চেষ্টা থামে, তাই D-ও decider. — সংজ্ঞা ২.২
- সময়: certificate বড়জোর 2p(n)+1 − 1টি, প্রতিটিতে q(n)-এর মতো ধাপ (সঙ্গে c লেখার polynomial খরচ)। মোট 2p(n)+1 · poly(n) ≤ 2nk কোনো k-এর জন্য, যেহেতু poly(n) = 2O(log n). তাই L ∈ EXP. ∎
পর্ব ৪৬-এর উপপাদ্য ৭.১ (t(n) সময়ের NTM ⇒ 2O(t(n)) সময়ের DTM) থেকেও NP ⊆ EXP সরাসরি আসে; এখানে verifier-এর ভাষায় একই কাজ। নিচের stepper D-কে S = (4, 7, 9), t = 16-এ চালায়।
1পরের certificate c (shortlex)2V(w, c) চালানো3গ্রহণ করলে D ACCEPT
| c | |
| বাছাই | |
| যোগফল | |
| চেষ্টা / সর্বোচ্চ |
- c = 000. কিছুই বাছাই হয়নি, যোগফল 0 ≠ 16. V বর্জন করে; D থামে না, পরের certificate নেয়।
- c = 001. শুধু 9; যোগফল 9. আবার বর্জন।
- c = 010. শুধু 7; যোগফল 7. বর্জন।
- c = 011. 7 আর 9; যোগফল 16 = t. V গ্রহণ করে, তাই D গ্রহণ করে, ৪টি চেষ্টায়। সবচেয়ে খারাপ ক্ষেত্রে (যেমন t = 15) D-কে সব 23 = ৮টি দেখতে হতো; m সংখ্যায় 2m-টি।
P, NP আর EXP — কী প্রমাণিত, কী অজানা
ভেতরের প্রতিটি অঞ্চল বাইরেরটির অংশ (প্রমাণিত)। দুটি সীমানা সত্যিই আলাদা কি না, তা অজানা।
শেষ লাইনের যুক্তিটি সুন্দর। Time hierarchy theorem (পর্ব ৬৭) প্রমাণ করে P ⊊ EXP, অর্থাৎ EXP-এ এমন language আছে যা P-তে নেই। যদি P = NP আর NP = EXP দুটিই সত্য হতো, তাহলে P = EXP হতো, যা মিথ্যা। তাই P ⊊ NP বা NP ⊊ EXP, অন্তত একটি সত্য; কোনটি, কেউ জানে না। P বনাম NP প্রশ্নে বেশিরভাগ গবেষক P ≠ NP মনে করেন, কিন্তু তা প্রমাণিত নয়; Clay Mathematics Institute এটিকে তাদের Millennium Prize সমস্যার তালিকায় রেখেছে (পর্ব ৬৩)।
৭ · যা সহজে NP-তে পড়ে না, আর “NP মানে non-polynomial” ভুল
ছবি ৫৮.১-এ কুমিল্লা থেকে নারায়ণগঞ্জ পর্যন্ত কোনো Hamiltonian path নেই। এই “না” উত্তরের ছোট প্রমাণ কী হবে? verifiers.py ২৪টি ক্রমের প্রতিটি বাতিল করে উত্তর দিয়েছে। এই ছোট graph-এ অবশ্য একটি চতুর যুক্তি আছে। নারায়ণগঞ্জের প্রতিবেশী শুধু কুমিল্লা আর ঢাকা, আর কুমিল্লা শুরু; তাই নারায়ণগঞ্জের ঠিক আগে ঢাকা। কুমিল্লার প্রতিবেশীও শুধু নারায়ণগঞ্জ আর ঢাকা, আর নারায়ণগঞ্জ শেষ; তাই কুমিল্লার ঠিক পরে ঢাকা। তাহলে রুটটি কুমিল্লা → ঢাকা → নারায়ণগঞ্জ, আর বাকি তিনটি জেলা বাদ পড়ে: কোনো রুট নেই। এই ছোট যুক্তিটিই এখানে “না”-এর certificate. কিন্তু সাধারণ graph-এ এমন ছোট যুক্তি সবসময় পাওয়া যাবে, এমন কোনো পদ্ধতি জানা নেই।
HAMPATH-এর complement, HAMPATH = {⟨G, s, t⟩ : G-এ s থেকে t কোনো Hamiltonian path নেই} (সঙ্গে ভুলভাবে লেখা string-ও, যা এখানে উপেক্ষা করা হলো)। coNP = {L : L-এর complement NP-তে}. বিস্তারিত পর্ব ৬২-এ।
HAMPATH NP-তে আছে কি না, কেউ জানে না। সব ক্রমের তালিকা একটি সঠিক প্রমাণ, কিন্তু তার দৈর্ঘ্য factorial, polynomial নয়। আরও সাধারণভাবে, NP = coNP কি না, তা খোলা; অধিকাংশ গবেষক মনে করেন সমান নয়, কিন্তু প্রমাণ নেই। একটি জিনিস প্রমাণিত: P complement-এ বদ্ধ (deterministic decider-এর accept আর reject অদলবদল), তাই P = NP হলে NP = coNP-ও হতো। লক্ষ করুন, NTM-এর ক্ষেত্রে এই অদলবদল কাজ করে না; সেই সতর্কতা পর্ব ৪৬-এ ছিল।
আরও কিছু প্রশ্ন, যেগুলো প্রথম দেখায় NP-তে মনে হলেও আসলে স্পষ্ট নয়:
- অপ্টিমাইজেশনের “সেরা” দাবি। “এই রুটটিই সবচেয়ে ছোট” দাবির ছোট প্রমাণ জানা নেই; কিন্তু decision রূপ “দৈর্ঘ্য ≤ k এমন রুট আছে?” NP-তে, certificate রুটটি নিজেই। তাই এই মডিউল সবসময় একটি সীমা k-সহ decision রূপ ব্যবহার করে।
- “ঠিক একটি” সমাধান। “ঠিক একটি Hamiltonian path আছে” দাবিতে একটি অংশ (অন্তত একটি) সহজে প্রমাণযোগ্য, কিন্তু অন্য অংশ (দ্বিতীয়টি নেই) “না”-ধরনের দাবি।
- Undecidable সমস্যা। ATM-এর “হ্যাঁ” উত্তরের প্রমাণ আছে: একটি গ্রহণকারী computation history (পর্ব ৫৪-এ এমন history-র ব্যবহার)। কিন্তু তার দৈর্ঘ্য w-এর কোনো polynomial দিয়ে সীমিত নয়, তাই ATM NP-তে নয়; NP-এর প্রতিটি language decidable (উপপাদ্য ৬.১)।
প্রচলিত ভুল: “NP মানে non-polynomial”, বা “NP মানে কঠিন”। NP-এর N এসেছে nondeterministic থেকে: nondeterministic polynomial time. P ⊆ NP, তাই sorting, PATH, COMPOSITES-এর মতো সহজ সমস্যাও NP-তে। “এই সমস্যা NP, তাই polynomial algorithm নেই” বাক্যটি দুইভাবে ভুল: NP-তে থাকা কঠিনতার প্রমাণ নয়, আর কঠিনতম সমস্যাগুলোর (NP-complete, পর্ব ৫৯) ক্ষেত্রেও “polynomial algorithm নেই” প্রমাণিত নয়, শুধু জানা নেই। আরেকটি বিভ্রান্তি: NP-hard আর NP এক নয়; halting problem NP-hard, কিন্তু NP-তে নয় (পর্ব ৬২)।
আরও গভীরে: Verifier-এর ধারণা complexity তত্ত্বের অনেক বড় শাখার মূল। Fagin ১৯৭৪ সালে দেখান যে NP ঠিক সেই graph-ধর্মগুলো, যা existential second-order logic-এ লেখা যায়, যেখানে “∃ একটি রুট/রং/সেট” অংশটিই certificate; এই শাখার নাম descriptive complexity. Verifier-কে randomness আর একাধিক প্রশ্নের সুযোগ দিলে আসে interactive proof (IP = PSPACE, পর্ব ৭৪), আর PCP theorem (১৯৯০-এর দশকের শুরু) দেখায় যে প্রতিটি NP certificate এমনভাবে লেখা যায়, যাতে একটি randomized verifier মাত্র স্থির সংখ্যক bit পড়ে প্রায় নিশ্চিত হতে পারে (পর্ব ৭১)। এগুলোর সবই “প্রমাণ মেলানো” প্রশ্নের নতুন রূপ।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Verifier দিয়ে NP-এর সংজ্ঞা দিন। L ∈ NP ⇔ polynomial-time V আর polynomial p আছে, যাতে w ∈ L ⇔ ∃c, |c| ≤ p(|w|), V ⟨w, c⟩ গ্রহণ করে।
- প্রমাণ করুন CLIQUE ∈ NP. Certificate k-টি vertex; verifier k(k − 1)/2 জোড়ার edge দেখে, O(m2); দুই দিকের যুক্তি।
- Verifier আর NTM সংজ্ঞা সমতুল্য কেন? NTM certificate অনুমান করে V চালায়; উল্টো দিকে গ্রহণকারী শাখার address-ই certificate.
- P ⊆ NP ⊆ EXP প্রমাণ করুন। certificate উপেক্ষা; আর 2p(n)+1 certificate একে একে চেষ্টা।
- NP কি “non-polynomial”? না; nondeterministic polynomial, আর P ⊆ NP.
৮ · AI-এর যুগে NP আর verifier
AI assistant-কে “X কি NP-তে?” জিজ্ঞেস করলে প্রায়ই আত্মবিশ্বাসী উত্তর আসে। কয়েকটি ভুল বারবার দেখা যায়: certificate ঠিক করে না বলে “এটি NP কারণ এটি কঠিন” লেখা, verifier-এর সময় certificate খোঁজাসহ গোনা, দুই দিকের একটি (সাধারণত soundness) বাদ দেওয়া, আর “NP মানে non-polynomial” বলা। মজার ব্যাপার, AI-এর নিজের উত্তর যাচাইয়ের সবচেয়ে ভালো উপায়টিও এই পর্বের মূল কথা: খোঁজার চেয়ে মেলানো সহজ। AI একটি রুট, একটি clique বা একটি satisfying assignment দাবি করলে আপনার verifier দিয়ে সেটি মিলিয়ে নিন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “NP মানে non-polynomial” বা “NP-তে, তাই polynomial algorithm নেই” | P ⊆ NP মনে রাখুন; P ≠ NP প্রমাণিত নয় |
| Certificate-এর দৈর্ঘ্যের সীমা দেয় না, বা সব সম্ভাবনার তালিকাকে certificate বলে | |c| ≤ p(|w|) আছে কি না দেখুন; তালিকার দৈর্ঘ্য গুনুন |
| Verifier-এর ভেতরে certificate খোঁজে (একটি loop সব subset-এ) | V শুধু দেওয়া c মেলায়; V-এর code-এ সব c-এর ওপর loop থাকলে সেটি verifier নয় |
| শুধু completeness দেখায়, soundness বাদ | w ∉ L হলে প্রতিটি c বর্জিত হয় কি না, একটি ছোট “না”-instance-এ সব c চালিয়ে দেখুন |
| SUBSET-SUM-এর O(m · t) DP দেখে “SUBSET-SUM ∈ P” | সংখ্যা binary-তে; t-এর মান তার দৈর্ঘ্যের সূচকীয়: pseudo-polynomial |
| “complement-ও NP-তে, কারণ accept/reject অদলবদল করা যায়” | NTM-এ অদলবদল complement দেয় না; NP = coNP খোলা |
AI-কে কাজে লাগানোর ভালো উপায়: certificate, verifier, সময়ের হিসাব আর দুই দিকের যুক্তি আলাদা আলাদা চাওয়া, আর একটি ছোট instance-এ সব certificate চালিয়ে দেখার code নিজে চালানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১NP-এর সংজ্ঞায় certificate-এর দৈর্ঘ্যের সীমা |c| ≤ p(|w|) তুলে দিলে কী হয়? শর্তটি কেন অপরিহার্য?
শর্তটি তুলে দিলে একটি নাটকীয় ঘটনা ঘটে। ধরুন verifier-কে শুধু decider হতে হবে, আর certificate যত লম্বা হোক। তখন “L = {w : ∃c, V ⟨w, c⟩ গ্রহণ করে}” আকারের language-গুলো ঠিক Turing-recognizable language. এক দিক: L-কে M চিনলে, w-এর certificate হিসেবে M-এর গ্রহণকারী computation history নিন, অর্থাৎ শুরু থেকে গ্রহণ পর্যন্ত সব configuration. একটি decider সেটি ধাপে ধাপে মেলাতে পারে: প্রথম configuration q0w কি না, প্রতিটি পরেরটি δ মেনে আগেরটি থেকে আসে কি না, আর শেষটি গ্রহণকারী কি না। অন্য দিক: এমন V থাকলে একটি recognizer সব c shortlex ক্রমে চেষ্টা করে। তাই সীমাহীন certificate নিলে ATM-এর মতো undecidable language-ও এই শ্রেণিতে ঢুকে পড়ে (পর্ব ৫০–৫১)।
Polynomial সীমা থাকলে ছবি একেবারে বদলে যায়। তখন সব certificate মিলিয়ে সংখ্যাটি সসীম, 2p(n)+1-এর মতো, তাই brute force decider বানানো যায়, আর NP ⊆ EXP (উপপাদ্য ৬.১)। অর্থাৎ certificate-এর দৈর্ঘ্যই ঠিক করে প্রশ্নটি computability-র (আদৌ সম্ভব?) না complexity-র (কত দ্রুত?)।
সময়ের সীমার দিকেও একই সূক্ষ্মতা। Sipser verifier-এর সময় মাপেন |w| দিয়ে। যদি সময় মাপা হতো |⟨w, c⟩| দিয়ে, আর certificate-এর দৈর্ঘ্যের কোনো সীমা না থাকত, তাহলে একটি সূচকীয় দৈর্ঘ্যের certificate (যেমন সব ক্রমের তালিকা) দিয়ে V সেই বিশাল input-এর “polynomial” সময়ে চলত, আর অনেক কঠিন সমস্যা কৃত্রিমভাবে “সহজে যাচাইযোগ্য” হয়ে যেত। এই পর্বের রীতিতে দুটি সীমাই স্পষ্ট লেখা: |c| ≤ p(|w|), আর V-এর সময় q(|w|)।
এখান থেকে একটি গভীর পর্যবেক্ষণ আসে: একটি complexity class-কে “প্রমাণের দৈর্ঘ্য” আর “যাচাইয়ের খরচ” দিয়ে সংজ্ঞায়িত করা যায়। পরে interactive proof আর PCP-তে (পর্ব ৭১, ৭৪) এই দুটি মাপের সঙ্গে আরও মাপ যোগ হয়: randomness-এর পরিমাণ, verifier কত bit পড়ে, কতবার প্রশ্ন করে।
মূল উপলব্ধি: সীমাহীন certificate দিলে verifier-এর শ্রেণি হয় Turing-recognizable language; polynomial সীমাই NP-কে decidable জগতে, EXP-এর ভেতরে রাখে।
প্র ০২“খোঁজা বনাম মেলানো”-র ফারাক বাস্তব জীবনে কোথায় দেখা যায়? Gödel-এর চিঠি থেকে আজকের cryptography পর্যন্ত এই প্রশ্ন কেন এত গুরুত্বপূর্ণ?
সবচেয়ে চেনা উদাহরণ গণিত নিজেই। একটি উপপাদ্যের প্রমাণ খুঁজতে বছর লাগতে পারে, কিন্তু লেখা প্রমাণ মেলানো, বিশেষত একটি formal proof checker-এ, যান্ত্রিক কাজ। ১৯৫৬ সালে Kurt Gödel John von Neumann-কে লেখা একটি চিঠিতে প্রায় এই প্রশ্নটিই তোলেন বলে পরিচিত: দৈর্ঘ্য n-এর প্রমাণ খুঁজতে একটি যন্ত্রের কত ধাপ লাগে, আর তা যদি n বা n2-এর মতো বাড়ে, তাহলে গণিতবিদের সৃজনশীল কাজের অনেকটাই যন্ত্র করতে পারত। চিঠিটি বহু বছর পরে পরিচিতি পায়; একে প্রায়ই P বনাম NP-এর একটি প্রাথমিক রূপ বলা হয়। প্রশ্নটি আজও খোলা।
দ্বিতীয় বড় উদাহরণ cryptography (cybersecurity কোর্সে এর ব্যবহার)। একটি পাসওয়ার্ড বা গোপন key সঠিক কি না, তা মেলানো সহজ; key খুঁজে বের করা কঠিন হওয়াই নিরাপত্তার ভিত্তি। এই অর্থে আধুনিক cryptography একটি বাজির ওপর দাঁড়িয়ে: কিছু NP-ধরনের সমস্যার উত্তর খোঁজা সত্যিই কঠিন। P = NP প্রমাণিত হলে, আর algorithm-টি বাস্তবে দ্রুত হলে, অনেক প্রচলিত পদ্ধতি দুর্বল হয়ে পড়ত। তবে উল্টোটা সত্য নয়: P ≠ NP প্রমাণিত হলেও cryptography নিরাপদ, এমন নয়। Cryptography-র দরকার average-case কঠিনতা আর one-way function, যা P ≠ NP-এর চেয়ে শক্ত অনুমান (পর্ব ৭৬)।
তৃতীয় উদাহরণ প্রতিদিনের engineering. বাজারঘরের ডেলিভারি পরিকল্পনা, পরীক্ষার রুটিন বানানো, কারখানার shift সাজানো: এসব সমস্যায় একটি প্রস্তাবিত সমাধান মেলানো সহজ (সব শর্ত মানা হয়েছে কি না), কিন্তু সেরা বা আদৌ একটি সমাধান খুঁজতে solver দরকার। বাস্তবে SAT solver আর ILP solver অনেক বড় instance-ও প্রায়ই দ্রুত সমাধান করে (পর্ব ৭৩), কিন্তু তাদের উত্তরও আমরা একটি সহজ verifier দিয়ে মিলিয়ে নিই। Software testing-এ একে “test oracle” সমস্যার সঙ্গে তুলনা করা যায়: উত্তর তৈরি করা কঠিন, মেলানো সহজ হলে স্বয়ংক্রিয় পরীক্ষা সম্ভব।
লক্ষ করুন, সব ক্ষেত্রে “সহজ মেলানো” আসলে একটি নিরাপত্তা জাল: কে সমাধান দিল, মানুষ, AI বা অজানা কোনো program, তা নিয়ে ভাবতে হয় না।
মূল উপলব্ধি: খোঁজা আর মেলানোর ফারাক গণিত, cryptography আর প্রকৌশলের ভিত্তি; এই ফারাক সত্যিই অনিবার্য কি না, সেটিই P বনাম NP, যা Gödel-এর ১৯৫৬ সালের চিঠি থেকে আজও খোলা।
প্র ০৩“না” উত্তরের ছোট প্রমাণ কখন থাকে? মৌলিক সংখ্যা, factoring আর Hamiltonian path-এর তুলনা থেকে কী শেখা যায়?
NP-এর সংজ্ঞা শুধু “হ্যাঁ” উত্তরের প্রমাণ চায়। কিছু সমস্যায় “না”-এরও ছোট প্রমাণ আছে, আর তখন সমস্যাটি NP ∩ coNP-তে। মৌলিক সংখ্যার গল্প এর সুন্দর উদাহরণ। COMPOSITES-এর certificate একটি গুণনীয়ক, তাই COMPOSITES ∈ NP. কিন্তু “n মৌলিক” দাবির প্রমাণ কী? প্রথম দেখায় “কোনো গুণনীয়ক নেই” বলতে সব সম্ভাবনা বাদ দিতে হয়। Vaughan Pratt ১৯৭৫ সালে দেখান যে মৌলিকতারও ছোট certificate আছে: n − 1-এর মৌলিক গুণনীয়কগুলো আর একটি primitive root, আর সেই গুণনীয়কগুলোর মৌলিকতার একই ধরনের পুনরাবৃত্ত প্রমাণ। তাই PRIMES ∈ NP ∩ coNP. ২০০২ সালে Agrawal, Kayal আর Saxena আরও এগিয়ে দেখান PRIMES ∈ P.
Factoring-এর decision রূপ, যেমন “n-এর কি k-এর চেয়ে ছোট কোনো গুণনীয়ক আছে (1-এর বেশি)?”, NP ∩ coNP-তে আছে বলে জানা: “হ্যাঁ”-এর certificate সেই গুণনীয়ক, আর “না”-এর certificate n-এর পুরো মৌলিক উৎপাদক-বিশ্লেষণ, সঙ্গে প্রতিটি মৌলিকের প্রমাণ। অথচ factoring-এর কোনো polynomial algorithm জানা নেই, আর অনেক cryptography এর কঠিনতার ওপর নির্ভর করে। তাই NP ∩ coNP-তে থাকা মানে P-তে থাকা, এমন প্রমাণ নেই; P = NP ∩ coNP কি না, তা-ও খোলা।
HAMPATH ঠিক উল্টো ছবি দেখায়। “হ্যাঁ”-এর certificate রুট; কিন্তু “না”-এর জন্য কোনো ছোট certificate জানা নেই। অংশ ৭-এ ছোট graph-এ একটি চতুর যুক্তি পাওয়া গেছে, কিন্তু সাধারণ ক্ষেত্রে এমন যুক্তি থাকবে, তা বিশ্বাস করার কারণ কম। পর্ব ৫৯–৬১-এ দেখবেন, HAMPATH NP-complete; আর কোনো NP-complete সমস্যা coNP-তে থাকলে NP = coNP হয়ে যেত, যা অধিকাংশ গবেষক অসম্ভাব্য মনে করেন (কিন্তু প্রমাণিত নয়)।
এই তুলনা একটি ব্যবহারিক নিয়ম দেয়: কোনো সমস্যার দুই দিকেরই ছোট প্রমাণ থাকলে, সেটি সম্ভবত NP-complete নয়, আর তার জন্য ভালো algorithm খোঁজা অর্থবহ হতে পারে। Linear programming-এর decision রূপ এমন একটি ক্ষেত্র ছিল: duality-র কারণে দুই দিকের certificate জানা ছিল, আর পরে Khachiyan ১৯৭৯ সালে polynomial algorithm দেন।
মূল উপলব্ধি: “না”-এর ছোট প্রমাণ থাকা (coNP) প্রায়ই একটি সমস্যার গঠনের গভীর খবর দেয়; PRIMES শেষে P-তে এসেছে, factoring NP ∩ coNP-তে থেকেও কঠিন মনে হয়, আর HAMPATH-এর “না”-এর ছোট প্রমাণ জানা নেই।
প্র ০৪Verifier আর NTM, দুই সংজ্ঞাই কেন রাখা হয়? প্রত্যেকটি কোন কাজে সুবিধা দেয়, আর ইতিহাসে কোনটি আগে এসেছিল?
ইতিহাসে দুটি ধারণা প্রায় একসঙ্গে বেড়েছে। ১৯৬৫ সালে Jack Edmonds matching-এর প্রবন্ধে polynomial সময়কে “ভালো algorithm”-এর মাপকাঠি হিসেবে প্রস্তাব করেন, আর অন্য একটি প্রবন্ধে “good characterization” নিয়ে লেখেন বলে পরিচিত, যেখানে একটি দাবির দুই দিকেরই সহজে যাচাইযোগ্য প্রমাণ থাকে; এটি আজকের NP ∩ coNP-এর কাছাকাছি ধারণা। Stephen Cook ১৯৭১ সালে NTM দিয়ে সংজ্ঞা দিয়ে দেখান যে SAT এই শ্রেণির সবচেয়ে কঠিন সমস্যাগুলোর একটি; Leonid Levin সোভিয়েত ইউনিয়নে প্রায় একই সময়ে “search problem” রূপে স্বাধীনভাবে একই ধরনের ফল পান, প্রকাশ ১৯৭৩। Levin-এর রূপটি আসলে verifier-এর ভাষার কাছাকাছি: একটি instance আর একটি সমাধান-প্রার্থী দিলে সহজে মেলানো যায়। Richard Karp ১৯৭২ সালে ২১টি সমস্যার জন্য একই ফল দেখান, আর P ও NP নামগুলো এরপর ব্যাপক প্রচলিত হয় বলে পরিচিত।
দুই সংজ্ঞার সুবিধা আলাদা। Verifier সংজ্ঞা দিয়ে একটি নির্দিষ্ট সমস্যা NP-তে, তা দেখানো সহজ: certificate বলুন, verifier লিখুন, দুই দিক যুক্তি দিন। এতে কোনো যন্ত্রের নকশা লাগে না, আর বাস্তব প্রোগ্রামারের কাছেও ভাষাটি স্বাভাবিক: “একটি সমাধান দিলে আমি দ্রুত মেলাতে পারি”। অংশ ৪-এর সারণির প্রতিটি সারি এভাবেই লেখা।
NTM সংজ্ঞা দিয়ে NP-কে বাকি complexity তত্ত্বের সঙ্গে জোড়া সহজ। NTIME(t(n)) আর TIME(t(n)) পাশাপাশি রাখা যায়; space-এর জন্য NSPACE আর Savitch-এর উপপাদ্য (পর্ব ৬৪) একই ছাঁচে আসে; Cook–Levin theorem-এর tableau প্রমাণ (পর্ব ৬০) সরাসরি NTM-এর configuration দিয়ে লেখা। NTM-এর ভাষা ছাড়া “polynomial সময়ের যেকোনো NP সমস্যাকে SAT-এ রূপান্তর” প্রমাণ লেখা কঠিন হতো, কারণ তখন verifier-কেই একটি Turing machine ধরে তার গণনাকে সূত্রে লিখতে হয়; আসলে কাজ একই।
উপপাদ্য ৫.২ তাই শুধু একটি সমতা নয়, একটি অনুবাদ-অভিধান: অনুমান ↔ certificate, শাখা ↔ address, সবচেয়ে লম্বা শাখা ↔ certificate-এর দৈর্ঘ্য আর verifier-এর সময়। পরীক্ষায় যেটি সুবিধাজনক, সেটি ব্যবহার করা যায়।
মূল উপলব্ধি: Verifier সংজ্ঞা একটি সমস্যাকে NP-তে বসাতে সুবিধাজনক, NTM সংজ্ঞা NP-কে time আর space-এর বাকি তত্ত্ব ও Cook–Levin প্রমাণের সঙ্গে জুড়তে; ইতিহাসে Edmonds, Cook, Levin আর Karp দুই ধারণাকে প্রায় একসঙ্গে গড়ে তোলেন।
প্র ০৫Input-এর encoding কি একটি সমস্যার NP-তে থাকা না-থাকা বদলে দিতে পারে? SUBSET-SUM-কে unary-তে লিখলে কী হয়?
NP-এর সংজ্ঞা input-এর দৈর্ঘ্য |w| দিয়ে মাপে, তাই encoding গুরুত্বপূর্ণ। পর্ব ০৫-এ “যুক্তিসংগত” encoding-এর কথা ছিল: graph-এর জন্য adjacency list বা matrix, যা পরস্পরের polynomial দূরত্বে; আর সংখ্যার জন্য binary (বা যেকোনো ভিত্তি ≥ ২)। এসবের মধ্যে বদলালে polynomial সময় polynomial-ই থাকে, তাই NP-এর সদস্যপদ বদলায় না।
Unary encoding ব্যতিক্রম। 5 লেখা হয় 11111, তাই একটি সংখ্যা t-এর দৈর্ঘ্য t নিজেই, binary-তে যা প্রায় log2 t. SUBSET-SUM-এর সংখ্যাগুলো unary-তে দিলে input সূচকীয়ভাবে বড় হয়ে যায়, আর তখন O(m · t) সময়ের DP এই বড় input-এর polynomial. তাই unary SUBSET-SUM P-তে। সমস্যাটি বদলায়নি; শুধু input-এর মাপকাঠি বদলেছে, ফলে একই algorithm এখন “দ্রুত” গোনা হচ্ছে। এই কারণে binary SUBSET-SUM-কে বলা হয় দুর্বলভাবে (weakly) NP-complete: সংখ্যাগুলো ছোট হলে এটি সহজ। অন্যদিকে 3-PARTITION বা bin packing-এর মতো কিছু সমস্যা unary-তেও NP-complete থাকে বলে পরিচিত; এদের বলে strongly NP-complete (পর্ব ৬১)।
একটি সূক্ষ্ম কথা: NP-তে থাকা encoding বদলেও সাধারণত টিকে থাকে, কারণ verifier-এর জন্য বড় input মানে বেশি সময় পাওয়া, কম নয়। Binary-তে NP-তে থাকলে unary-তেও NP-তে, কারণ unary থেকে binary-তে রূপান্তর polynomial সময়ে হয়। উল্টো দিক সবসময় সত্য নয়: unary-তে একটি সমস্যা P-তে, কিন্তু binary-তে সেটি NP-complete হতে পারে, যেমন SUBSET-SUM-এর ক্ষেত্রে।
বাস্তব শিক্ষা: “এই সমস্যার algorithm O(n · W)” শুনলে জিজ্ঞেস করুন, W কী? Knapsack-এর ধারণক্ষমতা যদি কয়েক হাজার কেজি হয়, DP চমৎকার চলে; যদি ৬৪-bit সংখ্যা হয়, DP অচল। বাজারঘরের পার্সেলের ওজন গ্রামে মাপলে t এক হাজার গুণ বড় হয়, আর DP-এর কাজও।
মূল উপলব্ধি: যুক্তিসংগত encoding বদলালে NP বা P বদলায় না, কিন্তু unary encoding input-কে কৃত্রিমভাবে বড় করে pseudo-polynomial algorithm-কে polynomial দেখায়; তাই সংখ্যা সবসময় binary-তে ধরে সময় গুনুন।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। verifiers.py আর verifier_to_ntm.py-তে নিজের instance বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা: বাজারঘরের পাঁচটি অর্ডার A, B, C, D, E-কে তিনটি delivery slot (1, 2, 3)-এ বসাতে হবে; দুটি অর্ডার একই ভ্যানের জন্য “সংঘাতে” থাকলে একই slot পাবে না। সংঘাত: A–B, B–C, C–A, C–D, D–E. প্রশ্নটিকে 3-COLOR-এর instance হিসেবে লিখুন, NP-তে থাকার জন্য certificate আর verifier নকশা করুন, একটি polynomial-সময়ের NTM-এর high-level বর্ণনা দিন, আর certificate A=1, B=2, C=3, D=1, E=2 মেলান।
Instance: vertex A–E, edge পাঁচটি সংঘাত; প্রশ্ন ⟨G⟩ ∈ 3-COLOR? Certificate: প্রতিটি vertex-এর একটি রঙ {1, 2, 3}, দৈর্ঘ্য O(m), যা input-এর polynomial-এ সীমিত। Verifier: (১) প্রতিটি vertex-এর ঠিক একটি রঙ আর তা {1, 2, 3}-এ কি না দেখা; (২) প্রতিটি edge (u, v)-এ রঙ(u) ≠ রঙ(v) কি না দেখা; সব ঠিক হলে গ্রহণ। প্রতিটি edge-এ একটি তুলনা, তাই O(|E|) তুলনা, Turing machine-এ polynomial সময়ে হয়। Completeness: G 3-রঙযোগ্য হলে সেই রঙ-করাই c. Soundness: না হলে যেকোনো রঙ-করায় অন্তত একটি edge-এর দুই প্রান্ত একই রঙ, V সেটি ধরে।
NTM: “প্রতিটি vertex-এর জন্য nondeterministic ভাবে তিনটি রঙের একটি লেখা (তিনটি পছন্দ); তারপর verifier-এর ধাপ চালানো।” প্রতিটি শাখা O(m + |E|)-এর একটি polynomial সময়ে থামে। Certificate 12312 মেলানো: A–B 1≠2, B–C 2≠3, C–A 3≠1, C–D 3≠1, D–E 1≠2; পাঁচটি তুলনাই ঠিক, গ্রহণ। Scratch-এ সব 35 = ২৪৩টি certificate চালিয়ে ২৪টি গৃহীত পাওয়া গেছে (ত্রিভুজ ABC-তে ৬ রকম, D-তে ২, E-তে ২)।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: HAMPATH ∈ NP. প্রমাণ: ⟨G, s, t⟩-এ কোনো Hamiltonian path না থাকলে certificate হিসেবে s দিয়ে শুরু আর t দিয়ে শেষ এমন সব vertex-ক্রমের তালিকা দিন। Verifier তালিকার প্রতিটি ক্রমের জন্য HAMPATH-এর verifier চালায়, যা polynomial সময়ের; সবগুলো বর্জিত হলে গ্রহণ করে। প্রতিটি পরীক্ষা polynomial, তাই verifier polynomial. ∎” ভুলটি কোথায়?
ভুল দুই জায়গায়, দুটিই সংজ্ঞার polynomial সীমায়। প্রথম, certificate-এর দৈর্ঘ্য: m vertex-এ তালিকায় (m − 2)!-টি ক্রম, প্রতিটি m দৈর্ঘ্যের; এটি |w|-এর কোনো polynomial দিয়ে সীমিত নয়, তাই |c| ≤ p(|w|) ভাঙে। দ্বিতীয়, সময়: “প্রতিটি পরীক্ষা polynomial” সত্য, কিন্তু পরীক্ষার সংখ্যা factorial; polynomial সংখ্যক polynomial পরীক্ষাই কেবল polynomial. verifiers.py-তে C থেকে N-এর জন্য ২৪টি ক্রম লেগেছিল; ৬০ জেলায় সংখ্যাটি ৭৯ অঙ্কের।
যুক্তিটি আসলে HAMPATH ∈ EXP প্রমাণ করে (সঠিকভাবে)। HAMPATH ∈ NP কি না, তা অজানা; HAMPATH NP-complete বলে এটি NP-তে থাকলে NP = coNP হতো (পর্ব ৬২)।
-
Trace (আউটপুট অনুমান): Verifier থেকে বানানো NTM-কে SUBSET-SUM-এর instance S = (3, 5, 8, 11, 14), t = 22-এ চালানো হলো; প্রতিটি সংখ্যার জন্য একটি bit অনুমান (0 = বাদ, 1 = নেওয়া), তারপর যোগ মেলানো। গাছে মোট কতটি node আর কতটি পাতা? কতটি পাতা গ্রহণ করে, কোনগুলো, আর shortlex (BFS) ক্রমে প্রথমটি কোনটি? t = 24 হলে উত্তর কী বদলায়?
m = 5, তাই পাতা 25 = ৩২টি আর node 26 − 1 = ৬৩টি, t যা-ই হোক। t = 22-এ তিনটি পাতা গ্রহণ করে: 00101 (8 + 14), 10110 (3 + 8 + 11) আর 11001 (3 + 5 + 14) নামের পাতাগুলো। Shortlex ক্রমে প্রথম 00101. তিনটি certificate, তিনটি ভিন্ন “প্রমাণ”: একটি “হ্যাঁ” উত্তরের অনেক certificate থাকতে পারে, একটিই যথেষ্ট।
t = 24-এ গাছের আকার একই (৬৩ node), কিন্তু গ্রহণকারী পাতা একটিই, 01110 (5 + 8 + 11), যা verifier_to_ntm.py-র তৃতীয় লাইন। সব ৩২টি যোগফল scratch-এ গোনা হয়েছে।
-
হিসাব: একটি language L-এর verifier V দৈর্ঘ্য n-এর input-এ বড়জোর q(n) = n2 ধাপ চলে, আর certificate {0, 1}-এর ওপর দৈর্ঘ্য বড়জোর p(n) = 2n. NP ⊆ EXP-এর brute-force decider D দৈর্ঘ্য n = 10-এর একটি input-এ সবচেয়ে খারাপ ক্ষেত্রে কতগুলো certificate চেষ্টা করে, আর V-এর মোট ধাপের একটি ঊর্ধ্বসীমা কত? n দ্বিগুণ হলে কী হয়?
দৈর্ঘ্য ০ থেকে ২০-এর binary string: 20 + 21 + ⋯ + 220 = 221 − 1 = 2,097,151টি। প্রতিটিতে V বড়জোর 102 = 100 ধাপ, তাই V-এর মোট ধাপ ≤ 209,715,100 (c লেখার খরচ বাদে)। n = 20 হলে certificate 241 − 1, দুই লাখ কোটির বেশি, আর প্রতিটিতে 400 ধাপ। n দ্বিগুণ হলে কাজ প্রায় 220 গুণ বাড়ে: এটিই 2O(p(n))-এর অর্থ। অথচ একটি নির্দিষ্ট certificate মেলাতে লাগে মাত্র n2 ধাপ। সংখ্যাগুলো scratch-এ Python দিয়ে গোনা।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমPolynomial-time verifier V (certificate-এর সীমা p(n)) থেকে L-এর জন্য polynomial সময়ের NTM N বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- input w পড়া আর তার দৈর্ঘ্য n ঠিক করা
- nondeterministic ভাবে দৈর্ঘ্য বড়জোর p(n)-এর একটি string c লেখা
- ⟨w, c⟩-এ deterministic verifier V চালানো
- V গ্রহণ করলে এই শাখা গ্রহণ করে, নইলে বর্জন করে
- কোনো একটি শাখা গ্রহণ করলেই N w গ্রহণ করে
Verifier দিয়ে NP-এর সঠিক সংজ্ঞা কোনটি? (V একটি polynomial-time deterministic verifier, p একটি polynomial)
- w ∈ L ⇔ V w-কে certificate ছাড়াই polynomial সময়ে গ্রহণ করে
- w ∈ L ⇔ |c| ≤ p(|w|) এমন প্রতিটি c-এর জন্য V ⟨w, c⟩ গ্রহণ করে
- w ∈ L ⇔ এমন c আছে, |c| ≤ p(|w|), যার জন্য V ⟨w, c⟩ গ্রহণ করে
- w ∈ L ⇔ যেকোনো দৈর্ঘ্যের কোনো c আছে, যার জন্য V ⟨w, c⟩ গ্রহণ করে
Undirected graph G-এর vertex {1, 2, 3, 4, 5}, edge {1,2}, {1,3}, {2,3}, {3,4}, {4,5}. ⟨G, 3⟩ ∈ CLIQUE-এর জন্য নিচের কোনটি একটি বৈধ certificate?
- {3, 4, 5}
- {1, 2, 3}
- {1, 2, 4}
- {1, 3}
P, NP আর EXP-এর সম্পর্ক নিয়ে কোন বক্তব্যটি প্রমাণিত সত্য?
- P = NP
- NP ⊊ EXP
- P ⊊ NP
- P ⊆ NP ⊆ EXP, আর P ≠ EXP
NP নামের “NP” কথাটির অর্থ কী?
- Nondeterministic polynomial time
- Non-polynomial time
- NP-hard সমস্যার সংক্ষিপ্ত রূপ
- Not provable: যে সমস্যার উত্তর প্রমাণ করা যায় না
একটি NTM N L-কে decide করে আর প্রতিটি শাখা দৈর্ঘ্য n-এর input-এ বড়জোর n3 ধাপে থামে। L-এর জন্য একটি polynomial-time verifier বানাতে certificate হিসেবে কী নেওয়া স্বাভাবিক?
- N-এর পুরো computation tree
- একটি গ্রহণকারী শাখার পছন্দগুলোর ক্রম, দৈর্ঘ্য ≤ n3
- N-এর transition function-এর বর্ণনা ⟨N⟩
- খালি string ε, কারণ V নিজেই সব শাখা দেখবে
HAMPATH-এর complement, অর্থাৎ {⟨G, s, t⟩ : G-এ s থেকে t কোনো Hamiltonian path নেই}, সম্পর্কে কোন বক্তব্যটি সঠিক?
- এটি NP-তে, কারণ সব vertex-ক্রমের তালিকাই একটি certificate
- এটি undecidable
- এটি coNP-তে আর EXP-এ আছে, কিন্তু NP-তে আছে কি না অজানা
- এটি P-তে, কারণ accept আর reject অদলবদল করা যায়
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Verifier V: deterministic decider, input ⟨w, c⟩; L ∈ NP ⇔ polynomial-time V আর polynomial p আছে, যাতে w ∈ L ⇔ ∃c, |c| ≤ p(|w|), V ⟨w, c⟩ গ্রহণ করে।
- দুই দিক সবসময় দেখাতে হয়: “হ্যাঁ” হলে ভালো c আছে (completeness), “না” হলে কোনো c চলে না (soundness বা নির্ভরযোগ্যতা)। ভুল c বর্জিত হলে w ∉ L প্রমাণ হয় না।
- HAMPATH (ক্রম), CLIQUE (k vertex), SUBSET-SUM (bit-vector), COMPOSITES (গুণনীয়ক), SAT (assignment): সবই NP-তে; সংখ্যা binary-তে ধরে সময় গুনুন।
- NP = ⋃k NTIME(nk): NTM certificate অনুমান করে V চালায়; উল্টো দিকে গ্রহণকারী শাখার address-ই certificate.
- P ⊆ NP ⊆ EXP প্রমাণিত, P ≠ EXP প্রমাণিত; P = NP, NP = EXP আর NP = coNP খোলা। NP মানে nondeterministic polynomial.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৬ · Nondeterministic Turing machine আর deterministic simulationফিরে দেখুনGuess and verify, computation tree, address আর সূচকীয় simulation-এর দাম।
- পর্ব ০৫ · সমস্যাকে language হিসেবে দেখা — encoding আর decision problemফিরে দেখুনযুক্তিসংগত encoding আর binary বনাম unary, যা polynomial সময়ের হিসাবে জরুরি।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৫৯ polynomial-time reduction, আর পর্ব ৬০-এ Cook–Levin.
- DSA · পর্ব ৬৪ — P বনাম NPপাশের ট্র্যাকAlgorithm-এর দিক থেকে NP-complete সমস্যা আর reduction.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৬০ — Euler আর Hamilton pathপাশের ট্র্যাকHamilton path-এর গ্রাফ-তত্ত্ব, Königsberg থেকে NP-কঠিনতা।