Many-One Reduction
ম্যানি-ওয়ান রিডাকশন
A ≤ₘ B — একটা computable function f আছে যেখানে w ∈ A ⟺ f(w) ∈ B। অর্থ: B সমাধানযোগ্য হলে A-ও সমাধানযোগ্য (B-র decider ধার করে); তাই A undecidable হলে B-ও undecidable।
also: mapping reduction, reduction, many-one reducible
দিকটা মনে রাখার নিয়ম: A ≤ₘ B মানে “A, B-এর চেয়ে সহজ বা সমান
কঠিন”। নতুন সমস্যা undecidable প্রমাণ করতে সবসময় পরিচিত undecidable
সমস্যা (সাধারণত HALT) থেকে নতুন সমস্যায় reduce করতে হয় —
(পরিচিত) ≤ₘ (নতুন), উল্টো দিকে না।
প্রমাণ টেমপ্লেট চার ধাপে: (১) পরিচিত undecidable ভাষা বাছাই, (২)
computable রূপান্তর f সংজ্ঞা — সাধারণত M-কে w-তে সিমুলেট
করা একটা “গেট” বসিয়ে নতুন মেশিন বানানো, (৩) f-এর computability
যাচাই, (৪) ⟺ উভয় দিক প্রমাণ।
এই একই কাঠামো (শুধু “computable” এর বদলে “polynomial-time computable”) পরে NP-completeness প্রমাণের ভিত্তি — SAT থেকে 3-SAT, vertex-cover ইত্যাদিতে reduce করার কৌশল হুবহু অভিন্ন।