কম্পিউটেশনাল জটিলতা তত্ত্বে, একটি বহুপদী-সময় হ্রাস হল ব্যবহার করে একটি সমস্যা সমাধানের একটি পদ্ধতি। জটিলতা শ্রেণী এবং সেই শ্রেণীর জন্য সম্পূর্ণ সমস্যা উভয়কে সংজ্ঞায়িত করার জন্য জটিলতা তত্ত্বে বহুপদ-সময় হ্রাস প্রায়শই ব্যবহৃত হয়। …
বহুপদ সময়কে কী বলে?
একটি অ্যালগরিদমকে বহুপদী সময়ের বলা হয় যদি এটির চলমান সময় অ্যালগরিদমের ইনপুটের আকারে একটি বহুপদী অভিব্যক্তি দ্বারা সীমাবদ্ধ থাকে, অর্থাৎ, T(n)=O(nk) কিছু ধনাত্মক ধ্রুবকের জন্য।
আপনি কিভাবে বুঝবেন যে কিছু একটা বহুপদী সময়?
3 উত্তর। একটি অ্যালগরিদম হল বহুপদী (বহুপদ চলমান সময় আছে) যদি কিছু k, C>0 এর জন্য, n আকারের ইনপুটগুলিতে এটির চলমান সময় সর্বাধিক Cnk হয়। সমানভাবে, একটি অ্যালগরিদম বহুপদী হয় যদি কিছু k>0 এর জন্য, n আকারের ইনপুটগুলিতে এটির চলমান সময় হয় O(nk)।
যদি সূচকীয় সময়ে হ্রাস অনুমোদিত হয় তাহলে কী হবে?
যদি হ্রাসকে সূচকীয় সময়ের অনুমতি দেওয়া হয়, তাহলে এটি মূল সমস্যাটি সম্পূর্ণরূপে সমাধান করতে পারে এবং লক্ষ্য সমস্যার একটি তুচ্ছ উদাহরণ তৈরি করতে পারে এর মানে হল NP-এর প্রতিটি সমস্যা প্রত্যেকের জন্য হ্রাসযোগ্য এই ধরনের হ্রাস দ্বারা অন্যান্য সমস্যা, তাই NP-এর প্রতিটি সমস্যাই সূচকীয় সময় হ্রাসের জন্য NP-সম্পূর্ণ।
একটি সূচকীয় অ্যালগরিদম কী?
একটি অ্যালগরিদমকে সূচকীয় সময় বলা হয়, যদি T(n) উপরের সীমাবদ্ধ থাকে 2পলি() ) , যেখানে পলি(n) n-এ কিছু বহুপদ। আরও আনুষ্ঠানিকভাবে, একটি অ্যালগরিদম হল সূচকীয় সময় যদি T(n) কিছু স্থির k. Ref:Wiki-এর জন্য O(2nk) দ্বারা আবদ্ধ থাকে।
