Cook-Levin Theorem
কুক-লেভিন উপপাদ্য
SAT (Boolean satisfiability) NP-complete — প্রমাণিত প্রথম NP-complete সমস্যা। ১৯৭১ সালে Stephen Cook, স্বাধীনভাবে Leonid Levin। এখান থেকেই reduction দিয়ে হাজার হাজার অন্য সমস্যার NP-completeness প্রমাণিত হয়েছে।
also: Cook's theorem, Cook-Levin, SAT is NP-complete
দাবি: SAT (একটা Boolean formula satisfiable কি না) NP-complete।
প্রমাণের কৌশল — computation tableau। যেকোনো NP সমস্যার
polynomial-time verifier V-এর computation history-কে একটা গ্রিড
(tableau) হিসেবে এনকোড করা হয় — প্রতিটা সেলের জন্য একটা Boolean
variable। তারপর clause-গুচ্ছ দিয়ে নিশ্চিত করা হয়: প্রতিটা সেলে ঠিক
একটা মান, initial row সঠিক, প্রতিটা transition বৈধ, আর শেষে accept
state আছে। এই পুরো formula \phi_x satisfiable \iff কোনো
certificate দিয়ে V x accept করে — আর formula polynomial সময়ে
গণনাযোগ্য।
তাৎপর্য: SAT-এর একটা polynomial algorithm পেলেই P = NP
প্রমাণিত হয়ে যাবে — কারণ প্রতিটা NP সমস্যা SAT-এ reduce হয়।
এটাই SAT-কে “universal translator” বানায় — reduction transitivity
দিয়ে হাজার হাজার অন্য সমস্যার (3-SAT, Vertex Cover, Independent
Set, …) NP-completeness এখান থেকেই বংশবিস্তার করেছে।
গভীর বার্তা: কম্পিউটেশন নিজেই একটা Boolean formula-য় এনকোড করা যায় — এই observation পরে circuit complexity, zero-knowledge proof, এবং আধুনিক zk-SNARK/zk-STARK প্রযুক্তির ভিত্তি হয়ে দাঁড়িয়েছে।