PR (complexity)
পিআর হল সমস্ত আদিম পুনরাবৃত্তিমূলক ফাংশনের জটিলতা শ্রেণী-বা, সমতুল্যভাবে, সমস্ত আনুষ্ঠানিক ভাষার সেট যা এই ধরনের ফাংশন দ্বারা সীমাবদ্ধ সময়ে সিদ্ধান্ত নেওয়া যেতে পারে। এর মধ্যে যোগ, গুণ, সূচকীকরণ, টেট্রেশন ইত্যাদি অন্তর্ভুক্ত রয়েছে। একারম্যান ফাংশন এমন একটি ফাংশনের উদাহরণ যা আদিম পুনরাবৃত্তিমূলক নয়, যা দেখায় যে পিআর কঠোরভাবে আর (কুপার 2004:88)-এ রয়েছে। অন্যদিকে, আমরা নিম্নলিখিত অর্থে একটি আদিম-পুনরাবৃত্তিমূলক ফাংশন দ্বারা যে কোনও পুনরাবৃত্তিমূলক গণনাযোগ্য সেটকে (এর জটিলতা শ্রেণী আরই দেখুন) "গণনা" করতে পারিঃ একটি ইনপুট দেওয়া (এম, কে), যেখানে এম একটি টুরিং মেশিন এবং কে একটি পূর্ণসংখ্যা, যদি এম কে ধাপের মধ্যে থামে তবে আউটপুট এম; অন্যথায় আউটপুট কিছুই হয় না। তারপর সমস্ত সম্ভাব্য ইনপুটের (এম, কে) উপর আউটপুটগুলির মিলন হল ঠিক এম-এর সেট যা থেমে থাকে। পিআর কঠোরভাবে উপাদান ধারণ করে। পিআর-এ "পিআর-সম্পূর্ণ" সমস্যা থাকে না (যেমন, এলিমেন্টারির অন্তর্গত হ্রাসগুলি ধরে নেওয়া)। বাস্তবে, অনেক সমস্যা যা পিআর-এ নেই কিন্তু কেবল তার বাইরেও রয়েছে-সম্পূর্ণ (শ্মিটজ 2016)। তথ্যসূত্র বাহ্যিক লিঙ্ক। জটিলতার ক্লাস