এই পর্বে যা শিখবেন
- P বনাম NP প্রশ্নের নিখুঁত রূপ, আর P = NP ⇔ SAT ∈ P-এর প্রমাণ
- P = NP হলে আর P ≠ NP হলে কী কী প্রমাণযোগ্যভাবে ঘটে, আর কোন দাবি অতিরঞ্জন
- Relativization-এর Baker–Gill–Solovay উপপাদ্য, প্রমাণের রূপরেখাসহ, আর natural proofs ও algebrization-এর মূল ভাবনা
- Ladner-এর উপপাদ্য, NP-intermediate প্রার্থী factoring আর graph isomorphism
- ETH, SETH, NP-complete সমস্যা নিয়ে বাস্তবে কাজের পথ, আর ভুল “প্রমাণ” চেনার উপায়
১ · প্রশ্নটি নিখুঁতভাবে — P = NP?
বাজারঘরের delivery বিভাগে প্রতিদিন সকালে একই ধরনের প্রশ্ন আসে। আজকের ৪০টি ঠিকানা ঘুরে মোট ৩০০ কিলোমিটারের মধ্যে ফেরা যায় কি? ৬০টি পার্সেল থেকে ঠিক ৫০০ কেজি বেছে ট্রাক ভরা যায় কি? সংঘাতে থাকা অর্ডারগুলোকে তিনটি delivery slot-এ ভাগ করা যায় কি? প্রতিটির উত্তর কেউ লিখে দিলে মেলানো সহজ; নিজে খুঁজতে গেলে সম্ভাবনার সংখ্যা বিস্ফোরিত হয়। এই মডিউলের আগের পর্বগুলো এই অনুভূতিকে নিখুঁত গণিতে রূপ দিয়েছে। এই পর্বে আসল প্রশ্নটি: এই ফারাক কি অনিবার্য?
পরীক্ষার খাতা দেখা আর পরীক্ষা দেওয়ার কথা ভাবুন। একজন পরীক্ষক ঘণ্টায় অনেক খাতা মেলাতে পারেন, কারণ উত্তর বসিয়ে দেখা যান্ত্রিক কাজ। কিন্তু সেই একই উত্তর নিজে বের করতে ছাত্রের অনেক সময় লাগে। P বনাম NP প্রশ্নটি জিজ্ঞেস করে: এমন কোনো সাধারণ কৌশল কি আছে, যাতে “মেলাতে সহজ” প্রতিটি প্রশ্নের উত্তর “বের করাও সহজ” হয়ে যায়? প্রায় সবার মনে হয় নেই। কিন্তু “মনে হওয়া” আর প্রমাণ এক জিনিস নয়।
সংজ্ঞাগুলো আগের পর্বের। পর্ব ৫৭-এ P = ⋃k TIME(nk): একটি deterministic single-tape Turing machine যেসব language O(nk) সময়ে decide করে। পর্ব ৫৮-এ NP = ⋃k NTIME(nk), আর সমতুল্যভাবে, যাদের polynomial-time verifier আছে: w ∈ L ⇔ ∃c, |c| ≤ p(|w|), V ⟨w, c⟩ গ্রহণ করে। এখানে c হলো certificate.
P = NP কি?
যেহেতু P ⊆ NP প্রমাণিত (পর্ব ৫৮), প্রশ্নটির সমতুল্য রূপ: NP-এর প্রতিটি language কি একটি polynomial সময়ের deterministic decider দিয়ে decide করা যায়? P বনাম NP প্রশ্নটি Stephen Cook ১৯৭১ সালে এই আকারে লেখেন; Clay Mathematics Institute ২০০০ সালে একে তাদের সাতটি Millennium Prize সমস্যার একটি হিসেবে তালিকাভুক্ত করে।
প্রশ্নটির সবচেয়ে কাজের রূপ আসে NP-complete সমস্যা থেকে। Polynomial-time reduction A ≤p B মানে polynomial সময়ে হিসাবযোগ্য একটি f, যাতে w ∈ A ⇔ f(w) ∈ B (পর্ব ৫৯); দিকের নিয়ম: “A ≤p B আর B ∈ P হলে A ∈ P; A NP-hard হলে B-ও NP-hard”. Cook–Levin theorem বলে, SAT NP-complete; এর পূর্ণ tableau প্রমাণ পর্ব ৬০-এ।
B যেকোনো একটি NP-complete language হলে, P = NP ⇔ B ∈ P. বিশেষত, P = NP ⇔ SAT ∈ P.
প্রমাণ:
- (⇒) ধরুন P = NP. B NP-complete, তাই B ∈ NP = P. — NP-complete-এর সংজ্ঞা: B ∈ NP
- (⇐) ধরুন B ∈ P, আর MB তাকে na সময়ে decide করে। যেকোনো L ∈ NP নিন। B NP-hard বলে একটি f আছে, L ≤p B, যা nb সময়ে চলে। — NP-hard-এর সংজ্ঞা
- L-এর decider: “w-এ f(w) হিসাব করা, তারপর f(w)-এ MB চালানো, তার উত্তরই উত্তর।” |f(w)| ≤ nb, কারণ f nb ধাপে এর বেশি লিখতে পারে না; তাই মোট সময় O(nb + (nb)a) = O(nab), একটি polynomial. — polynomial-এর composition polynomial
- সঠিকতা: w ∈ L ⇔ f(w) ∈ B ⇔ MB গ্রহণ করে। তাই L ∈ P. L যেকোনো ছিল, তাই NP ⊆ P, আর P ⊆ NP মিলিয়ে P = NP. ∎
অর্থাৎ হাজার হাজার NP-complete সমস্যা (SAT, 3SAT, CLIQUE, HAMPATH, SUBSET-SUM, 3-COLOR, TSP-এর decision রূপ) একই নৌকায়: একটিও P-তে পড়লে সবাই P-তে, আর কোনো একটি P-এর বাইরে প্রমাণিত হলে সবাই বাইরে। তাদের কোনোটির polynomial algorithm জানা নেই, আর কোনোটির জন্য polynomial algorithm অসম্ভব, এমন প্রমাণও নেই।
| বক্তব্য | অবস্থা | কোথায় |
|---|---|---|
| P ⊆ NP ⊆ EXP | প্রমাণিত | পর্ব ৫৮ |
| P ≠ EXP (time hierarchy) | প্রমাণিত | পর্ব ৬৭ |
| SAT NP-complete | প্রমাণিত (Cook ১৯৭১, Levin ১৯৭৩) | পর্ব ৬০ |
| P = NP? | খোলা | এই পর্ব |
| NP = coNP? | খোলা (P = NP হলে হ্যাঁ) | পর্ব ৬২ |
| NP = EXP? | খোলা (P = NP হলে না) | পর্ব ৫৮ |
ইতিহাস: প্রশ্নটির আগের রূপ পাওয়া যায় Kurt Gödel-এর ১৯৫৬ সালে John von Neumann-কে লেখা একটি চিঠিতে, যেখানে তিনি জিজ্ঞেস করেন দৈর্ঘ্য n-এর প্রমাণ খুঁজতে একটি যন্ত্রের কত ধাপ লাগে; চিঠিটি বহু বছর পরে পরিচিতি পায়। ১৯৬৫ সালে Jack Edmonds আর Alan Cobham polynomial সময়কে “দক্ষতার” মাপকাঠি হিসেবে প্রস্তাব করেন। Cook ১৯৭১ সালে আর Leonid Levin সোভিয়েত ইউনিয়নে স্বাধীনভাবে (প্রকাশ ১৯৭৩) NP-completeness-এর ধারণা দেন, আর Richard Karp ১৯৭২ সালে ২১টি সমস্যাকে NP-complete দেখান। তার পর থেকে পঞ্চাশ বছরের বেশি প্রশ্নটি খোলা।
২ · P = NP হলে কী হতো — বাজারঘরের planner থেকে গণিতের প্রমাণ
ধরা যাক, কাল কেউ প্রমাণ করলেন P = NP. প্রথম যে কথাটি স্পষ্ট নয়: NP হলো decision problem-এর শ্রেণি, “হ্যাঁ বা না”। কিন্তু বাজারঘরের planner চায় আসল রুট, শুধু “রুট আছে” নয়। ভালো খবর: NP সমস্যার search রূপ decision রূপের সমান কঠিন, এই কৌশলের নাম self-reducibility (বিস্তারিত পর্ব ৬২-এ)। নিচের stepper একটি ছোট instance-এ দেখায়, শুধু “tour ≤ k কিমি আছে?” প্রশ্নের একটি দ্রুত উত্তরদাতা দিয়ে কীভাবে সেরা রুট বানানো যায়।
Instance: পাঁচটি জেলা, ঢাকা (D), গাজীপুর (G), নারায়ণগঞ্জ (N), কুমিল্লা (C), টাঙ্গাইল (T); প্রতি জোড়ার মধ্যে একটি রাস্তা, দূরত্ব (কাল্পনিক, কিমি): D–G 35, D–N 20, D–C 100, D–T 90, G–N 50, G–C 140, G–T 60, N–C 85, N–T 110, C–T 190. প্রশ্ন: ঢাকা থেকে শুরু করে প্রতিটি জেলায় একবার গিয়ে ঢাকায় ফেরার সবচেয়ে ছোট রুট। দশটি দূরত্বের যোগফল 880, তাই উত্তর 0 থেকে 880-এর মধ্যে।
1k-এর ওপর binary search: ORACLE(k)?2সবচেয়ে ছোট হ্যাঁ = OPT3প্রতিটি রাস্তা e বাদ দিয়ে ORACLE(OPT)?4হ্যাঁ: e মুছে ফেলা; না: e রাখা
| প্রশ্ন | |
| সীমা | |
| প্রশ্ন গোনা |
- প্রথম তিন প্রশ্ন। “440 কিমির মধ্যে tour আছে?” হ্যাঁ। “220?” না। “330?” না। প্রতিটি উত্তর সম্ভাব্য পরিসর অর্ধেক করে; এখন উত্তর 331 থেকে 440-এর মধ্যে।
- আরও চার প্রশ্ন। 385-এ হ্যাঁ, কিন্তু 358, 372 আর 379-এ না। পরিসর এখন মাত্র 380 থেকে 385.
- Binary search শেষ। 382 আর 384-এ না, তাই সেরা দৈর্ঘ্য OPT = 385 কিমি। মোট ৯টি প্রশ্ন, কারণ ৮৮১টি সম্ভাব্য মানের জন্য log2 881 ≈ 9.8. দূরত্ব binary-তে লেখা, তাই প্রশ্নসংখ্যা input-এর দৈর্ঘ্যের রৈখিক।
- রাস্তা মোছা শুরু। একটি একটি রাস্তা নিষিদ্ধ করে জিজ্ঞেস: “তবুও 385-এর মধ্যে tour আছে?” D–G আর D–N ছাড়াও হয়, তাই সেগুলো স্থায়ীভাবে মুছে ফেলা হলো। D–C আর D–T নিষিদ্ধ করলে আর হয় না, তাই রাখা হলো।
- পরের চারটি। G–C মোছা যায়; G–N, G–T আর N–C দরকারি।
- রুট বেরিয়ে এল। N–T আর C–T-ও মুছে যায়। বাকি পাঁচটি রাস্তা ঠিক একটি tour: D → C → N → G → T → D = 100 + 85 + 50 + 60 + 90 = 385. মোট ১৯টি প্রশ্ন: ৯টি binary search আর ১০টি রাস্তার জন্য একটি করে।
সাধারণভাবে m রাস্তা আর দূরত্বের যোগফল W হলে প্রশ্ন লাগে প্রায় log2 W + m, যা input-দৈর্ঘ্যের polynomial. প্রতিটি প্রশ্ন P = NP হলে polynomial সময়ের, কারণ TSP-এর decision রূপ NP-তে। তাই P = NP হলে বাজারঘরের সেরা রুট, সেরা ট্রাক-ভরাট, সেরা slot-ভাগ সবই polynomial সময়ে বের হতো। (Scratch-এ সব ১২টি tour গুনে মেলানো হয়েছে: 385 কিমির tour একটিই, উল্টো দিকে ঘোরা বাদে।)
আরও কয়েকটি পরিণাম প্রমাণযোগ্যভাবে আসে:
- NP = coNP. P complement-এ বদ্ধ: deterministic decider-এর accept আর reject অদলবদল করলেই হয়। তাই L ∈ NP = P ⇒ L̄ ∈ P = NP. অর্থাৎ coNP = NP, আর “এই সূত্র কখনো সত্য হয় না” ধরনের দাবিরও ছোট প্রমাণ থাকত।
- One-way function থাকত না। একটি one-way function f-এর জন্য “y দিলে এমন x খুঁজুন যাতে f(x) = y” একটি NP search সমস্যা (x নিজেই certificate). P = NP হলে self-reduction-এ এটি polynomial সময়ে হতো। তাই আধুনিক public-key cryptography-র তাত্ত্বিক ভিত্তি থাকত না; cybersecurity কোর্সের পর্ব ১০-এ এর ব্যবহার দেখুন।
- গণিতের প্রমাণ খোঁজা। একটি formal proof system-এ “এই উপপাদ্যের দৈর্ঘ্য ≤ n-এর প্রমাণ আছে?” প্রশ্নটি NP-তে, কারণ প্রমাণ নিজেই certificate, আর proof checker polynomial সময়ে মেলায়। P = NP হলে n-এর polynomial সময়ে প্রমাণ খুঁজে পাওয়া যেত। এটিই Gödel-এর চিঠির প্রশ্ন।
- NP ≠ EXP. P ≠ EXP প্রমাণিত, তাই P = NP হলে NP ≠ EXP. polynomial hierarchy-ও P-তে ধসে পড়ত (পর্ব ৬৮)।
সাবধান: “P = NP হলে সব কঠিন সমস্যা কাল থেকেই সহজ” কথাটি অতিরঞ্জন। প্রথমত, polynomial মানেই দ্রুত নয়: n100 সময়ের algorithm তাত্ত্বিকভাবে polynomial, কিন্তু ব্যবহারে অচল। দ্বিতীয়ত, প্রমাণটি non-constructive হতে পারে, অর্থাৎ algorithm আছে দেখাবে কিন্তু হাতে দেবে না। (একটি সূক্ষ্ম কথা: Levin-এর universal search নামে পরিচিত একটি কৌশল দেখায়, P = NP হলে SAT-এর জন্য একটি স্পষ্ট লেখা polynomial algorithm আছে, কিন্তু তার ধ্রুবক অকল্পনীয় বড়।) তৃতীয়ত, cryptography ভাঙতে algorithm-টিকে বাস্তবে দ্রুত হতে হবে।
প্রথম সতর্কতাটি সংখ্যায় দেখা যাক। নিচের ব্লক হিসাব করে, কোন n থেকে 2n স্থায়ীভাবে nk-কে ছাড়িয়ে যায়, আর প্রতি সেকেন্ডে 109 ধাপে এক দিনে (8.64 × 1013 ধাপ) কত বড় n সামলানো যায়। সব হিসাব পূর্ণসংখ্যায়, কোনো ভাসমান-বিন্দুর গোলমাল নেই।
# "Polynomial" is not automatically "fast": exact integer arithmetic only
def crossover(k): # smallest n >= 2 after which 2^n > n^k (next 50 checked)
n = 2
while not all(2 ** m > m ** k for m in range(n, n + 50)):
n += 1
return n
for k in (2, 3, 10, 100):
print(f"2^n beats n^{k:<3} from n = {crossover(k)}")
budget = 10 ** 9 * 86400 # one day at 10^9 steps per second
def largest(cost): # largest n with cost(n) <= budget
n = 1
while cost(n + 1) <= budget: n += 1
return n
rows = [("n^2", lambda n: n ** 2), ("n^3", lambda n: n ** 3),
("n^10", lambda n: n ** 10), ("n^100", lambda n: n ** 100),
("1.3^n", lambda n: 13 ** n // 10 ** n), ("2^n", lambda n: 2 ** n)]
print("budget: 8.64e13 steps (one day)")
for name, cost in rows:
print(f" {name:6} largest n = {largest(cost)}")
twice = [(name, largest(lambda n, c=cost: c(n) // 2))
for name, cost in (rows[1], rows[2], rows[5])]
print("doubling the machine speed:", twice)আসল আউটপুট (ব্রাউজারের Python):
2^n beats n^2 from n = 5
2^n beats n^3 from n = 10
2^n beats n^10 from n = 59
2^n beats n^100 from n = 997
budget: 8.64e13 steps (one day)
n^2 largest n = 9295160
n^3 largest n = 44208
n^10 largest n = 24
n^100 largest n = 1
1.3^n largest n = 122
2^n largest n = 46
doubling the machine speed: [('n^3', 55699), ('n^10', 26), ('2^n', 47)]
n100-এর algorithm n = 997-এর আগে 2n-এর brute force-এর চেয়েও খারাপ, আর এক দিনে n = 1-এর বেশি সামলাতে পারে না। অন্যদিকে n3 চুয়াল্লিশ হাজারের বেশি সামলায়। লক্ষ করুন সূচকীয় সময়ের এক নিষ্ঠুর বৈশিষ্ট্য: যন্ত্র দ্বিগুণ দ্রুত হলে n3-এ n প্রায় ২৬% বাড়ে (44208 → 55699), কিন্তু 2n-এ n বাড়ে মাত্র ১ (46 → 47). আর 1.3n-এর মতো “ভালো সূচকীয়” algorithm (3SAT-এর জানা সেরা algorithm-গুলো মোটামুটি এই মাপের) 2n-এর তুলনায় প্রায় তিনগুণ বড় n সামলায়। তাই P বনাম NP তাত্ত্বিক সীমানার প্রশ্ন; বাস্তবের গতির প্রশ্ন আরও সূক্ষ্ম।
৩ · P ≠ NP হলে কী হতো — আর কী হতো না
অন্য জগৎটি ভাবুন: কেউ প্রমাণ করলেন P ≠ NP. তাহলে প্রমাণযোগ্যভাবে কোনো NP-complete সমস্যা P-তে নেই (উপপাদ্য ১.২)। বাজারঘরের planner জানবে, সবচেয়ে খারাপ ক্ষেত্রে সব instance দ্রুত সমাধান করার কোনো algorithm কখনো পাওয়া যাবে না, তাই গবেষণার শক্তি অন্য দিকে দেওয়া যাবে। আর Ladner-এর উপপাদ্যে (অংশ ৬) NP-এর ভেতরে একটি তৃতীয় অঞ্চল থাকবে।
কিন্তু P ≠ NP অনেক কিছু দেবে না, আর এখানেই অনেক জনপ্রিয় লেখা ভুল করে:
- Cryptography-র নিরাপত্তা আসবে না। P ≠ NP একটি worst-case কথা: প্রতিটি দ্রুত algorithm কোনো না কোনো instance-এ ব্যর্থ। Cryptography-র দরকার গড়পড়তা কঠিনতা: random key-এর প্রায় সব instance-এ কঠিন। এর জন্য one-way function দরকার, যার অস্তিত্ব P ≠ NP থেকে আসে বলে জানা নেই (পর্ব ৭৬)।
- প্রতিটি instance কঠিন হবে না। বাস্তবের অনেক instance-এ গঠন থাকে, আর SAT solver লাখো চলকের সূত্র প্রায়ই দ্রুত সমাধান করে (অংশ ৭)।
- সূচকীয় সময় প্রমাণ হবে না। P ≠ NP শুধু বলে polynomial অসম্ভব; nlog n-এর মতো quasi-polynomial algorithm তখনও সম্ভব থাকতে পারে। “2Ω(n) লাগবেই” একটি আলাদা, আরও শক্ত অনুমান, যার নাম ETH (অংশ ৭)।
দুই সম্ভাব্য জগৎ — কোনটি আমাদের, তা অজানা
ওপরে: P ≠ NP হলে NP-এর ভেতরের ছবি (Ladner-এর উপপাদ্যসহ)। নিচে: P = NP হলে ছবি।
নিচের JavaScript ব্লকে দুই জগতের পরিণামগুলো পাশাপাশি সাজানো। প্রতিটি সারিতে লেখা আছে সেটি প্রমাণিত পরিণাম, না খোলা থাকে। শেষ লাইনটি গোনে, প্রতিটি জগতে কতগুলো প্রশ্ন খোলা থাকে।
// Consequences in the two possible worlds (proved implications only).
const rows = [
// [question, if P = NP, if P != NP]
["SAT in P?", "yes", "no"],
["every NP-complete in P?", "yes", "no, none of them"],
["NP = coNP?", "yes", "open"],
["NP-intermediate exist?", "no", "yes (Ladner 1975)"],
["one-way functions exist?", "no", "open"],
["factoring in P?", "yes", "open"],
["NP = EXP?", "no", "open"],
["search as easy as decision?", "yes (NP search)", "yes (self-reduction)"],
];
const pad = (s, n) => s.padEnd(n);
console.log(pad("question", 29) + pad("P = NP", 18) + "P != NP");
for (const [q, a, b] of rows) console.log(pad(q, 29) + pad(a, 18) + b);
const openLeft = rows.filter(r => r[1] === "open").length;
const openRight = rows.filter(r => r[2] === "open").length;
console.log(`open in the P = NP world: ${openLeft}, open in the P != NP world: ${openRight}`);আসল আউটপুট (ব্রাউজারের JavaScript):
question P = NP P != NP
SAT in P? yes no
every NP-complete in P? yes no, none of them
NP = coNP? yes open
NP-intermediate exist? no yes (Ladner 1975)
one-way functions exist? no open
factoring in P? yes open
NP = EXP? no open
search as easy as decision? yes (NP search) yes (self-reduction)
open in the P = NP world: 0, open in the P != NP world: 4
শেষ লাইনটি এই সারণির সবচেয়ে বড় শিক্ষা: P = NP জগৎ “ঘোলা নয়”, সেখানে এই প্রশ্নগুলোর সবই মীমাংসিত। কিন্তু P ≠ NP প্রমাণ হলেও চারটি বড় প্রশ্ন খোলা থাকত, যার মধ্যে one-way function আর factoring cryptography-র জন্য সবচেয়ে জরুরি। Russell Impagliazzo ১৯৯৫ সালের একটি পরিচিত প্রবন্ধে এই সম্ভাবনাগুলোকে পাঁচটি কাল্পনিক “জগৎ” হিসেবে সাজান, যেখানে P = NP-এর জগৎটির নাম Algorithmica আর পূর্ণ public-key cryptography সম্ভব এমন জগৎটির নাম Cryptomania.
৪ · কেন এত কঠিন ১ — relativization আর Baker–Gill–Solovay
এই কোর্সে দুটি বড় অসম্ভবতার ফল এসেছে একই অস্ত্রে: diagonalization. পর্ব ৫১-এ ATM-এর undecidability, আর পর্ব ৬৭-এ time hierarchy theorem (P ≠ EXP). স্বাভাবিক প্রশ্ন: একই কৌশলে P ≠ NP প্রমাণ করা যায় না কেন? ১৯৭৫ সালে Theodore Baker, John Gill আর Robert Solovay এর একটি সুন্দর উত্তর দেন।
প্রথমে একটি যন্ত্র: oracle Turing machine MA চলার মাঝে যেকোনো string y নিয়ে এক ধাপে জেনে নিতে পারে y ∈ A কি না (পর্ব ৫২-এ Turing reduction-এর পেছনে এই ধারণা ছিল)। PA = polynomial সময়ের deterministic oracle যন্ত্রে decide করা language, NPA = polynomial সময়ের nondeterministic oracle যন্ত্রে। একটি প্রমাণ-কৌশল relativize করে, যদি প্রতিটি যন্ত্রকে একই oracle A দিলেও প্রমাণটি হুবহু চলে। Diagonalization ঠিক এমন: এর দুটি উপাদান, একটি যন্ত্র আরেকটিকে simulate করা আর উত্তর উল্টে দেওয়া; simulate-কারী যন্ত্রের কাছেও একই oracle থাকলে দুটিই অপরিবর্তিত থাকে। তাই প্রতিটি A-এর জন্য PA ≠ EXPA.
(ক) এমন oracle A আছে, যাতে PA = NPA. (খ) এমন oracle B আছে, যাতে PB ≠ NPB.
পরিণাম: যে কৌশল relativize করে, তা দিয়ে P = NP বা P ≠ NP কোনোটিই প্রমাণ করা যায় না। P ≠ NP-এর একটি relativizing প্রমাণ PA ≠ NPA-ও প্রমাণ করত, যা (ক)-এর সঙ্গে সাংঘর্ষিক; P = NP-এর একটি relativizing প্রমাণ (খ)-এর সঙ্গে।
প্রমাণের রূপরেখা (ক): A = TQBF নিন, quantified Boolean সূত্রের সত্যতার language, যা PSPACE-complete (পর্ব ৬৫)। তাহলে NPA ⊆ NPSPACE = PSPACE, কারণ polynomial space-এ প্রতিটি oracle প্রশ্নের উত্তর নিজেই হিসাব করা যায়, আর Savitch-এর উপপাদ্যে NPSPACE = PSPACE (পর্ব ৬৪)। আবার PSPACE ⊆ PA, কারণ যেকোনো PSPACE language-কে TQBF-এ reduce করে একটিমাত্র oracle প্রশ্নে উত্তর মেলে। তাই NPA ⊆ PSPACE ⊆ PA ⊆ NPA, সবগুলো সমান। ∎
প্রমাণের রূপরেখা (খ): যেকোনো B-এর জন্য UB = {1n : B-তে দৈর্ঘ্য n-এর অন্তত একটি string আছে}. UB ∈ NPB সবসময়: NTM দৈর্ঘ্য n-এর একটি y অনুমান করে oracle-কে একবার জিজ্ঞেস করে। এবার B এমনভাবে বানানো হয় যাতে UB ∉ PB: polynomial সময়ের সব oracle যন্ত্র M1, M2, … একে একে নিয়ে, Mi-এর জন্য এমন বড় n বাছাই করা হয় যেখানে Mi-এর সময়সীমা ni < 2n. Mi-কে 1n-এ চালানো হয়, আর প্রতিটি প্রশ্নের উত্তর দেওয়া হয় “না”। Mi বড়জোর niটি string জিজ্ঞেস করে, তাই দৈর্ঘ্য n-এর কোনো string জিজ্ঞেস হয়নি। Mi “হ্যাঁ” বললে দৈর্ঘ্য n-এ B ফাঁকা রাখা হয়; “না” বললে একটি অজিজ্ঞাসিত string B-তে ঢোকানো হয়। দুই ক্ষেত্রেই Mi ভুল, আর তার দেখা প্রতিটি উত্তর সত্যই থাকে। এটিও একটি diagonalization, শুধু oracle-কে নিয়ে। ∎
1কৌশলটি relativize করে?2oracle A: P^A = NP^A3oracle B: P^B ≠ NP^B4relativizing প্রমাণ দুই দিকেই ব্যর্থ5নতুন কৌশল দরকার
| বিষয় | |
| মূল কথা |
- Oracle যন্ত্র। MA যেকোনো y-এর জন্য “y ∈ A?” এক ধাপে জানে। এই নতুন যন্ত্রে PA আর NPA সংজ্ঞায়িত, পুরোনো সংজ্ঞার মতোই।
- Diagonalization relativize করে। পর্ব ৫১-এর D আর time hierarchy-র প্রমাণ শুধু “অন্য যন্ত্র simulate করা, উত্তর উল্টানো” ব্যবহার করে; সবার কাছে একই oracle থাকলে প্রমাণ হুবহু চলে। তাই PA ≠ EXPA প্রতিটি A-তে।
- Oracle A = TQBF. এত শক্তিশালী oracle যে polynomial সময়ের deterministic যন্ত্রও PSPACE-এর সব কিছু পারে। এই জগতে nondeterminism কোনো বাড়তি সুবিধা দেয় না: PA = NPA.
- Oracle B, NP-এর দিক। UB-এ “হ্যাঁ”-এর certificate হলো B-এর দৈর্ঘ্য n-এর একটি string; NTM সেটি অনুমান করে একবার জিজ্ঞেস করে।
- Oracle B, P-এর দিক। Deterministic যন্ত্র niটির বেশি প্রশ্ন করতে পারে না, অথচ দৈর্ঘ্য n-এর string 2nটি। প্রতিপক্ষ সব প্রশ্নে “না” বলে, শেষে যন্ত্রের উত্তরের উল্টোটি সত্য বানায়। নিচের Python ব্লক এটি সত্যি চালায়।
- সিদ্ধান্ত। একটি কৌশল যদি দুই জগতেই একই রকম চলে, তা P বনাম NP মীমাংসা করতে পারে না, কারণ দুই জগতে উত্তর আলাদা। তাই যেকোনো সফল প্রমাণকে এমন কিছু ব্যবহার করতে হবে, যা oracle থাকলে ভেঙে যায়।
প্রতিপক্ষ (adversary) যুক্তিটি একটি দৈর্ঘ্য n-এ সত্যি চালানো যাক। তিনটি deterministic “কৌশল” আছে: অভিধানের ক্রমে প্রশ্ন, এলোমেলো ক্রমে প্রশ্ন (seed স্থির), আর কোনো প্রশ্ন না করেই “হ্যাঁ” বলা। প্রতিটির প্রশ্নের সীমা n2, একটি polynomial.
# Baker-Gill-Solovay oracle B at one length n:
# U_B = {1^n : B has a string of length n}
import random
from itertools import product
random.seed(63)
def strings(n): return ["".join(p) for p in product("01", repeat=n)]
def scan_lex(n, ask, budget): # deterministic: query in order
return any(ask(y) for y in strings(n)[:budget])
def scan_random(n, ask, budget): # "clever": random order (seed fixed)
return any(ask(y) for y in random.sample(strings(n), min(budget, 2 ** n)))
def say_yes(n, ask, budget): # gives up and guesses "yes"
return True
def adversary(algo, n):
budget, asked = n ** 2, set() # a polynomial number of queries
def ask(y): # every answer so far: "y is not in B"
asked.add(y)
return False
verdict = algo(n, ask, budget)
free = [y for y in strings(n) if y not in asked]
B = set() if verdict or not free else {free[0]} # contradict the verdict
return verdict, bool(B), len(asked), B
print(" n 2^n n^2 algorithm says truth queries B at length n")
for n in (4, 5, 8):
for algo in (scan_lex, scan_random, say_yes):
v, t, q, B = adversary(algo, n)
mark = "ok" if v == t else "FOOLED"
print(f"{n:2} {2**n:4} {n*n:4} {algo.__name__:12} {v!s:5} {t!s:5}"
f" {q:7} {sorted(B)} {mark}")
print("NTM with oracle: guess y of length n, ask once -> 1 query per branch")আসল আউটপুট (ব্রাউজারের Python):
n 2^n n^2 algorithm says truth queries B at length n
4 16 16 scan_lex False False 16 [] ok
4 16 16 scan_random False False 16 [] ok
4 16 16 say_yes True False 0 [] FOOLED
5 32 25 scan_lex False True 25 ['11001'] FOOLED
5 32 25 scan_random False True 25 ['00010'] FOOLED
5 32 25 say_yes True False 0 [] FOOLED
8 256 64 scan_lex False True 64 ['01000000'] FOOLED
8 256 64 scan_random False True 64 ['00000000'] FOOLED
8 256 64 say_yes True False 0 [] FOOLED
NTM with oracle: guess y of length n, ask once -> 1 query per branch
n = 4-এ 24 = 16 = 42, তাই প্রশ্ন করা কৌশল দুটি সব string দেখে ফেলে, আর প্রতিপক্ষ কিছুই লুকাতে পারে না: উত্তর ঠিক। কিন্তু n = 5 থেকে 2n > n2, আর প্রতিটি কৌশল ঠকে: সব প্রশ্নে “না” শুনে কৌশল “না” বলে, তখন প্রতিপক্ষ একটি অজিজ্ঞাসিত string (যেমন 11001) B-তে রাখে। 2n আর n2-এর ফারাক যত বাড়ে, লুকানোর জায়গাও তত বাড়ে। অথচ oracle-সহ NTM-এর প্রতিটি শাখা একটিমাত্র প্রশ্ন করে। পূর্ণ প্রমাণে সব polynomial যন্ত্রের বিরুদ্ধে আলাদা আলাদা দৈর্ঘ্যে এই খেলা চালানো হয়।
Relativization বাধার মানে এই নয় যে diagonalization অকেজো; মানে, একে এমন কোনো উপাদানের সঙ্গে মেলাতে হবে যা oracle-এর সামনে ভেঙে যায়। এমন “non-relativizing” ফল সত্যিই আছে: ১৯৯০ সালের দিকে Lund, Fortnow, Karloff, Nisan আর Shamir-এর কাজে প্রমাণিত IP = PSPACE (পর্ব ৭৪), যার জন্য এমন oracle জানা আছে যেখানে সমতাটি ভাঙে। এর কৌশল arithmetization: Boolean সূত্রকে বহুপদী হিসেবে দেখা।
৫ · কেন এত কঠিন ২ — natural proofs আর algebrization
Relativization-এর পর গবেষকেরা অন্য পথ ধরেন: Boolean circuit-এর lower bound. ধারণাটি সরল: P-এর প্রতিটি language-এর জন্য polynomial আকারের circuit আছে, তাই যদি দেখানো যায় SAT-এর জন্য প্রতিটি circuit-এর আকার superpolynomial, তাহলে P ≠ NP. Circuit একটি স্থির, “স্বচ্ছ” বস্তু, তাই এখানে oracle-এর ঝামেলা নেই। কিছু সাফল্যও এসেছিল: ১৯৮০-এর দশকে দেখানো হয় যে স্থির গভীরতার circuit (AC0) parity হিসাব করতে পারে না (Furst–Saxe–Sipser আর Ajtai), আর Razborov ১৯৮৫ সালে monotone circuit-এ (শুধু AND আর OR) CLIQUE-এর জন্য superpolynomial lower bound দেন। বিস্তারিত পর্ব ৭০-এ।
কিন্তু সাধারণ circuit-এ অগ্রগতি থেমে যায়। ১৯৯৪ সালে Alexander Razborov আর Steven Rudich এর একটি ব্যাখ্যা দেন, যার নাম natural proofs বাধা। তাঁরা লক্ষ করেন, জানা প্রায় সব circuit lower bound প্রমাণ একই ছাঁচে চলে: একটি “সহজে পরীক্ষাযোগ্য” ধর্ম খোঁজা (constructive), যা random function-এর বড় একটি অংশের আছে (large), কিন্তু ছোট circuit-এর কোনো function-এর নেই। তাঁদের উপপাদ্য: যদি যথেষ্ট শক্ত pseudorandom function থাকে, যা cryptography-তে প্রায় সবাই বিশ্বাস করেন, তাহলে এমন “natural” প্রমাণ NP-এর জন্য superpolynomial circuit lower bound দিতে পারে না। কারণ এমন ধর্ম দিয়েই pseudorandom function-কে সত্যিকারের random থেকে আলাদা করা যেত, যা তাদের নিরাপত্তা ভাঙত। একটি বিদ্রূপময় মোচড়: P ≠ NP প্রমাণের পথে বাধা দিচ্ছে এমন একটি অনুমান, যা নিজেই P ≠ NP-এর চেয়ে শক্ত।
তৃতীয় বাধা এসেছে IP = PSPACE-এর মতো non-relativizing কৌশল থেকেই। ২০০৮ সালে Scott Aaronson আর Avi Wigderson দেখান যে arithmetization-ভিত্তিক কৌশলগুলো একটি দুর্বল অর্থে relativize করে: oracle-এর সঙ্গে তার একটি বহুপদী বিস্তারও (low-degree extension) দিলে প্রমাণগুলো টিকে থাকে। আর এমন “বীজগাণিতিক oracle” আছে, যার সামনে P বনাম NP দুই দিকেই যেতে পারে। এই বাধার নাম algebrization.
| বাধা | কোন কৌশল আটকায় | মূল ভাবনা |
|---|---|---|
| Relativization (Baker–Gill–Solovay ১৯৭৫) | Diagonalization, simulation | দুই oracle-জগতে উত্তর আলাদা |
| Natural proofs (Razborov–Rudich ১৯৯৪) | প্রচলিত circuit lower bound | এমন প্রমাণ pseudorandom function ভাঙত |
| Algebrization (Aaronson–Wigderson ২০০৮) | Arithmetization (IP = PSPACE-এর কৌশল) | বীজগাণিতিক oracle-জগতে উত্তর আলাদা |
বাধা মানে অসম্ভবতা নয়। এই তিনটি উপপাদ্য বলে “এই নির্দিষ্ট কৌশলগুলো একা যথেষ্ট নয়”, বলে না যে P বনাম NP প্রমাণ-অযোগ্য। Ryan Williams ২০১১ সালে NEXP-এর জন্য ACC0 নামের একটি circuit শ্রেণিতে lower bound প্রমাণ করেন, এমনভাবে যা তিনটি বাধাই এড়িয়ে যায় বলে ব্যাপকভাবে উল্লেখ করা হয়; ফলটি P বনাম NP থেকে অনেক দূরে, কিন্তু দেখায় যে বাধার ফাঁক দিয়ে নতুন কৌশল সম্ভব।
৬ · Ladner-এর উপপাদ্য — P আর NP-complete-এর মাঝখানে
NP-এর যে সমস্যাই দেখা হয়, তার প্রায় সবই হয় P-তে (PATH, 2SAT, matching), নয় NP-complete (SAT, CLIQUE, HAMPATH). তাহলে কি NP = P ∪ NP-complete? Richard Ladner ১৯৭৫ সালে দেখান: না, যদি P ≠ NP হয়।
যদি P ≠ NP, তাহলে এমন language L ∈ NP আছে, যা P-তে নেই আর NP-complete-ও নয়। এমন language-কে বলে NP-intermediate.
লক্ষ করুন শর্তটি: P = NP হলে NP-intermediate থাকতেই পারে না, কারণ তখন NP-এর সবকিছু P-তে। Ladner-এর প্রমাণ একটি কৃত্রিম language বানায়, SAT-এ “গর্ত খুঁড়ে”। নিচের stepper জনপ্রিয় একটি রূপ (“blowing holes in SAT”) দেখায়।
1তালিকা: M1, M2, … আর f1, f2, …2চালু খণ্ড: L = SAT, যতক্ষণ না Mi ভুল করে3বন্ধ খণ্ড: L = ∅, যতক্ষণ না fi ব্যর্থ হয়4L ∈ NP, L ∉ P, L NP-complete নয়
| খণ্ড | |
| L সেখানে | |
| হারানো হলো |
- প্রস্তুতি। ধরে নিন P ≠ NP. Polynomial সময়ের সব decider M1, M2, … আর polynomial সময়ের সব function f1, f2, …-এর একটি তালিকা নিন (প্রতিটিতে একটি “ঘড়ি” বসিয়ে, যাতে তালিকাটি গণনাযোগ্য হয়)। লক্ষ্য: L-কে input-দৈর্ঘ্যের খণ্ডে খণ্ডে বানানো।
- চালু খণ্ড ১। এই দৈর্ঘ্যগুলোয় L = SAT. খণ্ডটি চলে যতক্ষণ না M1 এমন কোনো দৈর্ঘ্যে ভুল করে, যেখানে L = SAT. ভুল আসবেই: নইলে M1 প্রায় সব জায়গায় SAT decide করত, আর SAT ∈ P হতো।
- বন্ধ খণ্ড ২। এবার L = ∅ (কোনো string নয়)। খণ্ডটি চলে যতক্ষণ না f1 “SAT ≤p L” reduction হিসেবে ব্যর্থ হয়, অর্থাৎ এমন φ পাওয়া যায় যাতে φ ∈ SAT ⇎ f1(φ) ∈ L. এটিও আসবেই: নইলে L-এর প্রায় ফাঁকা অংশ আর ছোট দৈর্ঘ্যের SAT মিলিয়ে SAT-কে polynomial সময়ে decide করা যেত।
- পালা চলতে থাকে। খণ্ড ৩-এ আবার SAT, M2-কে হারানো পর্যন্ত; খণ্ড ৪-এ আবার ∅, f2-কে হারানো পর্যন্ত। প্রতিটি খণ্ড সসীম, কিন্তু কখন শেষ হবে তা আগে জানা নেই।
- ফল। প্রতিটি Mi হেরেছে, তাই L ∉ P. প্রতিটি fi হেরেছে, তাই SAT ≤p L নয়, অর্থাৎ L NP-complete নয়। আর L ∈ NP, কারণ L = SAT ∩ {চালু খণ্ডের দৈর্ঘ্য}; সবচেয়ে সূক্ষ্ম অংশ হলো খণ্ডের সীমানা polynomial সময়ে হিসাব করা, যা “অলস” (lazy) diagonalization দিয়ে করা হয়। পূর্ণ প্রমাণ Arora–Barak-এ।
Ladner-এর L একটি কৃত্রিম language; কোনো স্বাভাবিক সমস্যা NP-intermediate, তা প্রমাণ করা অসম্ভব যতক্ষণ P বনাম NP খোলা (কারণ তা P ≠ NP প্রমাণ করত)। তবে কিছু স্বাভাবিক সমস্যা জোরালো প্রার্থী:
- Factoring. Decision রূপ (“n-এর k-এর চেয়ে ছোট, 1-এর বেশি কোনো গুণনীয়ক আছে?”) NP ∩ coNP-তে (পর্ব ৫৮-এর ভাবনার প্রশ্ন ৩)। এটি NP-complete হলে NP = coNP হতো, যা অসম্ভাব্য মনে করা হয়। আবার সাধারণ কম্পিউটারে polynomial algorithm জানা নেই; জানা সেরা algorithm (general number field sieve) sub-exponential. Peter Shor ১৯৯৪ সালে quantum কম্পিউটারের জন্য polynomial algorithm দেন (পর্ব ৭৫)।
- Graph isomorphism (GI). দুটি graph কি শুধু নামে আলাদা? GI ∈ NP (certificate একটি vertex-মিল)। ১৯৮০-এর দশকের ফলে জানা, GI NP-complete হলে polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ত। László Babai ২০১৫ সালে একটি quasi-polynomial সময়ের algorithm ঘোষণা করেন; ২০১৭ সালের শুরুতে বিশ্লেষণে একটি ভুল ধরা পড়ে, যা Babai কয়েক দিনের মধ্যে সংশোধন করেন বলে জানান। GI P-তে কি না, এখনো অজানা।
৭ · ETH, SETH আর NP-complete সমস্যার সঙ্গে বাস্তবে কাজ
P বনাম NP শুধু “polynomial কি না” জিজ্ঞেস করে। বাস্তবে আমরা আরও সূক্ষ্ম কথা জানতে চাই: 3SAT-এ কি 2n-এর চেয়ে অনেক ভালো করা যায়? Russell Impagliazzo আর Ramamohan Paturi ২০০১ সালে দুটি অনুমান স্পষ্ট করেন:
ETH: এমন ধ্রুবক δ > 0 আছে, যাতে n চলকের 3SAT-এর কোনো algorithm 2δn সময়ের কমে চলে না।
SETH: প্রতিটি ε > 0-এর জন্য এমন k আছে, যাতে k-SAT O(2(1 − ε)n) সময়ে সমাধান করা যায় না।
ETH সত্য হলে P ≠ NP, তাই ETH-ও প্রমাণিত নয়; এটি P ≠ NP-এর চেয়ে শক্ত একটি অনুমান। তবু এটি কাজের: ETH ধরে নিলে অনেক সমস্যার জন্য নির্দিষ্ট lower bound পাওয়া যায়, যেমন বহু graph সমস্যায় 2o(n) সময়ের algorithm নেই। SETH থেকে আসে fine-grained complexity, যেখানে edit distance-এর মতো polynomial সমস্যাতেও “n2-এর চেয়ে উল্লেখযোগ্যভাবে ভালো সম্ভবত নয়” ধরনের ফল আসে (পর্ব ৭২)।
ছোট n-এ brute force কেমন বাড়ে, তা গুনে দেখা যাক। নিচের ব্লক random 3CNF সূত্র বানায়, যেখানে clause-সংখ্যা m ≈ 4.26n; এই অনুপাতের কাছে random সূত্র সবচেয়ে কঠিন বলে পরিচিত। Brute force সব 2n মান চেষ্টা করে আর প্রতিটির জন্য verifier চালায়।
# Brute force vs verify on random 3-CNF at the hard ratio m = 4.26 n
import random
from itertools import product
random.seed(63)
def rand3cnf(n, m):
return [[v if random.random() < 0.5 else -v
for v in random.sample(range(1, n + 1), 3)] for _ in range(m)]
def verify(cnf, a): # a[v] in {0, 1}; count clause checks
checks = 0
for c in cnf:
checks += 1
if not any(a[abs(l)] == (l > 0) for l in c): return False, checks
return True, checks
def brute(cnf, n):
tried = total = 0
for bits in product((0, 1), repeat=n):
tried += 1
ok, ch = verify(cnf, (None,) + bits)
total += ch
if ok: return True, tried, total
return False, tried, total
print(" n m SAT? assignments clause checks checks per verify (max)")
for n in (6, 9, 12, 15):
cnf = rand3cnf(n, round(4.26 * n))
sat, tried, total = brute(cnf, n)
print(f"{n:2} {len(cnf):3} {str(sat):5} {tried:11} {total:14} {len(cnf):6}")আসল আউটপুট (ব্রাউজারের Python):
n m SAT? assignments clause checks checks per verify (max)
6 26 True 5 69 26
9 38 True 91 1018 38
12 51 False 4096 30359 51
15 64 False 32768 258401 64
একটি মান মেলাতে বড়জোর m-টি clause দেখা লাগে (শেষ কলাম, n-এর রৈখিক)। কিন্তু সূত্রটি unsatisfiable হলে brute force-কে সব 2n মান দেখতে হয়: n = 15-এ ৩২,৭৬৮টি মান আর আড়াই লাখের বেশি clause-check. n = 6 আর 9-এ সূত্র satisfiable, তাই আগেই থেমেছে। এটি একটি নির্দিষ্ট বোকা algorithm-এর হিসাব, কোনো lower bound-এর প্রমাণ নয়।
একটি সত্যিকারের SAT solver দিয়ে একই প্রশ্ন। বড় n-এ brute force অচল, কিন্তু আধুনিক CDCL solver অনেক এগিয়ে যায়। uv দিয়ে বানানো একটি ছোট প্রকল্পে python-sat (PySAT, MIT licence; এর ভেতরের MiniSat 2.2 solver-ও MIT licence) দিয়ে random 3CNF সমাধান করা হলো: দুটি অনুপাতে (m = 2n, যা সহজ, আর m = 4.26n), প্রতিটি n-এ ১০টি সূত্র, seed স্থির। Solver-এর “conflict” সংখ্যা (কতবার একটি আংশিক মান-বসানো বাতিল হয়েছে) কাজের একটি মাপ। প্রতিটি পাওয়া model আমাদের verifier দিয়ে মেলানো হয়েছে। PySAT-এ কোনো usage-reporting বা network কোড নেই।
from pysat.solvers import Solver
# random_3cnf and verify: as in brute_vs_verify.py
def run(n, ratio, trials, rng):
confl, sat, ok = [], 0, 0
for _ in range(trials):
cnf = random_3cnf(n, round(ratio * n), rng)
with Solver(name="minisat22", bootstrap_with=cnf) as s:
r = s.solve()
confl.append(s.accum_stats()["conflicts"])
if r:
sat += 1
ok += verify(cnf, s.get_model())
return statistics.median(confl), sat, okসত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev23, Python 3.12.13; পুরো run প্রায় ১১ সেকেন্ড):
~/bazarghar-toc$ uv run python hardness.py
python 3.12.13 | python-sat 1.9.dev23 | solver minisat22
ratio n median conflicts SAT/10 models verified
2.0 50 0 10 10
2.0 100 1 10 10
2.0 150 0 10 10
2.0 200 0 10 10
2.0 250 0 10 10
4.26 50 62 4 4
4.26 100 350 5 5
4.26 150 2412 5 5
4.26 200 22599 2 2
4.26 250 154968 4 4
m = 2n-এ ২৫০টি চলকেও solver প্রায় কোনো conflict ছাড়াই উত্তর পায়: brute force-এর 2250-এর তুলনায় এটি কিছুই না। কিন্তু m = 4.26n-এ প্রতি ৫০টি চলক বাড়লে median conflict প্রায় ৬ থেকে ৯ গুণ বাড়ে (62 → 350 → 2412 → 22599 → 154968), অর্থাৎ বৃদ্ধি সূচকীয়ের মতো দেখায়। প্রতিটি পাওয়া model আমাদের verifier-এ পাস করেছে (SAT আর verified কলাম সমান)। দুটি সতর্কতা: এটি একটি পরীক্ষা, প্রমাণ নয়; আর বাস্তবের শিল্প-instance-এ সাধারণত গঠন থাকে, যা random সূত্রে নেই, তাই solver সেখানে প্রায়ই অনেক ভালো করে।
তাহলে একটি সমস্যা NP-complete জানলে বাস্তবে কী করবেন? এই কোর্স আর DSA কোর্স মিলে চারটি পথ:
ছোট n-এ exact
Dynamic programming বা branch and bound; n = 30–50 পর্যন্ত প্রায়ই যথেষ্ট। ভালো সূচকীয় (1.3n) আর খারাপ সূচকীয় (2n)-এর ফারাক বিশাল।
Solver
সমস্যাকে SAT বা ILP-তে লিখে solver চালানো (পর্ব ৭৩; ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭)। উত্তর সবসময় নিজের verifier-এ মেলান।
Approximation
Approximation algorithm polynomial সময়ে প্রমাণিত মানের উত্তর দেয়, যেমন vertex cover-এ বড়জোর দ্বিগুণ (পর্ব ৭১; DSA কোর্সের পর্ব ৬৬)।
Parameter
সূচকীয় অংশটি একটি ছোট প্যারামিটার k-তে আটকে রাখা: FPT, f(k) · nc (পর্ব ৭২; DSA কোর্সের পর্ব ৬৫)।
৮ · ভুল “P = NP” বা “P ≠ NP” প্রমাণ চেনার উপায়
প্রতি বছর অনেক মানুষ P বনাম NP মীমাংসার দাবি করেন। Gerhard Woeginger বহু বছর এমন দাবির একটি তালিকা রেখেছিলেন, যাতে শতাধিক প্রবন্ধ জমেছিল, প্রায় সমান ভাগে P = NP আর P ≠ NP-এর পক্ষে; জানা মতে কোনোটিই বিশেষজ্ঞদের যাচাইয়ে টেকেনি। ২০১০ সালে Vinay Deolalikar-এর একটি P ≠ NP দাবি ব্যাপক আলোচনায় আসে, আর কয়েক সপ্তাহের মধ্যে বিশেষজ্ঞেরা মৌলিক ফাঁক চিহ্নিত করেন। দাবিদারদের প্রতি সম্মান রেখেও, কয়েকটি প্রশ্ন প্রায় সব ভুল ধরে ফেলে:
- সবচেয়ে খারাপ ক্ষেত্রে polynomial, প্রমাণসহ? “১০,০০০টি random instance-এ দ্রুত চলেছে” কোনো প্রমাণ নয়; ওপরের run দেখায়, m = 2n-এর random সূত্র যেকোনো solver-এর কাছে সহজ।
- সময় input-দৈর্ঘ্যে মাপা হয়েছে? SUBSET-SUM-এর O(m · t) DP pseudo-polynomial, কারণ t-এর মান তার bit-দৈর্ঘ্যের সূচকীয় (পর্ব ৫৭)।
- Reduction-এর দিক ঠিক? “একটি P-এর সমস্যাকে SAT-এ reduce করলাম” কিছুই প্রমাণ করে না; SAT-কে P-এর কোনো সমস্যায় reduce করতে হবে।
- বিশেষ ক্ষেত্র নয় তো? 2SAT, 2-COLOR বা tree-তে vertex cover P-তে; এগুলো সমাধান করে P = NP দাবি করা যায় না।
- যুক্তি relativize করে? P ≠ NP-এর একটি প্রমাণ যদি শুধু simulation আর diagonalization ব্যবহার করে, Baker–Gill–Solovay বলে সেটি ভুল হতেই হবে।
- বড় LP দিয়ে TSP? TSP-কে polynomial আকারের linear program হিসেবে লেখার চেষ্টা একটি পুরোনো ধারা। Mihalis Yannakakis ১৯৮৮ সালে symmetric এমন LP-এর জন্য, আর Fiorini ও সহকর্মীরা ২০১২ সালে সাধারণ ক্ষেত্রে দেখান যে TSP polytope-এর এমন বর্ণনার আকার সূচকীয় হতে বাধ্য।
আরও গভীরে: P বনাম NP কি ZFC set theory-তে প্রমাণ-অযোগ্য হতে পারে? এটি একটি খোলা সম্ভাবনা, আর কিছু দুর্বল formal system-এ এমন স্বাধীনতার ফল জানা আছে; তবে বেশিরভাগ বিশেষজ্ঞ মনে করেন না যে এটিই উত্তর। নতুন পথের মধ্যে আছে Ketan Mulmuley আর Milind Sohoni-র geometric complexity theory, যা algebraic geometry আর representation theory দিয়ে permanent বনাম determinant-এর মতো বীজগাণিতিক রূপ আক্রমণ করে, আর Williams-ধাঁচের “algorithm থেকে lower bound” কৌশল। আরেকটি গভীর দিক proof complexity: NP ≠ coNP হলে tautology-র জন্য কোনো proof system-এ সবসময় ছোট প্রমাণ থাকে না, আর resolution-এর মতো নির্দিষ্ট proof system-এ এমন সূচকীয় lower bound সত্যিই প্রমাণিত।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- P বনাম NP প্রশ্নটি লিখুন। P ⊆ NP প্রমাণিত; P = NP কি না খোলা। সমতুল্যভাবে: SAT ∈ P?
- প্রমাণ করুন: একটি NP-complete সমস্যা P-তে হলে P = NP. L ≤p B আর B-এর decider জুড়ে দিন; polynomial-এর composition polynomial.
- P = NP হলে কী হতো? NP = coNP, NP search polynomial সময়ে (self-reduction), one-way function থাকত না; কিন্তু “polynomial” মানেই দ্রুত নয়।
- Relativization কী বলে? PA = NPA আর PB ≠ NPB দুটিই সম্ভব, তাই শুধু diagonalization-এর মতো relativizing কৌশলে মীমাংসা হবে না।
- NP-intermediate কী? NP-তে, কিন্তু P-তেও নয়, NP-complete-ও নয়; P ≠ NP হলে আছে (Ladner). প্রার্থী: factoring, GI.
৯ · AI-এর যুগে P বনাম NP
“P বনাম NP” এমন একটি বিষয়, যেখানে AI assistant-এর আত্মবিশ্বাস আর নির্ভুলতার ফারাক সবচেয়ে বড় হতে পারে। কয়েকটি ভুল বারবার দেখা যায়: একটি heuristic-কে “NP-complete সমস্যার polynomial algorithm” বলা, “P ≠ NP হলে RSA নিরাপদ” বলা, Baker–Gill–Solovay-কে “P বনাম NP প্রমাণ-অযোগ্য” হিসেবে বর্ণনা করা, reduction-এর দিক উল্টে ফেলা, আর বানানো প্রবন্ধ বা সাল উল্লেখ করা। কখনো কখনো AI একটি সাম্প্রতিক “প্রমাণের” খবরও বানিয়ে ফেলে। নিয়মটি সরল: P বনাম NP নিয়ে যেকোনো “মীমাংসা হয়েছে” দাবি ভুল ধরে নিয়ে শুরু করুন, যতক্ষণ না বিশ্বস্ত উৎসে নিজে নিশ্চিত হন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “এই algorithm TSP-কে polynomial সময়ে সমাধান করে” (আসলে heuristic) | সবচেয়ে খারাপ ক্ষেত্রের সময় আর সঠিকতার প্রমাণ চান; ছোট instance-এ brute force-এর সঙ্গে মেলান |
| “P ≠ NP হলে cryptography নিরাপদ” | Worst-case বনাম average-case; one-way function-এর অস্তিত্ব আলাদা প্রশ্ন |
| “Relativization দেখায় P বনাম NP প্রমাণ করা যায় না” | শুধু relativizing কৌশল বাদ পড়ে; IP = PSPACE non-relativizing |
| “X-কে SAT-এ reduce করেছি, তাই X NP-hard” | দিক উল্টো: SAT ≤p X লাগবে |
| “Factoring NP-complete” | জানা নেই, আর হলে NP = coNP হতো; এটি NP-intermediate প্রার্থী |
| বানানো সাল, প্রবন্ধ বা “সম্প্রতি প্রমাণিত” | Sipser, Arora–Barak বা লেখকের নিজের প্রকাশনায় নিজে খুঁজুন |
AI-কে কাজে লাগানোর ভালো উপায়: প্রমাণিত আর খোলা আলাদা করে লিখতে বলা, প্রতিটি দাবির শর্ত চাওয়া, আর কোনো algorithm দাবি করলে ছোট instance-এ brute force-এর সঙ্গে মেলানোর code নিজে চালানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১বেশিরভাগ গবেষক কেন P ≠ NP মনে করেন? এই বিশ্বাসের পক্ষে প্রমাণ কতটা শক্ত, আর ইতিহাসে কোথায় বিশেষজ্ঞদের অনুমান ভুল প্রমাণিত হয়েছে?
William Gasarch কয়েক দফা (২০০২, ২০১২ আর ২০১৯ সালে) গবেষকদের মধ্যে জরিপ করেন; প্রতিবার বেশিরভাগ উত্তরদাতা P ≠ NP মনে করেছেন, আর পরের জরিপগুলোতে সেই অনুপাত বেড়েছে বলে জানা যায়। জরিপ অবশ্যই প্রমাণ নয়, কিন্তু বিশ্বাসের কারণগুলো দেখা জরুরি।
প্রথম কারণ পরোক্ষ কিন্তু জোরালো: হাজার হাজার NP-complete সমস্যা আছে, অপারেশনস রিসার্চ, জীববিজ্ঞান, সার্কিট নকশা, সময়সূচি থেকে আসা, আর বহু দশক ধরে বহু মানুষ এদের যেকোনো একটির জন্য polynomial algorithm খুঁজেছেন। একটি পেলেই সবগুলো মিলত (উপপাদ্য ১.২)। এই ব্যর্থতা একটি বিশাল, স্বাধীন “পরীক্ষা”। দ্বিতীয় কারণ দার্শনিক: P = NP হলে সৃজনশীলতা আর যাচাইয়ের ফারাক ঘুচে যেত; একটি সুন্দর প্রমাণ চিনতে পারা আর তা আবিষ্কার করা সমান সহজ হতো, যা মানুষের অভিজ্ঞতার বিরুদ্ধে যায়। Scott Aaronson এই যুক্তি জনপ্রিয় করেছেন। তৃতীয় কারণ গাণিতিক: বিশেষ মডেলে সত্যিই আলাদা প্রমাণিত, যেমন monotone circuit-এ CLIQUE-এর জন্য superpolynomial lower bound (Razborov ১৯৮৫), আর oracle-সহ “বেশিরভাগ” জগতে P ≠ NP (random oracle-এর জন্য Bennett আর Gill ১৯৮১)।
কিন্তু complexity তত্ত্বের ইতিহাসে বিস্ময় কম নয়। ১৯৮৭–৮৮ সালে Immerman আর Szelepcsényi স্বাধীনভাবে প্রমাণ করেন NL = coNL, যা আগে অনেকে অসম্ভাব্য ভেবেছিলেন (পর্ব ৬৬)। ১৯৯০ সালের দিকে IP = PSPACE দেখায় যে interactive proof-এর ক্ষমতা প্রত্যাশার চেয়ে অনেক বেশি। ২০০২ সালে PRIMES ∈ P (Agrawal, Kayal, Saxena), যদিও তার আগে randomized algorithm জানা ছিল বলে এটি অনেকের কাছে প্রত্যাশিত ছিল। Donald Knuth একটি সাক্ষাৎকারে বলেছেন বলে পরিচিত যে P = NP হতে পারে বলে তাঁর মনে হয়, কিন্তু সেই algorithm হয়তো কখনো জানা যাবে না বা ব্যবহারে অচল হবে।
তাই সৎ অবস্থান: “P ≠ NP বলে বেশিরভাগ গবেষক মনে করেন, কিন্তু প্রমাণিত নয়।” পরীক্ষায় বা লেখায় এর চেয়ে বেশি দাবি করা ভুল।
মূল উপলব্ধি: P ≠ NP-এর পক্ষে পরোক্ষ প্রমাণ বিশাল (হাজারো সমস্যায় ব্যর্থতা, বিশেষ মডেলে প্রমাণ), কিন্তু NL = coNL-এর মতো বিস্ময় মনে করিয়ে দেয় যে বিশ্বাস আর প্রমাণ আলাদা।
প্র ০২ধরুন কাল প্রমাণ হলো P = NP, কিন্তু algorithm-টি n1000 সময়ের, বা প্রমাণটি non-constructive. বাস্তবে কী বদলাত, আর কী বদলাত না?
প্রথমে তাত্ত্বিক জগৎ। Complexity তত্ত্বের অনেক কিছু রাতারাতি বদলে যেত: NP = coNP, polynomial hierarchy ধসে P-তে, NP-intermediate বলে কিছু থাকত না, আর P-এর প্রায় প্রতিটি language NP-complete হতো। এসব প্রমাণের ধরনের ওপর নির্ভর করে না; শুধু সমতাটিই যথেষ্ট।
বাস্তব জগৎ অন্য কথা। galactic.py-র হিসাবে n100-এর algorithm এক দিনে n = 1-এর বেশি সামলাতে পারে না; n1000 আরও খারাপ। ইতিহাসে দেখা গেছে, একটি সমস্যার প্রথম polynomial algorithm প্রায়ই বড় সূচকের হয়, আর পরে নামিয়ে আনা যায়। Linear programming-এর জন্য Khachiyan-এর ১৯৭৯ সালের ellipsoid method তাত্ত্বিকভাবে polynomial কিন্তু বাস্তবে ধীর ছিল; Karmarkar ১৯৮৪ সালে interior-point method দেন, যা বাস্তবেও কাজের। PRIMES-এর AKS algorithm-ও শুরুতে বড় সূচকের ছিল, পরে উন্নত হয়। তাই একটি P = NP প্রমাণ সম্ভবত দ্রুত algorithm-এর জন্য তীব্র গবেষণা শুরু করত, কিন্তু সফল হবে, এমন নিশ্চয়তা নেই। Robertson–Seymour graph minor তত্ত্ব একটি সতর্ক উদাহরণ: তা অনেক সমস্যার জন্য polynomial algorithm-এর অস্তিত্ব দেখায়, কিন্তু কিছু ক্ষেত্রে algorithm-টি কী, তা জানা যায় না, আর ধ্রুবকগুলো অকল্পনীয়।
Non-constructive প্রমাণ নিয়ে একটি চমকপ্রদ তথ্য: Levin-এর universal search কৌশল দেখায়, P = NP হলে SAT-এর search রূপের জন্য একটি স্পষ্টভাবে লেখা যায় এমন algorithm আছে, যা polynomial সময়ে চলে। কৌশলটি সব program পালাক্রমে চালায় আর প্রতিটির দেওয়া উত্তর verifier দিয়ে মেলায়। তাই “অস্তিত্ব জানা কিন্তু algorithm অজানা” পরিস্থিতি SAT-এর ক্ষেত্রে পুরোপুরি ঘটে না, যদিও algorithm-টির ধ্রুবক এত বড় যে ব্যবহার অসম্ভব।
Cryptography-র জন্যও একই কথা: n1000-এর algorithm দিয়ে বাস্তবের কোনো key ভাঙা যেত না। তবে আস্থা কমে যেত, আর নতুন ভিত্তি খুঁজতে হতো।
মূল উপলব্ধি: P = NP-এর প্রমাণ তত্ত্বকে সঙ্গে সঙ্গে বদলে দিত, কিন্তু বাস্তবকে বদলাত কেবল যদি algorithm-টি ছোট সূচক আর ধ্রুবকের হয়; “polynomial” আর “দ্রুত” সমার্থক নয়।
প্র ০৩Diagonalization দিয়ে halting problem আর time hierarchy প্রমাণ হলো, অথচ P ≠ NP-তে কেন আটকে যায়? কোন ফলগুলো relativization বাধা পেরিয়েছে?
Diagonalization-এর মূল কাজ: একটি যন্ত্র D অন্য সব যন্ত্রকে simulate করে আর প্রতিটির উত্তর অন্তত একটি input-এ উল্টে দেয়। Halting problem-এ (পর্ব ৫১) D-এর হাতে অসীম সময়; time hierarchy-তে D-এর হাতে একটু বেশি সময়, যা দিয়ে কম সময়ের সব যন্ত্র simulate করা যায়। P ≠ NP-এর জন্য একই কাজ করতে হলে একটি NP যন্ত্রকে প্রতিটি polynomial সময়ের deterministic যন্ত্র simulate করে উল্টে দিতে হবে, আর তার নিজের সময় একটি স্থির polynomial-এ সীমিত থাকতে হবে। কিন্তু সব polynomial (n, n2, n3, …) একটি স্থির polynomial দিয়ে ছাড়ানো যায় না; nondeterminism এখানে সাহায্য করে কি না, ঠিক সেটিই অজানা প্রশ্ন।
Baker–Gill–Solovay এই অনুভূতিকে উপপাদ্যে রূপ দেন। যে প্রমাণ শুধু “simulate করা আর উল্টানো” ব্যবহার করে, তা oracle-সহ সব জগতে চলে। কিন্তু oracle A = TQBF-এর জগতে PA = NPA, তাই সেখানে P ≠ NP-এর কোনো প্রমাণ চলতে পারে না। লক্ষ করুন, বাধাটি সূক্ষ্ম: diagonalization নিষিদ্ধ নয়; শুধু diagonalization আর অন্য relativizing উপাদান একা যথেষ্ট নয়।
কয়েকটি বড় ফল এই বাধা পেরিয়েছে। সবচেয়ে বিখ্যাত IP = PSPACE (Lund–Fortnow–Karloff–Nisan এবং Shamir, ১৯৯০ সালের দিকে)। এর জন্য এমন oracle জানা আছে যেখানে IPA ≠ PSPACEA, তাই প্রমাণটি relativize করতে পারে না। এর কৌশল arithmetization: Boolean সূত্রকে সসীম field-এর ওপর বহুপদী হিসেবে দেখা, আর verifier random বিন্দুতে বহুপদীর মান মিলিয়ে দেখে। একই ধারায় PCP theorem (১৯৯০-এর দশকের শুরু, পর্ব ৭১)। Cook–Levin theorem-এর tableau প্রমাণও (পর্ব ৬০) যন্ত্রের গণনার “স্থানীয় গঠন” ব্যবহার করে, যা oracle থাকলে সহজে ভাঙে।
কিন্তু ২০০৮ সালে Aaronson আর Wigderson দেখান, arithmetization-ও একটি দুর্বল অর্থে relativize করে (algebrization), আর P বনাম NP সেই দুর্বল অর্থেও আটকে আছে। তাই সফল প্রমাণকে তিনটি বাধাই এড়াতে হবে। Williams-এর ২০১১ সালের ACC0 lower bound দেখায় এটি অন্তত দুর্বল প্রশ্নে সম্ভব।
মূল উপলব্ধি: Diagonalization relativize করে, আর P বনাম NP দুই দিকের oracle-জগৎ আছে বলে relativizing কৌশল একা যথেষ্ট নয়; IP = PSPACE-এর মতো ফল দেখায় বাধা পেরোনো যায়, কিন্তু algebrization আরেকটি দেয়াল তোলে।
প্র ০৪Factoring আর graph isomorphism কেন NP-intermediate-এর সেরা প্রার্থী? Babai-এর algorithm আর Shor-এর algorithm এই ছবিতে কী যোগ করে?
NP-intermediate প্রমাণ করা যায় না (তা P ≠ NP প্রমাণ করত), তাই “প্রার্থী” মানে দুই দিকের পরোক্ষ প্রমাণ: একদিকে polynomial algorithm জানা নেই, অন্যদিকে NP-complete হলে কোনো বড় অসম্ভাব্য পরিণাম আসত।
Factoring-এর decision রূপে “হ্যাঁ”-এর certificate একটি গুণনীয়ক, আর “না”-এর certificate n-এর পুরো মৌলিক উৎপাদক-বিশ্লেষণ, প্রতিটি মৌলিকের প্রমাণসহ (PRIMES ∈ P হওয়ায় এটি এখন সরাসরি মেলানো যায়)। তাই এটি NP ∩ coNP-তে। কোনো NP-complete সমস্যা coNP-তে থাকলে NP = coNP হতো; তাই factoring NP-complete হলে NP = coNP, যা অসম্ভাব্য মনে করা হয়। অন্যদিকে বহু শতাব্দীর চেষ্টাতেও সাধারণ কম্পিউটারে polynomial algorithm মেলেনি; জানা সেরা general number field sieve মোটামুটি exp(c · (log n)1/3 (log log n)2/3) সময়ের, যা polynomial-এর চেয়ে ধীর কিন্তু পূর্ণ সূচকীয়ের চেয়ে দ্রুত।
Peter Shor ১৯৯৪ সালে দেখান, একটি quantum কম্পিউটার factoring polynomial সময়ে করতে পারে, অর্থাৎ factoring ∈ BQP. এটি P বনাম NP মীমাংসা করে না: factoring NP-complete বলে জানা নেই, আর BQP-তে NP-complete সমস্যা আছে বলে বিশ্বাস করার কারণও কম (পর্ব ৭৫)। কিন্তু এটি factoring-কে “সম্ভবত NP-complete নয়” দলের আরও কাছে রাখে।
Graph isomorphism-এর গল্প আলাদা। ১৯৮০-এর দশকের interactive proof-এর ফল থেকে জানা যায়, GI NP-complete হলে polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ত, যা অসম্ভাব্য। অন্যদিকে বাস্তবে GI প্রায়ই সহজ: nauty-র মতো প্রোগ্রাম বিশাল graph-ও দ্রুত মেলায়। László Babai ২০১৫ সালে একটি quasi-polynomial, অর্থাৎ 2(log n)c সময়ের algorithm ঘোষণা করেন। ২০১৭ সালের শুরুতে Harald Helfgott বিশ্লেষণে একটি ত্রুটি পান, আর Babai কয়েক দিনের মধ্যে সংশোধন প্রকাশ করেন বলে জানান। এটি GI-কে P-এর খুব কাছে নিয়ে আসে, কিন্তু P-তে নয়। মজার ব্যাপার: Ladner-এর উপপাদ্য বলে NP-intermediate অঞ্চলটি নিজেই অসীম স্তরে বিভক্ত, তাই factoring আর GI দুটিই মাঝামাঝি হলেও তারা পরস্পরের সমান কঠিন হবে, এমন নয়।
মূল উপলব্ধি: Factoring (NP ∩ coNP) আর GI (NP-complete হলে hierarchy ধসে) এমন সমস্যা, যাদের NP-complete হওয়া অসম্ভাব্য আর P-তে থাকা অজানা; Shor আর Babai তাদের সহজ দিকে ঠেলেছেন, কিন্তু কোনোটির অবস্থান প্রমাণিত নয়।
প্র ০৫একটি “P = NP-এর প্রমাণ” হাতে এলে একজন সতর্ক পাঠক কী কী জিজ্ঞেস করবেন? ইতিহাসের কোন ধরনের ভুল বারবার ফিরে আসে?
প্রথম প্রশ্ন সবসময়: algorithm-টি কোথায়, আর তা কি একটি পরিচিত NP-complete সমস্যার প্রতিটি instance-এ সঠিক উত্তর দেয়? দাবিদার যদি একটি নতুন সমস্যা আনেন, প্রথমে দেখতে হবে সেটি সত্যিই NP-complete কি না, অর্থাৎ SAT বা 3SAT থেকে সঠিক দিকে একটি reduction আছে কি না। এরপর সবচেয়ে কাজের পরীক্ষা হাতে-কলমে: algorithm-টি একটি ছোট instance-সংগ্রহে চালান, আর brute force-এর সঙ্গে মেলান। m = 4.26n-এর কাছের random 3CNF, বা পরিচিত কঠিন benchmark, প্রায়ই ভুল সঙ্গে সঙ্গে ধরে।
দ্বিতীয় প্রশ্ন সময়ের হিসাব: প্রতিটি ধাপ কি সত্যিই input-দৈর্ঘ্যের polynomial? সাধারণ লুকোনো ভুল হলো একটি “ছোট” কাজ যা আসলে সব subset বা সব ক্রমের ওপর চলে, বা সংখ্যার মান দিয়ে সময় মাপা (pseudo-polynomial). আরেকটি হলো একটি linear program বা ভিন্ন সমস্যায় রূপান্তর, যার আকার নিজেই সূচকীয়। TSP-কে polynomial আকারের LP-তে লেখার বহু চেষ্টা হয়েছে; Yannakakis ১৯৮৮ সালে দেখান symmetric এমন LP সূচকীয় আকারের হতে বাধ্য, আর ২০১২ সালে Fiorini, Massar, Pokutta, Tiwary আর de Wolf সাধারণ extended formulation-এর জন্যও একই দেখান। তাই “TSP-এর polynomial LP” দাবি এখন একটি প্রমাণিত দেয়ালে ধাক্কা খায়।
P ≠ NP-এর দাবিতে প্রশ্নগুলো অন্য রকম: যুক্তিটি কি relativize করে? তাহলে TQBF oracle-এর জগতেও চলবে, যেখানে উপসংহারটি মিথ্যা, তাই যুক্তিতে ভুল থাকতেই হবে। যুক্তিটি কি একটি natural circuit lower bound? যুক্তিটি কি 2SAT বা XOR-SAT-এর মতো P-এর একটি সমস্যার জন্যও “কঠিনতা” প্রমাণ করে ফেলে? করলে নিশ্চিতভাবে ভুল। ২০১০ সালে Deolalikar-এর দাবিতে বিশেষজ্ঞেরা অনলাইনে প্রকাশ্যে আলোচনা করে কয়েক সপ্তাহে এমন মৌলিক সমস্যা চিহ্নিত করেন; সেই আলোচনা নিজেই একটি শিক্ষণীয় দলিল।
শেষে সম্মানের কথা: ভুল প্রমাণ লেখা লজ্জার নয়, অনেক বড় গণিতবিদও ভুল প্রমাণ লিখেছেন। কিন্তু একটি দাবি গবেষক সমাজে গৃহীত হয় শুধু বিস্তারিত যাচাইয়ের পর।
মূল উপলব্ধি: একটি P বনাম NP দাবি যাচাইয়ে চারটি প্রশ্ন প্রায় সব ভুল ধরে: পরিচিত NP-complete সমস্যার সব instance-এ সঠিক কি না, সময় input-দৈর্ঘ্যে polynomial কি না, reduction-এর দিক ঠিক কি না, আর যুক্তিটি কোনো পরিচিত বাধায় পড়ে কি না।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের সংখ্যা বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা (oracle যন্ত্র): বাজারঘরের ছয়টি গুদাম 1–6; দুটি গুদামের মধ্যে “সরাসরি ট্রাক” থাকলে edge: {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,5}, {5,6}, {4,6}. একটি polynomial সময়ের oracle Turing machine MCLIQUE-এর high-level বর্ণনা নকশা করুন, যা শুধু “G-এ k আকারের clique আছে?” প্রশ্ন করে সবচেয়ে বড় clique-টি বের করে। এই graph-এ চালিয়ে দেখান কতগুলো প্রশ্ন লাগে (binary search-এ মাঝের মান ⌈(lo + hi)/2⌉, vertex মোছার ক্রম 1 থেকে 6).
বর্ণনা: “(১) k-এর ওপর binary search: lo = 1, hi = |V|; প্রতি ধাপে mid = ⌈(lo + hi)/2⌉ নিয়ে oracle-কে ⟨G, mid⟩ জিজ্ঞেস; হ্যাঁ হলে lo = mid, না হলে hi = mid − 1; শেষে k* = lo. (২) প্রতিটি vertex v-এর জন্য: ⟨G − v, k*⟩ জিজ্ঞেস; হ্যাঁ হলে G থেকে v স্থায়ীভাবে মুছে ফেলা। (৩) বাকি vertex-গুলোই উত্তর।” প্রশ্ন বড়জোর log2|V| + |V|, প্রতিটি প্রশ্ন লেখা polynomial, তাই MCLIQUE polynomial সময়ের। সঠিকতা: ধাপ ২-এর প্রতিটি মোছার পরও k*-clique থাকে, আর শেষে প্রতিটি বাকি vertex দরকারি, তাই বাকি সেট ঠিক একটি k*-clique.
এই graph-এ: mid = 4 → না (hi = 3); mid = 2 → হ্যাঁ (lo = 2); mid = 3 → হ্যাঁ (lo = 3); k* = 3, ৩টি প্রশ্ন। তারপর 1, 2, 3 মোছা যায় ({4, 5, 6} তখনও একটি ত্রিভুজ), কিন্তু 4, 5, 6 মুছলে আর 3-clique থাকে না। উত্তর {4, 5, 6}, মোট ৯টি প্রশ্ন। ({2, 3, 4}-ও একটি 3-clique; মোছার ক্রম বদলালে সেটি আসতে পারে।) সংখ্যাগুলো scratch-এ brute-force oracle দিয়ে মেলানো।
-
প্রমাণ: প্রমাণ করুন: যদি P = NP হয়, তাহলে ∅ আর Σ∗ ছাড়া P-এর প্রতিটি language B NP-complete. ∅ আর Σ∗ কেন বাদ?
B ∈ P = NP, তাই B ∈ NP. NP-hard দেখাতে যেকোনো A ∈ NP নিন। B ≠ ∅, তাই একটি y1 ∈ B আছে; B ≠ Σ∗, তাই একটি y0 ∉ B আছে। P = NP বলে A-এর একটি polynomial সময়ের decider MA আছে। f(w) = “MA-কে w-এ চালানো; গ্রহণ করলে y1 লেখা, নইলে y0 লেখা।” f polynomial সময়ের (y0, y1 স্থির string), আর w ∈ A ⇔ f(w) = y1 ⇔ f(w) ∈ B. তাই A ≤p B. ∎
∅ বাদ, কারণ কোনো f-এর জন্য f(w) ∈ ∅ কখনো সত্য নয়, তাই A ≠ ∅ হলে A ≤p ∅ অসম্ভব। একইভাবে Σ∗-এ সবকিছু থাকে, তাই A ≠ Σ∗ হলে A ≤p Σ∗ অসম্ভব। এ কারণেই ছবি ৬৩.১-এর নিচের অংশে এই দুটি বাদ।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: P ≠ NP. প্রমাণ: polynomial সময়ের সব deterministic যন্ত্র M1, M2, … তালিকা করি, যেখানে Mi ni সময়ে থামে। L = {⟨Mi⟩ : Mi ⟨Mi⟩-কে ni ধাপের মধ্যে গ্রহণ করে না}. Diagonal যুক্তিতে L কোনো Mi-এর language নয়, তাই L ∉ P. আবার একটি NTM ⟨Mi⟩ পেয়ে Mi-কে ni ধাপ simulate করে উত্তর উল্টাতে পারে, তাই L ∈ NP. ∴ P ≠ NP. ∎” ভুলটি কোথায়?
“L ∉ P” অংশটি ঠিক। ভুল “L ∈ NP” অংশে। NP-এর একটি যন্ত্রকে একটি স্থির polynomial nk সময়ে থামতে হবে। কিন্তু input ⟨Mi⟩-এ simulate করতে ni ধাপ লাগে, আর i input-এর সঙ্গে বাড়ে; কোনো একটি k সব i-কে ছাড়ায় না। তাই simulator-টি polynomial সময়ের নয়; এটি আসলে L ∈ EXP দেখায়, যা time hierarchy-র যুক্তির সঙ্গে মেলে। Nondeterminism এখানে কোনো সাহায্যই করছে না: “উত্তর উল্টানো” একটি deterministic কাজ।
দ্বিতীয় সংকেত: যুক্তিটি শুধু simulation আর diagonalization ব্যবহার করে, তাই relativize করে। সঠিক হলে প্রতিটি oracle A-তে PA ≠ NPA প্রমাণ করত, অথচ A = TQBF-এ PA = NPA (উপপাদ্য ৪.১)। তাই কোথাও ভুল থাকতেই হবে, আর ভুলটি ওপরের সময়-সীমায়।
-
হিসাব (আউটপুট অনুমান): একটি যন্ত্র এক দিনে 8.64 × 1013 ধাপ চালায়। galactic.py অনুযায়ী এক দিনে n3-এর algorithm n = 44208, 1.3n-এর algorithm n = 122 আর 2n-এর algorithm n = 46 পর্যন্ত সামলায়। যন্ত্রটি ১০০০ গুণ দ্রুত হলে প্রতিটির সর্বোচ্চ n মোটামুটি কত হবে? কোন algorithm সবচেয়ে বেশি লাভ পায়, আর কেন?
n3: নতুন n3 = ১০০০ × পুরোনো, তাই n গুণ হয় ∛1000 = 10: প্রায় ৪,৪২,০৮০ (৪ লাখের বেশি)। 1.3n: 1.3n′ = 1000 · 1.3n ⇒ n′ = n + log1.3 1000 ≈ n + 26.3, অর্থাৎ ১২২ থেকে প্রায় ১৪৮. 2n: n′ = n + log2 1000 ≈ n + 9.97, অর্থাৎ ৪৬ থেকে প্রায় ৫৬. (log-গুলো scratch-এ Python দিয়ে হিসাব করা: 26.33 আর 9.97.)
Polynomial algorithm গুণ আকারে লাভ পায় (n দশগুণ), আর সূচকীয় algorithm শুধু একটি যোগ (n-এ কয়েকটি বেশি)। তাই হার্ডওয়্যারের উন্নতি সূচকীয় সময়ের সমস্যাকে বাঁচাতে পারে না; ভালো algorithm (ছোট ভিত্তি, যেমন 1.3) বা polynomial algorithm-ই আসল লাভ। এটিই P বনাম NP প্রশ্নকে বাস্তবেও গুরুত্বপূর্ণ করে, আর ETH-এর মতো অনুমান ঠিক এই ভিত্তির সীমা নিয়ে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রম“শুধু simulation আর diagonalization দিয়ে P ≠ NP প্রমাণ করা যায় না” যুক্তির ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- প্রমাণ-কৌশলটি শুধু অন্য যন্ত্র simulate করা আর উত্তর উল্টানো ব্যবহার করে
- তাই সব যন্ত্রকে একই oracle A দিলেও প্রমাণটি হুবহু চলে (relativize করে)
- তাহলে প্রমাণটি প্রতিটি oracle A-তে PA ≠ NPA দেখাত
- কিন্তু A = TQBF নিলে PA = NPA (Baker–Gill–Solovay)
- অতএব এমন কৌশল একা P ≠ NP প্রমাণ করতে পারে না
P বনাম NP প্রশ্নের বর্তমান অবস্থা সম্পর্কে কোন বক্তব্যটি সঠিক?
- P ≠ NP প্রমাণিত, শুধু প্রকাশ বাকি
- P ⊆ NP প্রমাণিত, কিন্তু P = NP কি না খোলা
- Baker–Gill–Solovay প্রমাণ করেছে প্রশ্নটি প্রমাণ-অযোগ্য
- NP ⊊ P প্রমাণিত
কেউ দেখালেন যে 3-COLOR-এর একটি O(n5) সময়ের সঠিক algorithm আছে (3-COLOR NP-complete). প্রমাণযোগ্যভাবে কী আসে?
- শুধু 3-COLOR P-তে, বাকি NP-complete সমস্যা আগের মতো
- P = NP = EXP
- P = NP, আর তাই NP = coNP
- বাস্তবের সব encryption সঙ্গে সঙ্গে দ্রুত ভাঙা যাবে
Baker–Gill–Solovay (১৯৭৫) উপপাদ্যের সঠিক বক্তব্য কোনটি?
- এমন oracle A আছে যাতে PA = NPA, আর এমন B আছে যাতে PB ≠ NPB
- প্রতিটি oracle A-তে PA ≠ NPA
- P = NP, কারণ TQBF oracle-এ দুটি সমান
- কোনো প্রমাণে diagonalization ব্যবহার করা যাবে না
Ladner-এর উপপাদ্য (১৯৭৫) কী বলে?
- Factoring NP-intermediate
- P = NP হলে NP-intermediate সমস্যা আছে
- P ≠ NP
- P ≠ NP হলে NP-তে এমন language আছে, যা P-তেও নয়, NP-complete-ও নয়
Exponential Time Hypothesis (ETH) সম্পর্কে কোনটি সঠিক?
- ETH প্রমাণিত, আর এটি P ≠ NP-এর চেয়ে দুর্বল
- ETH অপ্রমাণিত, আর সত্য হলে P ≠ NP-ও সত্য
- ETH বলে 3SAT-এর জন্য 2n-এর চেয়ে ভালো algorithm অসম্ভব
- ETH বলে 2SAT সূচকীয় সময় নেয়
Graph isomorphism (GI) সম্পর্কে কোন বক্তব্যটি সঠিক?
- GI NP-complete প্রমাণিত
- Babai ২০১৫ সালে GI ∈ P প্রমাণ করেন
- GI NP-তে, কিন্তু P-তে বা NP-complete বলে জানা নেই; quasi-polynomial algorithm আছে
- GI NP-তে নেই, কারণ কোনো ছোট certificate নেই
বাজারঘরের একজন developer বললেন: “আমার নতুন heuristic ১০,০০০টি random TSP instance-এ সেরা রুট দিয়েছে, তাই TSP P-তে।” এই দাবির প্রধান ভুল কী?
- কয়েকটি instance-এ পরীক্ষা worst-case সঠিকতা আর polynomial সময়ের প্রমাণ নয়
- TSP NP-তে নেই, তাই প্রশ্নই ওঠে না
- Heuristic ব্যবহার করাই ভুল
- দাবিটি relativize করে, তাই ভুল
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- P ⊆ NP প্রমাণিত; P = NP কি না খোলা। P = NP ⇔ SAT ∈ P ⇔ যেকোনো একটি NP-complete সমস্যা P-তে। বেশিরভাগ গবেষক P ≠ NP মনে করেন, কিন্তু প্রমাণিত নয়।
- P = NP হলে: NP search polynomial সময়ে (self-reduction), NP = coNP, one-way function নেই, NP ≠ EXP; কিন্তু “polynomial” মানেই বাস্তবে দ্রুত নয়।
- P ≠ NP হলে: কোনো NP-complete সমস্যা P-তে নেই আর NP-intermediate আছে (Ladner); কিন্তু cryptography-র নিরাপত্তা বা সূচকীয় lower bound আপনা-আপনি আসে না।
- তিন বাধা: relativization (BGS ১৯৭৫: PA = NPA আর PB ≠ NPB), natural proofs (১৯৯৪), algebrization (২০০৮)। এগুলো কৌশলের সীমা, অসম্ভবতার প্রমাণ নয়।
- ETH আর SETH অপ্রমাণিত, P ≠ NP-এর চেয়ে শক্ত অনুমান। বাস্তবে NP-complete সমস্যায় solver, approximation, FPT আর ছোট n-এ exact algorithm; প্রতিটি উত্তর verifier-এ মেলান।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৫৮ · NP — verifier আর nondeterministic polynomial timeফিরে দেখুনCertificate, verifier আর P ⊆ NP ⊆ EXP-এর প্রমাণ।
- পর্ব ৫১ · Diagonalization আর halting problemফিরে দেখুনযে কৌশল relativize করে, তার সবচেয়ে বিখ্যাত ব্যবহার।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৬৪-এ space complexity.
- DSA · পর্ব ৬৪ — P বনাম NPপাশের ট্র্যাকAlgorithm-এর দিক থেকে NP-complete সমস্যা আর reduction.
- DSA · পর্ব ৬৫ — NP-hard সমস্যা বাস্তবেপাশের ট্র্যাকছোট input, বিশেষ গঠন, FPT, approximation, heuristic আর solver.