P vs NP
পি বনাম এনপি
গণিত/computer science-এর সবচেয়ে বিখ্যাত খোলা প্রশ্ন — P (দ্রুত সমাধানযোগ্য) কি NP (দ্রুত যাচাইযোগ্য)-এর সমান? Clay Millennium Prize সমস্যা, $১ মিলিয়ন পুরস্কার, এখনো অমীমাংসিত।
also: P=NP, P versus NP, P?=NP
P হলো deterministic polynomial-time সমাধানযোগ্য সমস্যার class;
NP হলো সেই সমস্যা যাদের সমাধান polynomial-time যাচাইযোগ্য।
P ⊆ NP প্রমাণিত (তুচ্ছ); P = NP কি না — অমীমাংসিত।
বিশ্বাস: প্রায় সব গবেষক মনে করেন P ≠ NP — কিন্তু কোনো প্রমাণ
নেই। প্রমাণ-প্রচেষ্টা দুইটা পরিচিত কাঠামোগত বাধায় আটকায়:
relativization barrier (Baker-Gill-Solovay, ১৯৭৫ — কিছু
oracle-world-এ P=NP, কিছুতে P≠NP, তাই oracle-relativizing
কৌশল যথেষ্ট নয়) আর natural proofs barrier (Razborov-Rudich,
১৯৯৪ — “natural” circuit-lower-bound কৌশল cryptographic one-way
function অস্তিত্বশীল হলে কাজ করতে পারে না)।
যদি P = NP প্রমাণিত হয়: one-way function-এর অস্তিত্ব অসম্ভব
হয়ে যায় — তাই cryptography-র ভিত্তি (RSA-সহ) নীতিগতভাবে ভেঙে পড়ে,
যদিও কোনো সরাসরি reduction RSA-কে ভাঙে না (factoring NP-complete
বলে প্রমাণিত নয়)। Automated theorem proving আর হাজার হাজার
optimization সমস্যা তাত্ত্বিকভাবে সমাধানযোগ্য হয়ে যায় — বাস্তব
গতি নির্ভর করবে algorithm-এর polynomial exponent-এর উপর।
Clay Millennium Prize (২০০০)-এর সাতটা সমস্যার একটা, $১ মিলিয়ন পুরস্কার, এখনো দাবিদারহীন।