NP-equivalent
গণনামূলক জটিলতা তত্ত্বে, জটিলতা শ্রেণী এন. পি-সমতুল্য হল ফাংশন সমস্যার সেট যা এন. পি-সহজ এবং এন. পি-শক্ত উভয়ই। এনপি-সমতুল্য হল ফাংশন সমস্যার জন্য এনপি-সম্পূর্ণের এনালগ। উদাহরণস্বরূপ, FIND-SABSET-SAM সমস্যাটি এনপি-সমতুল্য। পূর্ণসংখ্যার একটি সেট দেওয়া হলে, FIND-SABSET-SAM হল শূন্য পর্যন্ত যোগ হওয়া পূর্ণসংখ্যার কিছু অ-খালি উপসেট খুঁজে বের করার সমস্যা (অথবা যদি এমন কোনও উপসেট না থাকে তবে খালি সেটটি ফেরত দেওয়া)। এই অপ্টিমাইজেশান সমস্যাটি সিদ্ধান্ত সমস্যা সাবসেট-এসইউএম-এর অনুরূপ। পূর্ণসংখ্যার একটি সেট দেওয়া হলে, সাবসেট-এস. ইউ. এম হল শূন্যের সমষ্টি সহ একটি উপসেট বিদ্যমান কিনা তা খুঁজে বের করার সমস্যা। সাবসেট-এস. ইউ. এম এন. পি-সম্পূর্ণ। এফ. আই. এন. ডি-এস. ইউ. বি. এস. ই. টি-এস. ইউ. এম-কে এন. পি-সমতুল্য দেখানোর জন্য আমাদের অবশ্যই দেখাতে হবে যে এটি এন. পি-হার্ড এবং এন. পি-সহজ উভয়ই। স্পষ্টতই এটি এনপি-হার্ড। যদি আমাদের কাছে এমন একটি ব্ল্যাক বক্স থাকত যা একক সময়ে FIND-SABSET-SAM সমাধান করত, তাহলে সাবসেট-SAM সমাধান করা সহজ হত। কেবল কালো বাক্সটিকে শূন্যের সমষ্টি সহ উপসেটটি খুঁজে বের করতে বলুন, তারপরে এটি একটি খালি সেট ফিরিয়ে দিয়েছে কিনা তা পরীক্ষা করুন। এটি এনপি-ও সহজ। যদি আমাদের কাছে একটি কালো বাক্স থাকত যা একক সময়ে সাবসেট-সাম সমাধান করত, তাহলে আমরা এটি ব্যবহার করে ফাইন্ড-সাবসেট-সাম সমাধান করতে পারতাম। যদি এটি মিথ্যা ফিরে আসে, আমরা অবিলম্বে খালি সেটটি ফেরত দিই। অন্যথায়, আমরা প্রতিটি উপাদান ক্রমানুসারে পরিদর্শন করি এবং এটি সরিয়ে ফেলি তবে শর্ত থাকে যে সাবসেট-সাম এটি অপসারণের পরেও সত্য ফিরে আসবে। একবার আমরা প্রতিটি উপাদান পরিদর্শন করার পরে, আমরা আর সত্য থেকে মিথ্যা উত্তর পরিবর্তন না করে কোনও উপাদান অপসারণ করতে সক্ষম হব না; এই মুহুর্তে মূল উপাদানগুলির অবশিষ্ট উপসেটকে অবশ্যই শূন্যে যোগ করতে হবে। এর জন্য আমাদের লক্ষ্য রাখতে হবে যে, পরবর্তী উপাদান অপসারণ এই সত্যকে পরিবর্তন করে না যে, পূর্ববর্তী উপাদান অপসারণের ফলে উত্তরটি সত্য থেকে অসত্য হয়ে যায়। সিউডোকোডেঃ ফাংশন FIND-SABSET-SAM (সেট S) যদি না হয় (SABSET-SAM (S)) S-এ প্রতিটি x-এর জন্য {} রিটার্ন করে যদি SABSET-SAM (S-{x}) S: = S-{x} রিটার্ন S হয়। এই প্রসঙ্গে এন. পি-র অর্থ হল অনির্ধারিত বহুপদী সময়। বুলিয়ান ফাংশনের এনপি-সমতুল্য শ্রেণীও রয়েছে, যেখানে এনপি মানে হল নেতিবাচকতা এবং বিন্যাস। উল্লেখগুলি উল্লেখ করুন। জটিলতার ক্লাস