PR (complexity)
پی آر تمام ابتدائی تکراری افعال کی پیچیدگی کی کلاس ہے-یا، مساوی طور پر، تمام رسمی زبانوں کا مجموعہ جس کا فیصلہ اس طرح کے فنکشن سے محدود وقت میں کیا جا سکتا ہے۔ اس میں اضافہ، ضرب، طول و عرض، ٹیٹریشن وغیرہ شامل ہیں۔ ایکر مین فنکشن ایک ایسی فنکشن کی مثال ہے جو ابتدائی تکراری نہیں ہے، جس سے یہ ظاہر ہوتا ہے کہ PR سختی سے R (کوپر 2004:88) میں موجود ہے۔ دوسری طرف، ہم کسی بھی بار بار شمار ہونے والے سیٹ کو (اس کی پیچیدگی کلاس RE کو بھی دیکھیں) ایک ابتدائی بار بار آنے والی فنکشن کے ذریعے درج ذیل معنوں میں "شمار" کر سکتے ہیں: ایک ان پٹ (M, k) دیا گیا ہے، جہاں M ایک ٹورنگ مشین ہے اور k ایک عدد ہے، اگر M k مراحل کے اندر رکتا ہے تو M آؤٹ پٹ کرتا ہے ؛ بصورت دیگر کچھ بھی آؤٹ پٹ نہیں کرتا ہے۔ پھر تمام ممکنہ ان پٹ (M، k) پر آؤٹ پٹ کا اتحاد بالکل M کا سیٹ ہے جو رکتا ہے۔ پی آر سختی سے عناصر پر مشتمل ہے۔ پی آر میں "پی آر مکمل" مسائل شامل نہیں ہوتے ہیں (یہ فرض کرتے ہوئے کہ، مثال کے طور پر، ELEMENTARY سے تعلق رکھنے والی کمی)۔ عملی طور پر، بہت سے مسائل جو پی آر میں نہیں ہیں لیکن صرف اس سے آگے ہیں-مکمل ہیں (شمٹز 2016)۔ حوالہ جات بیرونی لنکس۔ پیچیدگی کلاسیں