Pseudo-polynomial time
গণনামূলক জটিলতা তত্ত্বে, একটি সংখ্যাসূচক অ্যালগরিদম ছদ্ম-বহুপদী সময়ে চলে যদি তার চলমান সময়টি ইনপুটের সংখ্যাসূচক মানের একটি বহুপদী হয় (ইনপুটটিতে উপস্থিত বৃহত্তম পূর্ণসংখ্যা)-তবে ইনপুটের দৈর্ঘ্যে অগত্যা নয় (এটি প্রতিনিধিত্ব করার জন্য প্রয়োজনীয় বিটের সংখ্যা), যা বহুপদী সময় অ্যালগরিদমের ক্ষেত্রে হয়। সাধারণভাবে, ইনপুটের সংখ্যাসূচক মান ইনপুট দৈর্ঘ্যে সূচকীয়, যে কারণে একটি ছদ্ম-বহুপদী সময় অ্যালগরিদম ইনপুট দৈর্ঘ্যের সাপেক্ষে বহুপদী সময়ে চলে না। পরিচিত সিউডো-পলিনোমিয়াল টাইম অ্যালগরিদম সহ একটি এনপি-সম্পূর্ণ সমস্যাকে দুর্বলভাবে এনপি-সম্পূর্ণ বলা হয়। একটি এনপি-সম্পূর্ণ সমস্যাকে দৃঢ়ভাবে এনপি-সম্পূর্ণ বলা হয় যদি এটি প্রমাণিত হয় যে এটি একটি ছদ্ম-বহুপদী সময় অ্যালগরিদম দ্বারা সমাধান করা যায় না যদি না। শক্তিশালী/দুর্বল ধরনের এনপি-কঠোরতা অনুরূপভাবে সংজ্ঞায়িত করা হয়। উদাহরণস্বরূপ প্রাথমিক পরীক্ষা একটি সংখ্যা n মৌলিক কিনা তা পরীক্ষা করার সমস্যাটি বিবেচনা করুন, সরলভাবে পরীক্ষা করে দেখুন যে কোনও সংখ্যা সমানভাবে বিভক্ত হয় কি না। এই পদ্ধতিটি বিভাজন পর্যন্ত নিতে পারে, যা n-এর মানে উপ-রৈখিক কিন্তু n-এর দৈর্ঘ্যে সূচকীয় (যা প্রায়)। উদাহরণস্বরূপ, এন-এর দৈর্ঘ্য মাত্র 11 অঙ্ক হলেও, এন-এর তুলনায় সামান্য কম সংখ্যার জন্য প্রায় 100,000 পর্যন্ত বিভাগের প্রয়োজন হবে। উপরন্তু কেউ সহজেই একটি ইনপুট লিখতে পারে (ধরুন, একটি 300-সংখ্যার সংখ্যা) যার জন্য এই অ্যালগরিদমটি অবাস্তব। যেহেতু গণনামূলক জটিলতা (এনকোডেড) ইনপুটের দৈর্ঘ্যের সাপেক্ষে অসুবিধা পরিমাপ করে, তাই এই সরল অ্যালগরিদমটি আসলে সূচকীয়। তবে এটি ছদ্ম-বহুপদী সময়। এই অ্যালগরিদমটিকে একটি সত্যিকারের বহুপদী সংখ্যাসূচক অ্যালগরিদমের সাথে তুলনা করুন-ধরুন, যোগের জন্য সোজা অ্যালগরিদমঃ দুটি 9-সংখ্যার সংখ্যা যোগ করতে প্রায় 9 টি সহজ পদক্ষেপ লাগে এবং সাধারণভাবে অ্যালগরিদমটি ইনপুটের দৈর্ঘ্যে সত্যই রৈখিক। যোগ করা প্রকৃত সংখ্যার (বিলিয়নগুলিতে) তুলনায়, অ্যালগরিদমটিকে "সিউডো-লগারিদমিক সময়" বলা যেতে পারে, যদিও এই ধরনের শব্দটি আদর্শ নয়। সুতরাং, 300-সংখ্যার সংখ্যা যোগ করা অবাস্তব নয়। একইভাবে, দীর্ঘ বিভাজন দ্বিঘাতঃ একটি এম-অঙ্কের সংখ্যাকে ধাপে ধাপে একটি এন-অঙ্কের সংখ্যা দ্বারা ভাগ করা যেতে পারে (বিগ ও স্বরলিপি দেখুন।) প্রাথমিকতার ক্ষেত্রে, দেখা যায় যে n মৌলিক (2002 সালে আবিষ্কৃত) কিনা তা পরীক্ষার জন্য একটি ভিন্ন অ্যালগরিদম রয়েছে যা সময়ের সাথে চলে। ন্যাপস্যাকের সমস্যা ন্যাপস্যাকের সমস্যায়, আমাদের ওজন এবং মূল্য সহ একটি ন্যাপস্যাকের সর্বোচ্চ ওজনের ক্ষমতা সহ আইটেম দেওয়া হয়। লক্ষ্য হল নিম্নলিখিত অপ্টিমাইজেশান সমস্যাটি সমাধান করা; অনানুষ্ঠানিকভাবে, মান সর্বাধিক করার জন্য ন্যাপস্যাকে আইটেমগুলি ফিট করার সর্বোত্তম উপায় কী? এবং-এর সাপেক্ষে সর্বাধিক করুন। এই সমস্যাটি সমাধান করা এনপি-হার্ড, তাই একটি বহুপদী সময় অ্যালগরিদম অসম্ভব যদি না। যাইহোক, গতিশীল প্রোগ্রামিং ব্যবহার করে একটি সময় অ্যালগরিদম সম্ভব; যেহেতু সংখ্যাটি বর্ণনা করার জন্য শুধুমাত্র বিট প্রয়োজন, এই অ্যালগরিদমটি ছদ্ম-বহুপদী সময়ে চলে। যদিও ছদ্ম-বহুপদী সময়ের ধারণাটি প্রায় একচেটিয়াভাবে সংখ্যাসূচক সমস্যার জন্য ব্যবহৃত হয়, তবে ধারণাটি সাধারণীকরণ করা যেতে পারেঃ m ফাংশনটি ছদ্ম-বহুপদী যদি m (n) সমস্যার আকার n এর বহুপদী ফাংশনের চেয়ে বড় না হয় এবং ইনপুটের একটি অতিরিক্ত বৈশিষ্ট্য, k (n)। (সম্ভবত, k কে সমস্যার সাথে প্রাসঙ্গিক কিছু হিসাবে বেছে নেওয়া হয়েছে।) এটি k কে ইনপুটের সংখ্যাসূচক মান হিসাবে গ্রহণ করে সংখ্যাসূচক বহুপদী সমস্যাগুলিকে একটি বিশেষ ক্ষেত্রে পরিণত করে। একটি সংখ্যার মান এবং তার দৈর্ঘ্যের মধ্যে পার্থক্য হল এনকোডিংঃ যদি সংখ্যাসূচক ইনপুটগুলি সর্বদা ইউনারিতে এনকোড করা হয়, তবে সিউডো-পলিনোমিয়াল পলিনোমিয়ালের সাথে মিলে যায়। আরও দেখুন স্ট্রংলি এনপি-সম্পূর্ণ আধা-বহুপদী সময় তথ্যসূত্র অ্যালগরিদমের বিশ্লেষণ জটিলতা শ্রেণী গণনামূলক জটিলতা তত্ত্ব ছদ্ম-বহুপদী সময় অ্যালগরিদম