NP-easy
জটিলতা তত্ত্বে, জটিলতা শ্রেণী এন. পি-সহজ হল ফাংশন সমস্যাগুলির সেট যা এন. পি-তে কিছু সিদ্ধান্তের সমস্যার জন্য একটি ওরাকল সহ একটি নির্ধারক টুরিং মেশিন দ্বারা বহুপদী সময়ে সমাধানযোগ্য। অন্য কথায়, একটি সমস্যা এক্স এনপি-সহজ হয় যদি এবং শুধুমাত্র যদি এনপিতে এমন কিছু সমস্যা থাকে যে এক্স পলিনোমিয়াল-টাইম টুরিং থেকে ওয়াই হ্রাসযোগ্য। এর মানে হল যে Y-এর জন্য একটি ওরাকল দেওয়া হলে, একটি অ্যালগরিদম বিদ্যমান যা বহুপদী সময়ে X-কে সমাধান করে (সম্ভবত সেই ওরাকলটি বারবার ব্যবহার করে)। এন. পি-ইজি হল এফ. পি. এন. পি-র আরেকটি নাম (ফাংশন সমস্যা নিবন্ধ দেখুন) বা এফ. ডি. 2. পি-র জন্য (বহুপদী শ্রেণিবিন্যাস নিবন্ধ দেখুন)। এনপি-সহজ সমস্যার একটি উদাহরণ হল স্ট্রিংয়ের একটি তালিকা বাছাই করার সমস্যা। সিদ্ধান্তের সমস্যা "স্ট্রিং এ স্ট্রিং বি এর চেয়ে বড়" এনপিতে রয়েছে। কুইকসোর্টের মতো অ্যালগরিদম রয়েছে যা তুলনামূলক রুটিনে শুধুমাত্র একটি বহুপদী কল ব্যবহার করে তালিকাটি সাজাতে পারে, পাশাপাশি অতিরিক্ত কাজের একটি বহুপদী পরিমাণ। অতএব, বাছাই করা এনপি-সহজ। আরও কঠিন সমস্যা রয়েছে যা এনপি-সহজ। একটি উদাহরণের জন্য এন. পি-সমতুল্য দেখুন। এনপি-ইজি-র সংজ্ঞায় বহু-এক হ্রাসের পরিবর্তে টুরিং হ্রাস ব্যবহার করা হয়েছে কারণ ওয়াই সমস্যার উত্তরগুলি কেবল সত্য বা মিথ্যা, তবে এক্স সমস্যার উত্তরগুলি আরও সাধারণ হতে পারে। অতএব, একই উত্তর দিয়ে X-এর একটি দৃষ্টান্তকে Y-এর একটি উদাহরণে অনুবাদ করার কোনও সাধারণ উপায় নেই। উল্লেখগুলি উল্লেখ করুন। জটিলতার ক্লাস