Cobham's thesis
কোভামের থিসিস, যা কোভাম-এডমন্ডস থিসিস নামেও পরিচিত (অ্যালান কোভাম এবং জ্যাক এডমন্ডসের নামে নামকরণ করা হয়েছে), দাবি করে যে গণনামূলক সমস্যাগুলি কেবলমাত্র কোনও গণনামূলক যন্ত্রে সম্ভাব্যভাবে গণনা করা যেতে পারে যদি সেগুলি বহুপদী সময়ে গণনা করা যায়; অর্থাৎ, যদি সেগুলি জটিলতা শ্রেণী পি-তে থাকে। আধুনিক ভাষায়, এটি জটিলতা শ্রেণী পি-এর সাথে ট্র্যাক্টেবল সমস্যাগুলি চিহ্নিত করে। আনুষ্ঠানিকভাবে, একটি সমস্যা বহুপদী সময়ে সমাধান করা যেতে পারে বলার অর্থ হল এমন একটি অ্যালগরিদম রয়েছে যা ইনপুট হিসাবে সমস্যার একটি এন-বিট উদাহরণ দেওয়া হলে, বড়-ও নোটেশন ব্যবহার করে ও (এনসি) সময়ে একটি সমাধান তৈরি করতে পারে এবং সি একটি ধ্রুবক যা সমস্যার উপর নির্ভর করে তবে সমস্যার উপর নয়। অ্যালান কোভামের 1965 সালের গবেষণাপত্রে "ফাংশনের অভ্যন্তরীণ গণনামূলক অসুবিধা" শিরোনামটি জটিলতা শ্রেণী পি-এর ধারণার প্রাচীনতম উল্লেখগুলির মধ্যে একটি, যা বহুপদী সময়ে নির্ণয়যোগ্য সমস্যাগুলির সমন্বয়ে গঠিত। কোভাম তত্ত্ব দিয়েছিলেন যে এই জটিলতা শ্রেণীটি সম্ভাব্য গণনাযোগ্য সমস্যার সেট বর্ণনা করার একটি ভাল উপায় ছিল। জ্যাক এডমন্ডসের 1965 সালের গবেষণাপত্র "পাথস, ট্রিজ, অ্যান্ড ফ্লাওয়ার্স"-কে 'পি'-কে চিহ্নিত করার কৃতিত্বও দেওয়া হয়। যদিও কোভামের থিসিস গণনামূলক জটিলতা তত্ত্বের বিকাশে একটি গুরুত্বপূর্ণ মাইলফলক, তবে অ্যালগরিদমের ব্যবহারিক সম্ভাবনার ক্ষেত্রে এর সীমাবদ্ধতা রয়েছে। থিসিসটি মূলত বলে যে "পি" মানে "সহজ, দ্রুত এবং ব্যবহারিক", যেখানে "পি-তে নয়" মানে "কঠিন, ধীর এবং অবাস্তব"। তবে এটি সর্বদা সত্য নয়, কারণ থিসিসটি অনুশীলনে রানটাইমকে প্রভাবিত করে এমন কিছু গুরুত্বপূর্ণ ভেরিয়েবলকে বিমূর্ত করেঃ এটি ধ্রুবক কারণ এবং নিম্ন-ক্রমের পদগুলিকে উপেক্ষা করে। এটি সূচকের আকারকে উপেক্ষা করে। সময় শ্রেণিবিন্যাস উপপাদ্যটি পি-তে সমস্যাগুলির অস্তিত্ব প্রমাণ করে যার জন্য নির্বিচারে বড় সূচক প্রয়োজন। এটি ইনপুটের সাধারণ আকারকে উপেক্ষা করে। তিনটিই সম্পর্কিত এবং অ্যালগরিদম বিশ্লেষণ সম্পর্কে সাধারণ অভিযোগ, তবে এগুলি বিশেষত কোভামের থিসিসের ক্ষেত্রে প্রযোজ্য, কারণ এটি ব্যবহারিকতা সম্পর্কে একটি স্পষ্ট দাবি করে। কোভামের থিসিসের অধীনে, একটি সমস্যা যার জন্য সেরা অ্যালগরিদম n200 নির্দেশাবলী গ্রহণ করে তা সম্ভব বলে মনে করা হয়, এবং একটি অ্যালগরিদমের সমস্যা যা 20.00001 n নির্দেশাবলী গ্রহণ করে তা অসম্ভব বলে মনে করা হয়-যদিও কেউ কখনও পূর্ববর্তী অ্যালগরিদমের সাথে আকার n = 2 এর একটি উদাহরণ সমাধান করতে পারে না, যেখানে আকার n = 106 এর পরবর্তী সমস্যার একটি উদাহরণ কোনও অসুবিধা ছাড়াই সমাধান করা যেতে পারে। যে ক্ষেত্রগুলিতে ব্যবহারিক সমস্যাগুলির লক্ষ লক্ষ পরিবর্তনশীল রয়েছে (যেমন অপারেশন গবেষণা বা বৈদ্যুতিন নকশা অটোমেশন), এমনকি ও (এন3) অ্যালগরিদমগুলিও প্রায়শই অবাস্তব। একটি পৃথক বিবেচনা হল যে, সঠিক সমাধান খুঁজে না পেলে অনেক ক্ষেত্রেই প্রায়শই আনুমানিক সমাধান নিয়ে সন্তুষ্ট থাকে। উদাহরণস্বরূপ, ভ্রমণকারী বিক্রেতার সমস্যাটি বহুপদী সময়ে ঠিক সমাধানযোগ্য নয় বলে ব্যাপকভাবে সন্দেহ করা হয় (এটি এনপি-হার্ড), তবে ক্রিস্টোফাইডস অ্যালগরিদমের মতো পদ্ধতির সাহায্যে বহুপদী সময়ে ভাল সমাধান পাওয়া যেতে পারে। তথ্যসূত্র গণনামূলক জটিলতা তত্ত্ব