Low (computability)
کمپیوٹیبلٹی تھیوری میں، ٹورنگ ڈگری [X] کم ہوتی ہے اگر ٹورنگ جمپ [X′] 0′ ہو۔ ایک سیٹ کم ہوتا ہے اگر اس کی ڈگری کم ہو۔ چونکہ ہر سیٹ اس کی چھلانگ سے قابل حساب ہوتا ہے، کوئی بھی کم سیٹ 0′ میں قابل حساب ہوتا ہے، لیکن 0′ میں قابل حساب سیٹوں کی چھلانگ کسی بھی ڈگری کو 0′ (شین فیلڈ جمپ انورژن) میں قابل بار بار شمار کر سکتی ہے۔ ایکس کا کم ہونا کہتا ہے کہ اس کی چھلانگ X′ میں کسی سیٹ کی چھلانگ کے لیے ٹورنگ کی تخفیف کے لحاظ سے کم سے کم ممکنہ ڈگری ہے۔ کم ڈگریوں کے لیے مختلف متعلقہ خصوصیات ہیں: ایک ڈگری کو کم کیا جاتا ہے اگر اس کی n 'th چھلانگ 0 کی n' th چھلانگ ہو۔ ایک سیٹ X کو عام طور پر کم کیا جاتا ہے اگر یہ X′ ष्ण T X + 0′ کو مطمئن کرتا ہے، یعنی: اگر اس کی چھلانگ میں سب سے کم ڈگری ممکن ہو۔ ایک ڈگری d کو عام طور پر کم n کہا جاتا ہے اگر اس کی n 'th چھلانگ (n-1)' 0 'کے ساتھ d کے جوڑ کی پہلی چھلانگ ہے۔ زیادہ عام طور پر، سیٹوں کی خصوصیات جو ان کے کمپیوٹیشنل طور پر کمزور ہونے کی وضاحت کرتی ہیں (جب ٹورنگ اوریکل کے طور پر استعمال کیا جاتا ہے) کو چھتری کی اصطلاح لونیس پراپرٹیز کے تحت کہا جاتا ہے۔ جوکسچ اور سوارے کے لو بیس تھیوریم کے مطابق، کسی بھی نان ایمپٹی کلاس میں لو ڈگری کا ایک سیٹ ہوتا ہے۔ اس کا مطلب یہ ہے کہ، اگرچہ کم سیٹ کمپیوٹیشنل طور پر کمزور ہیں، پھر بھی وہ پیانو ریاضی کی تکمیل کا حساب لگانے جیسے کارنامے انجام دے سکتے ہیں۔ عملی طور پر، یہ تکرار نظریاتی تعمیرات کے لیے درکار اشیاء کی کمپیوٹیشنل طاقت پر پابندی کی اجازت دیتا ہے: مثال کے طور پر، وہ جو رمسی کے نظریہ کی پروف تھیوریٹک طاقت کا تجزیہ کرنے میں استعمال ہوتے ہیں۔ ہائی (کمپیوٹیبلٹی) لو بیسز تھیوریم حوالہ جات کمپیوٹیبلٹی تھیوری بھی دیکھیں۔