Foundationপ্রথম নীতি থেকে
LEVEL 13লেসন ১২/২৩কঠিন৪৫ মিনিট

P vs NP-এর তাৎপর্য — একটা প্রমাণ যা পৃথিবী বদলে দিত

The Significance of P vs NP

P = NP প্রমাণিত হলে গণিত, ক্রিপ্টোগ্রাফি, আর optimization-এর জগৎ বদলে যেত — কিন্তু ঠিক কীভাবে, সেটা যতটা মনে হয় তার চেয়ে সূক্ষ্ম। আর কেন এই প্রশ্নটা ৫০ বছরের সেরা প্রচেষ্টাকেও হারিয়ে দিয়েছে, তার পেছনে আছে প্রমাণ-পদ্ধতি নিজের গাণিতিক সীমাবদ্ধতা।

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

  • P = NP প্রমাণিত হলে বাস্তবে (cryptography, optimization, automated reasoning-এ) কী ঘটতে পারে তা সূক্ষ্মতা সহ ব্যাখ্যা করতে পারবেন
  • কেন P = NP সরাসরি RSA/Diffie-Hellman ভাঙে না, অথচ কেন তবুও এটা cryptography-র জন্য বিপর্যয়কর হতে পারে তা যুক্তি দিয়ে বলতে পারবেন
  • SAT-এর self-reducibility দিয়ে দেখাতে পারবেন কেন decision problem সমাধান করাই search problem সমাধানের জন্য যথেষ্ট
  • Relativization ও natural proofs বাধা স্বজ্ঞাতভাবে ব্যাখ্যা করতে পারবেন — কেন এই প্রশ্নটা পরিচিত কৌশলে ধরা দেয় না
  • Clay Millennium Prize-এর প্রেক্ষাপটে P vs NP-এর গবেষণা-অবস্থা বর্ণনা করতে পারবেন

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

আগে এটা বুঝি

কল্পনা করুন আগামীকাল সকালে একটা খবর ভাইরাল হলো: “গণিতবিদ প্রমাণ করলেন P = NP”। কয়েক ঘণ্টার মধ্যে headline লেখা হবে — “ইন্টারনেট ব্যাংকিং আজই ভেঙে পড়বে”, “সব password এক নিমেষে ভাঙা যাবে”, “AI আজ থেকে যেকোনো গাণিতিক উপপাদ্য প্রমাণ করতে পারবে”।

এই সব দাবির মধ্যে কোনটা সত্য, আর কোনটা অতিরঞ্জিত — এটাই এই লেসনের প্রশ্ন। উত্তরটা প্রথম দর্শনে যতটা মনে হয় তার চেয়ে অনেক বেশি সূক্ষ্ম।

আগের লেসনে আমরা দেখেছি SAT NP-complete — অর্থাৎ এর জন্য একটা polynomial algorithm পেলেই প্রতিটা NP সমস্যা polynomial সময়ে সমাধানযোগ্য হয়ে যাবে। কিন্তু সাংবাদিকতার শিরোনাম আর গাণিতিক সত্যের মধ্যে ফাঁক আছে — একটা প্রমাণ থাকা আর একটা ব্যবহারযোগ্য algorithm পাওয়া এক জিনিস নয়। আর RSA-এর মতো cryptography আসলে NP-complete কোনো সমস্যার উপর দাঁড়িয়ে নেই — তাই সরাসরি reduction দিয়ে এটা ভাঙে না, যদিও পরোক্ষভাবে বিপদে পড়ে।

এই লেসনে আমরা এই প্রশ্নের তিনটা অংশ আলাদা করে দেখব: (১) P = NP প্রমাণিত হলে বাস্তবে ঠিক কী ঘটবে (আর কী ঘটবে না), (২) কেন প্রায় প্রতিটা গবেষক বিশ্বাস করেন P \ne NP, আর (৩) কেন এই বিশ্বাসটা প্রমাণ করা এত অস্বাভাবিক কঠিন — এতটাই যে প্রমাণ-পদ্ধতি নিজেই এখানে প্রাচীরে ধাক্কা খায়।

মূল ধারণা

যদি P = NP প্রমাণিত হয় — দুই ধরনের প্রমাণ, দুই ধরনের প্রভাব

প্রথম সূক্ষ্মতা: “প্রমাণিত হওয়া” আর “algorithm হাতে পাওয়া” এক জিনিস নয়।

Non-constructive প্রমাণ: গণিতে এমন প্রমাণ সম্ভব যা শুধু দেখায় যে একটা জিনিস আছে, কিন্তু সেটা কী তা বলে না। একটা P = NP-এর প্রমাণ যদি এভাবে আসে (যদিও জটিলতা তত্ত্বের প্রকৃতির কারণে এটা কম সম্ভাব্য মনে হয়, কারণ P-এর সংজ্ঞাই একটা algorithm-এর অস্তিত্ব), তাহলে আমরা জানব “একটা polynomial algorithm আছে” কিন্তু সেটা লিখতে পারব না — কোনো ব্যবহারিক প্রভাব সাথে সাথে পড়বে না।

Constructive প্রমাণ: যদি প্রমাণটা সরাসরি একটা algorithm দেয় (যেমন “এই কৌশলে SAT সমাধান করুন, আর এই কারণে এটা polynomial সময়ে চলে”), তাহলে প্রভাব নির্ভর করে সেই polynomial-এর exponent আর constant factor-এর উপর। একটা O(n^{70}) algorithm তাত্ত্বিকভাবে polynomial, কিন্তু n = 100-এও ব্যবহারের অযোগ্য। ইতিহাসে এমন হয়েছে — যেমন AKS primality test (2002) প্রথমে O(n^{12})-এর কাছাকাছি ছিল, ব্যবহারিকভাবে ধীর, পরে অপ্টিমাইজ হয়ে O(n^6)-এ নেমেছে।

Cryptography — সরাসরি ভাঙে না, কিন্তু নিরাপদও থাকে না

এটাই সবচেয়ে বেশি ভুল বোঝা অংশ। RSA নির্ভর করে factoring-এর কাঠিন্যের উপর; Diffie-Hellman নির্ভর করে discrete logarithm-এর কাঠিন্যের উপর। এই দুইটা সমস্যা NP-complete বলে প্রমাণিত নয় — বরং এরা \mathbf{NP} \cap \mathbf{co\text{-}NP}-তে আছে বলে মনে করা হয় (factoring-এর “হ্যাঁ” আর “না” দুই দিকেরই সংক্ষিপ্ত certificate আছে — মৌলিক উৎপাদক দেখানো, বা সংখ্যাটা মৌলিক তার প্রমাণ দেখানো)।

\mathbf{NP} \cap \mathbf{co\text{-}NP}-তে থাকা সমস্যাগুলো NP-complete হওয়ার সম্ভাবনা কম বলে মনে করা হয় (কারণ যদি একটা NP \cap co\text{-}NP} সমস্যা NP-complete হতো, আর NP \ne co\text{-}NP} হতো — যা বিশ্বাস করা হয় — তাহলে একটা কাঠামোগত দ্বন্দ্ব তৈরি হতো)। তাই P = NP-এর একটা প্রমাণ সরাসরি reduction দিয়ে factoring-কে ভাঙে না — কোনো \text{SAT} \le_p \text{FACTORING} জানা reduction নেই যা “SAT-এর polynomial algorithm ধার করে factoring সমাধান করুন” বলতে দেয়।

তাহলে কেন cryptographer-রা এখনো ভয় পান? দুইটা কারণ:

  1. ঐতিহাসিক প্যাটার্ন: P = NP-এর প্রায় যেকোনো বাস্তবসম্মত প্রমাণ-কৌশল এতটাই গভীর algorithmic insight দাবি করে যে সেই একই insight প্রায় নিশ্চিতভাবে factoring, discrete log-এর মতো কাছাকাছি সমস্যাতেও প্রয়োগযোগ্য হবে — এরা একই “কাঠিন্যের পরিবার”-এর সদস্য বলে মনে করা হয়, formal reduction না থাকলেও।
  2. Cryptography-র বৃহত্তর ভিত্তি নিজেই নড়বড়ে হয়ে যায়: আধুনিক cryptography দাঁড়িয়ে আছে one-way function-এর অস্তিত্বের অনুমানের উপর (এমন function যা গণনা করা সহজ কিন্তু উল্টানো কঠিন)। P = NP হলে one-way function-এর অস্তিত্বই অসম্ভব হয়ে যায় (প্রমাণ: যদি f one-way হয়, f(x) থেকে x খুঁজে বের করা একটা NP সমস্যা — certificate x, verify করা f(x)-এর সাথে মিলিয়ে দেখা, polynomial সময়ে। P = NP হলে এই খোঁজাটাও polynomial সময়ে সম্ভব হয়ে যাবে — যা “উল্টানো কঠিন” শর্তটাই ভেঙে দেয়)। আর সব symmetric cryptography (AES-এর মতো), সব public-key cryptography, এমনকি cryptographic hash function-ও one-way function-এর অস্তিত্বের উপর নির্ভরশীল। তাই P = NP cryptography-কে সরাসরি না ভেঙে হলেও এর ভিত্তিটাই ধ্বংস করে দেয়।

Automated theorem proving — গণিত নিজেই বদলে যেত

NP-এর সংজ্ঞা মনে করুন: certificate সংক্ষিপ্ত, যাচাই দ্রুত। এখন লক্ষ্য করুন — একটা গাণিতিক উপপাদ্যের প্রমাণও ঠিক এই কাঠামো মেনে চলে: একটা প্রস্তাবিত প্রমাণ (certificate) দেওয়া হলে, সেটা সঠিক কি না formal logic-এর নিয়ম মেনে যাচাই করা যান্ত্রিক ও দ্রুত (প্রতিটা ধাপ আগের ধাপ থেকে অনুমান-নিয়মে বেরিয়ে আসছে কি না চেক করা)।

তাই: “একটা উপপাদ্যের n-দৈর্ঘ্যের প্রমাণ (যদি থাকে) আছে কি?” এটা নিজেই একটা NP সমস্যা। P = NP হলে — এবং এটা কার্যকরভাবে দ্রুত হলে — যেকোনো উপপাদ্য যার একটা “ছোট” প্রমাণ আছে (formal system-এর সাপেক্ষে), সেই প্রমাণ স্বয়ংক্রিয়ভাবে খুঁজে বের করা যাবে, মানুষের হস্তক্ষেপ ছাড়াই।

এই observation-টা প্রথম করেছিলেন Leonid Levin নিজেই (Cook-Levin theorem-এর “Levin”) এবং Kurt Gödel ১৯৫৬ সালে (একটা চিঠিতে John von Neumann-কে, P বনাম NP-এর আধুনিক formulation-এরও আগে!) — গণিতের ইতিহাসে P বনাম NP-এর প্রথম আভাস হিসেবে গণ্য করা হয় এই চিঠিকে।

Optimization — logistics থেকে ML পর্যন্ত

আগের লেসনে দেখা অসংখ্য NP-hard optimization সমস্যা (scheduling, routing, resource allocation, VLSI placement) P = NP হলে সবগুলোই নীতিগতভাবে polynomial সময়ে অপটিমালি সমাধানযোগ্য হয়ে যাবে — এখন যা approximation বা heuristic দিয়ে “ভালো কিন্তু নিখুঁত না” সমাধান করা হয়, তা তখন নিখুঁত optimal সমাধান দেবে, দ্রুত।

সতর্কতা: machine learning-এর মূল training সমস্যা (neural network-এর weight খুঁজে বের করা, একটা loss function minimize করে) সাধারণভাবে NP-hard বলে প্রমাণিত নয় (এটা একটা continuous optimization সমস্যা, NP-এর ঐতিহ্যগত discrete/decision framework-এর বাইরে, যদিও নির্দিষ্ট সরলীকৃত সংস্করণ — যেমন ছোট neural network-এর exact training — NP-hard প্রমাণিত)। তাই P = NP সরাসরি “AI আজ থেকে নিখুঁত হয়ে যাবে” বোঝায় না — কিন্তু ML pipeline-এর ভেতরের অনেক discrete sub-problem (feature selection, architecture search, কিছু combinatorial hyperparameter tuning) সত্যিই সরাসরি উপকৃত হতো।

ভেতরে কী ঘটছে

Self-reducibility — কেন “decision” সমাধান করলেই “search” পাওয়া যায়

একটা গুরুত্বপূর্ণ সূক্ষ্মতা পরিষ্কার করা দরকার: NP-এর সংজ্ঞা decision problem (হ্যাঁ/না) নিয়ে কথা বলে। কিন্তু বাস্তব আগ্রহ প্রায়ই search problem-এ — “একটা satisfying assignment কী?”, শুধু “আছে কি না” নয়। সৌভাগ্যক্রমে, SAT-এর জন্য এই দুইটা সমস্যা সমান কঠিন — এই property-টার নাম self-reducibility।

ধরুন আমাদের কাছে SAT-এর জন্য একটা polynomial-time decision oracle D(\phi) আছে (\phi satisfiable কি না বলে দেয়, কিন্তু assignment বলে না)। একটা satisfying assignment খুঁজে বের করতে এই oracle-টা বারবার ব্যবহার করা যায়:

১. যদি D(φ) = false, তাহলে unsatisfiable — থামুন
২. x₁ = true বসিয়ে φ সরল করুন, পান φ'
৩. যদি D(φ') = true: x₁ = true চূড়ান্ত করুন, φ'-এর উপর x₂ থেকে আবার শুরু করুন (ধাপ ২-এ ফিরুন)
৪. নাহলে: x₁ = false বসিয়ে সরল করুন (φ'' বলুন), অবশ্যই D(φ'') = true হবে
   (কারণ ধাপ ১-এ জানা গেছে মূল φ satisfiable, আর x₁-এর দুইটা মানের
   অন্তত একটা কাজ করবেই) — x₁ = false চূড়ান্ত করে φ''-এর উপর চালিয়ে যান
৫. সব variable-এর মান বসানো পর্যন্ত পুনরাবৃত্তি করুন

n-টা variable, প্রতিটাতে O(1)-টা oracle call — মোট O(n)-টা call, প্রতিটা polynomial সময়ে। তাই decision oracle থাকলে, পুরো satisfying assignment O(n)-টা oracle call-এই খুঁজে বের করা যায় — search আর decision-এর মধ্যে শুধু একটা polynomial factor-এর পার্থক্য।

কেন প্রায় সবাই বিশ্বাস করেন P ≠ NP

প্রমাণ নেই, কিন্তু কাঠামোগত সাক্ষ্য প্রচুর:

১. পঞ্চাশ বছরের ব্যর্থ প্রচেষ্টা। হাজার হাজার NP-complete সমস্যা, বিশ্বের সেরা গবেষকরা, কোনো একটার জন্যও কোনো polynomial algorithm নেই। এটা প্রমাণ নয় (গণিতে “আমরা খুঁজে পাইনি” কখনো “নেই” প্রমাণ করে না), কিন্তু শক্তিশালী inductive সাক্ষ্য।

২. Ladner’s theorem (1975) — যদি P \ne NP, তাহলে NP\text{-intermediate} সমস্যাও আছে। এই উপপাদ্য প্রমাণ করে: যদি P \ne NP, তাহলে এমন সমস্যাও আছে যা NP-তে, কিন্তু P-তেও না, NP-complete-ও না — একটা “মধ্যবর্তী” অঞ্চল। (Factoring-কে অনেকে এই অঞ্চলের একজন candidate বলে মনে করেন — না P-তে প্রমাণিত, না NP-complete বলে প্রমাণিত।) এই কাঠামোগত সমৃদ্ধি (P, intermediate, NP-complete — তিনটা স্তর) নিজেই ইঙ্গিত দেয় hierarchy-টা “সমতল” নয়, P = NP হওয়ার সম্ভাবনা কম।

৩. Polynomial hierarchy collapse। P = NP হলে একটা সম্পূর্ণ অসীম হায়ারার্কি (Polynomial Hierarchy, \Sigma_k^p, \Pi_k^p স্তরসমূহ, quantifier-এর সংখ্যা দিয়ে সংজ্ঞায়িত জটিলতা class-এর ক্রম) সম্পূর্ণভাবে ভেঙে P-তে পতিত হয়ে যাবে (একটা স্তরে সমতা পুরো হায়ারার্কিকে ধসিয়ে দেয় — এই ফলাফলের নাম হায়ারার্কি collapse theorem)। এতগুলো স্বতন্ত্র, স্বাভাবিকভাবে সংজ্ঞায়িত class সবগুলো হঠাৎ একই হয়ে যাওয়াটা কাঠামোগতভাবে “অসম্ভাব্য” মনে হয় — যদিও আবারও, এটা প্রমাণ নয়, একটা কাঠামোগত সাক্ষ্য।

Relativization barrier — কেন সরল simulation কৌশল কাজ করবে না

১৯৭৫ সালে Baker, Gill, আর Solovay একটা অস্বস্তিকর ফলাফল দেখান।

কল্পনা করুন একটা “oracle” A — একটা কাল্পনিক black-box যা কিছু সমস্যা তাৎক্ষণিক (এক ধাপে) সমাধান করে দেয়। P^A আর NP^A কে সংজ্ঞায়িত করুন P আর NP-এর মতোই, কিন্তু এই oracle ব্যবহারের সুবিধাসহ।

তারা দেখান দুইটা oracle A আর B আছে এমন যে:

PA=NPAঅথচPB≠NPB\mathbf{P}^A = \mathbf{NP}^A \qquad \text{অথচ} \qquad \mathbf{P}^B \ne \mathbf{NP}^B

কেন এটা সমস্যা তৈরি করে? কারণ P বনাম NP নিয়ে এখন পর্যন্ত পরিচিত প্রায় সব “সরল” প্রমাণ-কৌশল (diagonalization, simulation-based যুক্তি — Time hierarchy theorem-এর মতো যা আগের লেসনে দেখেছি) একটা প্রপার্টি রাখে: সেগুলো relativize করে, অর্থাৎ oracle যোগ করলেও একইভাবে কাজ করে। কিন্তু যদি কোনো কৌশল relativize করে, আর সেটা P \ne NP প্রমাণ করত, তাহলে সেই একই যুক্তি \mathbf{P}^A = \mathbf{NP}^A oracle-এও প্রয়োগ করলে একটা দ্বন্দ্ব তৈরি হতো (কারণ oracle A-এর জগতে P = NP)। যেহেতু দ্বন্দ্বটা বাস্তব, উপসংহার: কোনো relativizing কৌশল P \ne NP প্রমাণ করতে পারবে না (আর কোনো relativizing কৌশল P = NP-ও প্রমাণ করতে পারবে না, একই যুক্তিতে B oracle ব্যবহার করে)।

Relativization barrier — কেন এটা একটা প্রাচীর
  1. পরিচিত প্রমাণ-কৌশলDiagonalization, direct simulation — Time Hierarchy Theorem-এর মতো (আগের লেসন)
  2. এই কৌশলগুলোর সাধারণ প্রপার্টি"Relativize করে" — oracle যোগ করলেও একইভাবে কাজ করে
  3. Baker-Gill-Solovay-এর ফলাফলকিছু oracle-এ P=NP, কিছুতে P≠NP — উভয়ই সমান বৈধ জগৎ
  4. উপসংহারকোনো relativizing কৌশল P vs NP নিষ্পত্তি করতে পারবে না — নতুন, non-relativizing কৌশল লাগবে

Natural proofs barrier — আরেকটা গভীর দেয়াল

১৯৯৪ সালে Razborov আর Rudich আরেকটা বাধা খুঁজে পান, আরো গভীর একটা কারণে — এটা সরাসরি cryptography-র সাথে যুক্ত।

P \ne NP প্রমাণ করার একটা স্বাভাবিক উপায় হতো: দেখানো যে SAT-এর মতো একটা সমস্যার জন্য কোনো ছোট Boolean circuit থাকতে পারে না (একটা “circuit lower bound”)। গবেষকরা লক্ষ্য করেন যে এখন পর্যন্ত পরিচিত প্রায় সব circuit-lower-bound-কৌশল একটা সাধারণ প্যাটার্নের (“natural proof”) মধ্যে পড়ে — এগুলো গঠনমূলক (efficiently checkable — একটা function “কঠিন” কি না তা নিজেই দ্রুত পরীক্ষাযোগ্য) আর ব্যাপক (বেশিরভাগ random function-এই প্রযোজ্য)।

তাদের বিস্ময়কর ফলাফল: যদি শক্তিশালী one-way function (আর pseudorandom function generator) অস্তিত্বশীল হয় (যা cryptography-র ভিত্তি — বিশ্বাস করা হয় অস্তিত্বশীল), তাহলে কোনো “natural proof” NP-এর জন্য প্রয়োজনীয় শক্তিশালী circuit lower bound প্রমাণ করতে পারবে না।

এখানেই একটা বিদ্রূপাত্মক পরিস্থিতি তৈরি হয়: P \ne NP প্রমাণ করার পরিচিত সবচেয়ে স্বাভাবিক পথ (circuit lower bound) ঠিক সেই একই জিনিসের (pseudorandomness/one-way function-এর অস্তিত্ব) উপর নির্ভর করে বাধাপ্রাপ্ত হয়, যা P \ne NP বিশ্বাসের পেছনের cryptographic motivation। প্রমাণ-পদ্ধতিটাই নিজের লক্ষ্যের বিরুদ্ধে কাজ করে।

Clay Millennium Prize

২০০০ সালে Clay Mathematics Institute সাতটা “Millennium Prize Problem” ঘোষণা করে, প্রতিটার সমাধানের জন্য $১ মিলিয়ন পুরস্কার — P বনাম NP তাদের একটা (আরেকটা, Poincaré conjecture, ২০০৩ সালে Grigori Perelman সমাধান করেন এবং পুরস্কার প্রত্যাখ্যান করেন — এখন পর্যন্ত একমাত্র সমাধানকৃত Millennium Problem)।

সমস্যা ঘোষণার পর থেকে ২৫ বছরের বেশি পার হয়ে গেছে — কোনো গৃহীত সমাধান নেই। প্রতি বছর কয়েকটা (“প্রমাণ”) দাবি আসে (arXiv-তে, বা সরাসরি গবেষকদের কাছে) — এখন পর্যন্ত প্রতিটাতেই ত্রুটি পাওয়া গেছে, বেশিরভাগই প্রকাশের কয়েক ঘণ্টা বা দিনের মধ্যে।

উদাহরণ

একটা সংখ্যাগত উদাহরণ — polynomial exponent কতটা গুরুত্বপূর্ণ

ধরুন কাল্পনিকভাবে SAT-এর জন্য একটা algorithm পাওয়া গেল যার সময় O(n^{10})। n = 100 variable-এর একটা মাঝারি আকারের formula-তে এটা প্রয়োগ করলে দেখি সংখ্যাটা বাস্তবে কী বোঝায়:

AlgorithmComplexityn = 100-এ ধাপ সংখ্যা১০⁹ ধাপ/সেকেন্ডে সময়
ভালো polynomialO(n^2)10^4মাইক্রোসেকেন্ড
মাঝারি polynomialO(n^4)10^8০.১ সেকেন্ড
আজকের brute-force SATO(2^n)~10^{30}মহাবিশ্বের বয়সের চেয়ে বেশি
কাল্পনিক “P=NP” algorithmO(n^{10})10^{20}কয়েক হাজার বছর
আরো ভালো কাল্পনিক algorithmO(n^{3})10^{6}মিলিসেকেন্ড
একই 'polynomial' exponent-এর ব্যবহারিক প্রভাব কতটা ভিন্ন হতে পারে, n = 100-এ।

পাঠ: brute-force-এর তুলনায় O(n^{10}) তাত্ত্বিকভাবে “সমাধান করা হয়ে গেছে” — কিন্তু বাস্তবে এখনো অব্যবহারযোগ্য। তাত্ত্বিক বিজয় (P = NP) আর ব্যবহারিক বিজয় (দ্রুত algorithm হাতে থাকা) দুই ভিন্ন মাইলফলক — একটা অন্যটার নিশ্চয়তা দেয় না। ঐতিহাসিকভাবে অবশ্য, একবার একটা সমস্যার জন্য প্রথম polynomial algorithm পাওয়া গেলে (যতই বড় exponent হোক), গবেষকরা প্রায় সবসময় দ্রুত সেটা optimize করেছেন — linear programming (প্রথম polynomial algorithm, ellipsoid method, ব্যবহারিকভাবে ধীর; পরে interior-point method অনেক দ্রুত) এর একটা ঐতিহাসিক উদাহরণ।

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

EXPERIMENT

Self-reducibility নিজে চালিয়ে দেখুন — decision থেকে search

Python 3· ১৫ মিনিট
import itertools

def decision_oracle(clauses, n_vars, fixed):
    """
    fixed: {var_index: bool} — কিছু variable-এর মান ইতিমধ্যে স্থির।
    বাকি variable-এর জন্য brute-force দিয়ে satisfiability চেক করে
    (এটাই ভান করছি একটা 'জাদুকরী polynomial oracle' — বাস্তবে P=NP
    হলে এটাই polynomial সময়ে চলত, এখানে শুধু ছোট n-এ demonstrate করছি)
    """
    free_vars = [i for i in range(1, n_vars + 1) if i not in fixed]
    for bits in itertools.product([False, True], repeat=len(free_vars)):
        assignment = dict(fixed)
        assignment.update(zip(free_vars, bits))
        if all(any((assignment[abs(l)] if l > 0 else not assignment[abs(l)])
                   for l in clause) for clause in clauses):
            return True
    return False

def find_assignment_via_self_reduction(clauses, n_vars):
    """শুধু decision oracle ব্যবহার করে পূর্ণ satisfying assignment বের করে"""
    if not decision_oracle(clauses, n_vars, {}):
        return None  # unsatisfiable

    fixed = {}
    oracle_calls = 0
    for var in range(1, n_vars + 1):
        fixed[var] = True
        oracle_calls += 1
        if decision_oracle(clauses, n_vars, fixed):
            continue  # true কাজ করল, রাখুন
        fixed[var] = False  # true কাজ করেনি, false-ই হতে হবে (self-reducibility guarantee)
    return fixed, oracle_calls


# একটা ৫-variable, non-trivial formula
clauses = [
    [1, 2, -3], [-1, 3, 4], [2, -4, 5], [-2, -5, 1], [3, 4, -5],
]
n_vars = 5

result = find_assignment_via_self_reduction(clauses, n_vars)
if result:
    assignment, calls = result
    print(f"Satisfying assignment: {assignment}")
    print(f"Oracle call সংখ্যা      : {calls}  (n = {n_vars}, তাই O(n) ✓)")

    # যাচাই
    ok = all(any((assignment[abs(l)] if l > 0 else not assignment[abs(l)])
                 for l in clause) for clause in clauses)
    print(f"সব clause satisfied?    : {ok}")
else:
    print("Unsatisfiable")

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

Satisfying assignment: {1: True, 2: True, 3: True, 4: True, 5: False}
Oracle call সংখ্যা      : 5  (n = 5, তাই O(n) ✓)
সব clause satisfied?    : True

লক্ষ্য করুন: oracle কে ঠিক n = 5-বার ডাকা হয়েছে (এই কোডে প্রতি variable-এ ১টা call — একটু optimize করলে “false” নিশ্চিত হওয়া call এড়ানো যায়, কিন্তু worst case-ও O(n)), আর প্রতিবার শুধু “satisfiable কি না” জিজ্ঞাসা করা হয়েছে — কখনো সরাসরি “assignment কী” জিজ্ঞাসা করা হয়নি। এই O(n)-টা call-ই পুরো assignment পুনর্গঠন করে দিয়েছে — সেই একই কৌশল যা P = NP প্রমাণিত হলে decision solver থেকে পূর্ণ solution বের করতে ব্যবহৃত হবে।

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

একটা decision-only SAT oracle (satisfiable কি না বলে, কিন্তু assignment না) দিয়েও পুরো satisfying assignment মাত্র O(n)-টা oracle call-এ পুনর্গঠন করা যায় — 'P=NP মানে search-ও সমাধানযোগ্য' দাবিটার সরাসরি বাস্তব প্রমাণ।

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

অনিশ্চয়তার মধ্যে বাস্তব সিদ্ধান্ত

P বনাম NP অমীমাংসিত থাকা সত্ত্বেও প্রতিদিন শিল্প-ক্ষেত্র সিদ্ধান্ত নেয় — P \ne NP}-কে একটা working hypothesis হিসেবে ধরে:

Cryptography standard। NIST-এর মতো সংস্থা cryptographic standard (RSA key size, AES) নির্ধারণ করে এই অনুমানে যে factoring/discrete-log কঠিন থাকবে — P \ne NP} প্রমাণিত না হলেও, “এখনো কেউ ভাঙতে পারেনি” কে যথেষ্ট practical evidence ধরে সিদ্ধান্ত নেওয়া হয়, নিয়মিত key size বাড়িয়ে (নতুন আক্রমণ কৌশলের বিরুদ্ধে safety margin রাখতে)।

Post-quantum cryptography। এখানে একটা তাৎপর্যপূর্ণ ব্যতিক্রম লক্ষ্য করা যায় — quantum computer (Shor’s algorithm) factoring আর discrete log polynomial সময়ে সমাধান করতে পারে, P বনাম NP নিষ্পত্তি না করেই (কারণ Shor’s algorithm BQP class-এর, classical P-এর নয়, আর এটা NP-complete কোনো সমস্যা সমাধান করে না — এটা নির্দিষ্টভাবে factoring-এর algebraic গঠন কাজে লাগায়)। এই কারণেই পুরো industry এখন lattice-based cryptography-তে সরে যাচ্ছে — সমস্যাগুলো যেন P বনাম NP বা quantum, দুই বিতর্কের বাইরেও নিরাপদ থাকে বলে বিশ্বাস করা হয়।

Venture capital ও research funding। কম্পিউটেশনাল biology (protein folding-এর নির্দিষ্ট সংস্করণ NP-hard), logistics optimization, chip design কোম্পানি জানে তাদের core সমস্যা NP-hard — তাই তারা exact solver-এর বদলে heuরিস্টিক/approximation/ML-ভিত্তিক পদ্ধতিতে বিনিয়োগ করে, P = NP-এর অপেক্ষায় না থেকে।

একাডেমিক গবেষণার দিকনির্দেশ। Complexity theory-র একটা বড় অংশ (পরের লেসনের বিষয়) সরাসরি P \ne NP} ধরে নিয়ে এগিয়েছে — approximation algorithm-এর গ্যারান্টি, randomized algorithm-এর bound, এসবের অনেকগুলোর ভিত্তি এই অনুমান (বা তার চেয়েও শক্তিশালী অনুমান, যেমন Unique Games Conjecture) — প্রমাণ ছাড়াই, কারণ অপেক্ষা করলে পুরো ক্ষেত্রটা স্থবির হয়ে যেত।

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

“P vs NP প্রমাণিত হয়ে গেছে — P ≠ NP, এটা এখন প্রতিষ্ঠিত জ্ঞান।”

না — এটা এখনো সম্পূর্ণ অমীমাংসিত, ২০২৬ সাল পর্যন্তও।

বেশিরভাগ গবেষক (জরিপে প্রায় ৮০-৯০%) P \ne NP} বিশ্বাস করেন — কিন্তু বিশ্বাস আর প্রমাণ গণিতে এক জিনিস নয়। এই লেসনের “hood” অংশে আলোচিত সব সাক্ষ্য (ব্যর্থ প্রচেষ্টা, Ladner’s theorem, hierarchy collapse) evidence, proof নয়।

Clay Millennium Prize আজও দাবিদারহীন। যেকোনো পাঠ্যবই বা প্রবন্ধ যা “যেহেতু P ≠ NP প্রমাণিত…” বলে শুরু করে, সেটা ভুল বলছে — সঠিক বাক্যাংশ “যেহেতু P ≠ NP বলে বিশ্বাস করা হয়…” বা “P ≠ NP ধরে নিলে…”।

“P = NP প্রমাণিত হলে শুধু খারাপ জিনিস ঘটবে (cryptography ভাঙা)।”

একপাক্ষিক দৃষ্টিভঙ্গি — এই লেসনের “concept” অংশে দেখা গেছে প্রভাবটা দ্বিমুখী।

খারাপ দিক: cryptography-র ভিত্তি (one-way function-এর অস্তিত্ব) ভেঙে পড়ে।

ভালো দিক: automated theorem proving বাস্তবে সম্ভব হয়ে যেত (Gödel-এর কল্পনা করা জগৎ), হাজার হাজার optimization সমস্যা (logistics, scheduling, VLSI design, drug discovery-র কিছু উপ-সমস্যা) নিখুঁতভাবে ও দ্রুত সমাধানযোগ্য হয়ে যেত, বিজ্ঞান ও প্রকৌশলের বহু ক্ষেত্রে বিশাল অগ্রগতি হতো।

বাস্তবে ফলাফলটা মিশ্র এবং সভ্যতা-স্তরের একটা পুনর্বিন্যাস হতো — নিছক “বিপর্যয়” বলাটা গল্পের অর্ধেক বলা।

“P = NP প্রমাণ হলেও সেটা 'শুধু তাত্ত্বিক' — বাস্তব প্রভাব থাকবে না যদি algorithm-টা impractically ধীর হয় (যেমন O(n^100))।”

আংশিক সত্য, কিন্তু সম্পূর্ণ ছবি নয়।

সত্য অংশ: এই লেসনের “সংখ্যাগত উদাহরণ” অংশে দেখা গেছে, একটা বড়-exponent polynomial algorithm ব্যবহারিকভাবে অব্যবহারযোগ্য হতে পারে।

কিন্তু cryptography-র জন্য এটা প্রযোজ্য নয় — cryptographic নিরাপত্তা প্রমাণ সাধারণত এই রকম দাবি করে: “যদি কোনো polynomial-time algorithm থাকে (exponent যাই হোক), তাহলে নিরাপত্তা ভেঙে যায়” (কারণ one-way function-এর সংজ্ঞাই “কোনো polynomial-time adversary সফল হতে পারবে না” — একটা O(n^{1000}) algorithm-ও এই সংজ্ঞা লঙ্ঘন করে, ব্যবহারিক গতি নির্বিশেষে)। তাই তাত্ত্বিক P = NP প্রমাণ, exponent যত বড়ই হোক, cryptography-র নিরাপত্তা-সংজ্ঞাকেই অকার্যকর করে দেয় — যদিও বাস্তবে আক্রমণকারী হয়তো সাথে সাথে ব্যবহারিক আক্রমণ চালাতে পারবে না, পুরো ক্ষেত্রের ভিত্তি-অনুমান তখনও নীতিগতভাবে ভেঙে যাবে, আর দীর্ঘমেয়াদে (optimize হওয়ার পরে) ব্যবহারিক আক্রমণও প্রায় অবশ্যম্ভাবী ধরে নেওয়া হবে।

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

1

RSA-এর নিরাপত্তা NP-completeness-এর উপর সরাসরি দাঁড়িয়ে নেই — তাহলে কেন P = NP-এর একটা প্রমাণ তবুও RSA-এর জন্য বিপজ্জনক বলে গণ্য হয়? দুইটা আলাদা যুক্তি দিন।

যুক্তি

যুক্তি ১ — সরাসরি (কিন্তু দুর্বল): Factoring \mathbf{NP} \cap \mathbf{co\text{-}NP}}-তে আছে — NP-এর একটা উপসেট। P = NP হলে NP-এর সব সমস্যা P-তে চলে আসে, factoring সহ (কারণ NP \cap co\text{-}NP} \subseteq NP)। তাই যদিও কোনো পরিচিত reduction SAT-কে factoring-এ যুক্ত করে না, P = NP-এর সংজ্ঞা নিজেই factoring-সহ NP-এর সব সমস্যাকে P-তে টেনে আনে, কারণ P = NP মানে P NP-এর সমান, এবং factoring NP-এর সদস্য।

যুক্তি ২ — কাঠামোগত (গভীর): RSA-এর নিরাপত্তা “one-way function অস্তিত্বশীল” এই অনুমানের একটা বিশেষ ক্ষেত্র। P = NP হলে কোনো one-way function-ই অস্তিত্বশীল থাকতে পারে না (এই লেসনের “concept” অংশের প্রমাণ — যেকোনো f(x) invert করা নিজেই একটা NP সমস্যা, P = NP হলে সব NP সমস্যা polynomial সময়ে সমাধানযোগ্য, তাই invert করাও)। RSA-এর f(x) = x^e \bmod n একটা (দাবি করা) one-way function — তাই P = NP সরাসরি এই দাবিটাকেই মিথ্যা প্রমাণ করে দেয়, factoring-এর জন্য নির্দিষ্ট কোনো reduction ছাড়াই।

দুইটা যুক্তিই একই সিদ্ধান্তে পৌঁছায় ভিন্ন পথে — প্রথমটা NP-এর সংজ্ঞা থেকে সরাসরি, দ্বিতীয়টা one-way function-এর গঠন থেকে।

2

Relativization barrier ঠিক কী দেখায়, আর natural proofs barrier-এর থেকে এটা মূলত কীভাবে আলাদা?

স্মরণ

Relativization barrier: দেখায় দুইটা oracle A, B আছে এমন যে \mathbf{P}^A = \mathbf{NP}^A কিন্তু \mathbf{P}^B \ne \mathbf{NP}^B। যেহেতু পরিচিত প্রায় সব “সরল” প্রমাণ-কৌশল (diagonalization, simulation) oracle-এর উপস্থিতিতেও একইভাবে কাজ করে (“relativize” করে), আর দুই বিপরীত oracle-জগতে দুই বিপরীত উত্তর সত্য, তাই কোনো relativizing কৌশল P বনাম NP নিষ্পত্তি করতে পারবে না — অন্যথায় একই কৌশল দুই বিপরীত oracle-জগতে দুই বিপরীত সিদ্ধান্তে পৌঁছাত, যা স্ববিরোধী।

Natural proofs barrier: ভিন্ন ধরনের বাধা — এটা নির্দিষ্টভাবে circuit-lower-bound-ভিত্তিক প্রমাণ-কৌশল নিয়ে কথা বলে, oracle নিয়ে নয়। এটা দেখায় “natural” (গঠনমূলক + ব্যাপক) circuit lower bound প্রমাণ-কৌশল, যদি শক্তিশালী one-way function অস্তিত্বশীল হয়, তাহলে NP আলাদা করার জন্য প্রয়োজনীয় শক্তির lower bound প্রমাণ করতেই পারবে না — cryptographic hardness assumption-এর সাথে সরাসরি সংযুক্ত একটা বাধা।

মূল পার্থক্য: relativization barrier একটা oracle-ভিত্তিক, model-theoretic বাধা (কোনো cryptographic অনুমান লাগে না প্রমাণ করতে); natural proofs barrier cryptography-র (অনুমিত) কাঠিন্যের উপর নির্ভরশীল একটা বাধা। দুটোই আলাদাভাবে দেখায় “পরিচিত ধরনের” কৌশল যথেষ্ট নয়, কিন্তু সম্পূর্ণ ভিন্ন গাণিতিক যন্ত্র ব্যবহার করে।

3

Self-reduction demo-তে (experiment অংশ) oracle-কে ঠিক n-বার ডাকা হয়েছিল একটা n-variable formula-র জন্য। যদি প্রতিটা oracle call নিজেই O(n^3) সময় নেয় (একটা কাল্পনিক polynomial SAT-decider), তাহলে পুরো satisfying-assignment-খোঁজার প্রক্রিয়ার মোট সময়-জটিলতা কত? এটা কি তখনও polynomial?

প্রয়োগ

মোট সময় = (\text{oracle call সংখ্যা}) \times (\text{প্রতি call-এর সময়)} = O(n) \times O(n^3) = O(n^4)।

হ্যাঁ, এখনো polynomial — polynomial-এর polynomial-গুণ composition polynomial-ই থাকে (এটা P-এর একটা গুরুত্বপূর্ণ closure property, যা P class-কে “স্বাভাবিক” ও ব্যবহারযোগ্য করে তোলে — polynomial-time subroutine-কে polynomial-বার call করলেও সামগ্রিক algorithm polynomial-ই থাকে)।

এই observation-টাই ব্যাখ্যা করে কেন self-reducibility “বিনামূল্যে” আসে যদি P = NP প্রমাণিত হয় — decision oracle-এর polynomial সময় আর oracle-call সংখ্যার polynomial বাউন্ড একসাথে গুণ হয়ে এখনো polynomial থাকে, তাই “decision সমাধানযোগ্য” থেকে “search সমাধানযোগ্য”-তে যাওয়ার পথে কোনো “exponential leap” নেই।

4

আপনি একটা কাল্পনিক গবেষণা প্রবন্ধ পড়ছেন যা দাবি করছে “আমরা একটা নতুন প্রমাণ-কৌশল আবিষ্কার করেছি যা diagonalization বা simulation-এর কোনো রূপ নয়, বরং directly circuit-এর algebraic structure বিশ্লেষণ করে, এবং এটা দিয়ে আমরা P \ne NP প্রমাণ করেছি।” এই দাবিটা যাচাই করার সময় আপনি প্রথমে কোন দুইটা প্রশ্ন জিজ্ঞাসা করবেন, এই লেসনের আলোচিত দুইটা বাধার ভিত্তিতে?

ডিজাইন

প্রশ্ন ১ (relativization): “এই কৌশলটা কি relativize করে?” অর্থাৎ, যদি একটা oracle A যোগ করা হয় যেখানে \mathbf{P}^A = \mathbf{NP}^A} (যেমন A = \text{PSPACE}-complete কোনো ভাষা, যেখানে জানা আছে relativized world-এ সমতা ঘটে), তাহলে কি একই প্রমাণ-কৌশল সেই oracle-world-এও একই সিদ্ধান্তে পৌঁছায় (P^A \ne NP^A)? যদি হ্যাঁ, তাহলে প্রমাণটা ভুল (একটা স্ববিরোধিতা তৈরি হয়েছে) — relativization barrier অনুযায়ী এটা relativize করতেই পারে না। লেখকদের দেখাতে হবে ঠিক কোথায় তাদের কৌশল oracle-নির্ভর জগতে ভেঙে পড়ে (non-relativizing হওয়ার সুনির্দিষ্ট কারণ)।

প্রশ্ন ২ (natural proofs): “এই কৌশলটা কি ‘natural’ প্রমাণের সংজ্ঞা মেনে চলে — অর্থাৎ, এটা কি একটা efficiently-checkable property ব্যবহার করছে যা বেশিরভাগ random function-এও সত্য?” যদি হ্যাঁ, তাহলে Razborov-Rudich অনুযায়ী এই কৌশল pseudorandom function generator-এর অস্তিত্বের বিরুদ্ধে কাজ করবে — যদি cryptographic one-way function সত্যিই অস্তিত্বশীল হয় (যা প্রায় সবাই বিশ্বাস করেন), তাহলে এই কৌশলটা কাজ করতে পারবেই না। লেখকদের দেখাতে হবে তাদের property কীভাবে “unnatural” — বেশিরভাগ random function-এ প্রযোজ্য নয়, বা efficiently checkable নয়।

এই দুইটা প্রশ্নই বাস্তবে জটিলতা তত্ত্বের গবেষকরা প্রথম জিজ্ঞাসা করেন যখন কোনো নতুন P \ne NP দাবি সামনে আসে — এবং প্রায় প্রতিটা প্রকাশিত ভুল দাবিই এই দুই প্রশ্নের কোনো একটায় ব্যর্থ হয়ে ধরা পড়েছে।

এরপর কী

আমরা দেখেছি P বনাম NP প্রমাণিত হলে কী ঘটবে, আর কেন এটা প্রমাণ করা এত কঠিন। কিন্তু বাস্তব ইঞ্জিনিয়ারদের P = NP-এর জবাবের জন্য অপেক্ষা করার সুযোগ নেই — scheduling চালাতে হয়, package resolve করতে হয়, ML model train করতে হয় আজই, NP-hard সমস্যা মোকাবিলা করে।

পরের লেসনে আমরা দেখব বাস্তবে এই মোকাবিলা কীভাবে হয়: approximation algorithm (প্রমাণযোগ্য গ্যারান্টি সহ প্রায়-optimal সমাধান), randomized algorithm ও \mathbf{BPP} class, আর PCP theorem — যা দেখায় কিছু সমস্যার আনুমানিক সমাধানও কেন সমান কঠিন।

আরও পড়ুন

  • The Status of the P Versus NP Problem — Lance Fortnow · Communications of the ACM, 2009 — সাধারণ পাঠকের জন্য সেরা সারসংক্ষেপ, এই লেসনের অনেক উদাহরণের উৎস
  • Relativizations of the P =? NP Question — Theodore Baker, John Gill, Robert Solovay · 1975 — relativization barrier-এর মূল paper
  • Natural Proofs — Alexander Razborov, Steven Rudich · 1994 — natural proofs barrier, cryptography আর lower bound-এর গভীর সংযোগ
  • P vs NP Problem — Clay Mathematics Institute · Millennium Prize-এর আনুষ্ঠানিক সমস্যা-বিবৃতি