Fagin's theorem
ফাগিনের উপপাদ্যটি বর্ণনামূলক জটিলতা তত্ত্বের প্রাচীনতম ফলাফল, গণনামূলক জটিলতা তত্ত্বের একটি শাখা যা সেই সমস্যাগুলি সমাধানের জন্য অ্যালগরিদমের আচরণের পরিবর্তে তাদের সমস্যার যুক্তি-ভিত্তিক বর্ণনার পরিপ্রেক্ষিতে জটিলতা শ্রেণীগুলিকে চিহ্নিত করে। উপপাদ্যটি বলে যে অস্তিত্বগত দ্বিতীয়-ক্রম যুক্তিতে প্রকাশযোগ্য সমস্ত বৈশিষ্ট্যের সেটটি সঠিকভাবে জটিলতা ক্লাস এনপি। 1973 সালে রোনাল্ড ফেগিন তাঁর ডক্টরাল থিসিসে এটি প্রমাণ করেছিলেন এবং তাঁর 1974 সালের গবেষণাপত্রে এটি প্রকাশিত হয়েছিল। দ্বিতীয়-ক্রমের সূত্র দ্বারা প্রয়োজনীয় যোগ্যতা উন্নত করা হয়েছিল (এক দিকে) এবং গ্র্যান্ডজিনের বেশ কয়েকটি ফলাফল অনির্ধারিত র্যান্ডম-অ্যাক্সেস মেশিনে আরও কঠোর সীমা প্রদান করেছে। প্রমাণ ফাগিনের 1974 সালের গবেষণাপত্র ছাড়াও, উপপাদ্যটির একটি বিস্তারিত প্রমাণ প্রদান করে। এটা দেখানো সোজা যে প্রতিটি অস্তিত্বগত দ্বিতীয়-ক্রমের সূত্রকে এনপিতে শনাক্ত করা যেতে পারে, সমস্ত অস্তিত্বগত-যোগ্য চলকের মান অনির্ধারিতভাবে বেছে নেওয়ার মাধ্যমে, তাই প্রমাণের মূল অংশটি দেখানো হয় যে এনপির প্রতিটি ভাষাকে একটি অস্তিত্বগত দ্বিতীয়-ক্রম সূত্র দ্বারা বর্ণনা করা যেতে পারে। এটি করার জন্য, নির্বিচারে একটি গণনার ট্যাবলো বেছে নেওয়ার জন্য দ্বিতীয়-ক্রমের অস্তিত্বগত পরিমাপ ব্যবহার করা যেতে পারে। আরও বিস্তারিতভাবে, একটি অনির্ধারিত টুরিং মেশিনের এক্সিকিউশন ট্রেসের প্রতিটি টাইমস্টেপের জন্য, এই ট্যাবলো টুরিং মেশিনের অবস্থা, টেপে এর অবস্থান, প্রতিটি টেপ সেলের বিষয়বস্তু এবং সেই ধাপে মেশিনটি কোন অনির্ধারিত পছন্দ করে তা এনকোড করে। একটি ফার্স্ট-অর্ডার সূত্র এই এনকোডেড তথ্যকে সীমাবদ্ধ করতে পারে যাতে এটি একটি বৈধ এক্সিকিউশন ট্রেস বর্ণনা করে, যেখানে টেপের বিষয়বস্তু এবং টুরিং মেশিনের অবস্থা এবং প্রতিটি টাইমস্টেপে অবস্থান পূর্ববর্তী টাইমস্টেপ থেকে অনুসরণ করে। প্রমাণটিতে ব্যবহৃত একটি মূল সূত্র হল যে, মহাবিশ্বের একটি সম্পর্ক হিসাবে দৈর্ঘ্যের একটি রৈখিক ক্রমকে (যেমন যে কোনও সময় ধাপে টাইমস্টেপ এবং টেপ বিষয়বস্তুর রৈখিক ক্রম) এনকোড করা সম্ভব। এটি অর্জনের একটি উপায় হল একটি রৈখিক ক্রম নির্বাচন করা এবং তারপরে সম্মানের সাথে এর অভিধানগত ক্রম হিসাবে সংজ্ঞায়িত করা।