Addition-subtraction chain
ایک اضافی-گھٹاؤ سلسلہ، گھٹاؤ کو شامل کرنے کے لیے اضافی زنجیروں کی عمومی شکل، ایک ترتیب a0، a1، a2، a3 ہے۔ جو مطمئن کرتی ہے۔ لمبائی L کی n کے لیے ایک اضافی-گھٹاؤ سلسلہ، ایک اضافی-گھٹاؤ سلسلہ ہے۔ یعنی اس طرح کوئی بھی n کا حساب L کے اضافے اور/یا گھٹاؤ سے لگا سکتا ہے۔ (نوٹ کریں کہ n مثبت ہونا ضروری نہیں ہے۔ اس صورت میں، ترتیب میں a −1 = 0 بھی شامل کیا جا سکتا ہے، تاکہ n = −1 لمبائی 1 کی زنجیر سے حاصل کیا جا سکے۔) تعریف کے مطابق، ہر اضافی سلسلہ بھی ایک اضافی-گھٹاؤ سلسلہ ہے، لیکن اس کے برعکس نہیں۔ لہذا، n کے لیے مختصر ترین اضافہ-گھٹاؤ سلسلہ کی لمبائی اوپر n کے لیے مختصر ترین اضافہ سلسلہ کی لمبائی سے محدود ہے۔ تاہم، عام طور پر، کم سے کم اضافہ-گھٹاؤ سلسلہ کا تعین (جیسے کم سے کم اضافہ سلسلہ کا تعین کرنے کا مسئلہ) ایک مشکل مسئلہ ہے جس کے لیے فی الحال کوئی موثر الگورتھم معلوم نہیں ہے۔ زیادہ سے زیادہ اضافے کی ترتیب تلاش کرنے کا متعلقہ مسئلہ NP-مکمل (Downey et al., 1981) ہے، لیکن یہ یقینی طور پر معلوم نہیں ہے کہ آیا زیادہ سے زیادہ اضافے یا اضافے-گھٹاؤ کی زنجیروں کو تلاش کرنا NP-مشکل ہے۔ مثال کے طور پر، ایک اضافی-گھٹاؤ سلسلہ ہے:،،،۔ تاہم، یہ n = 3 کے لیے کم از کم اضافی-گھٹاؤ سلسلہ نہیں ہے، کیونکہ ہم اس کے بجائے انتخاب کر سکتے تھے۔ سب سے چھوٹا n جس کے لیے ایک اضافی-گھٹاؤ سلسلہ کم سے کم اضافی سلسلہ سے چھوٹا ہے، n = 31 ہے، جس کا حساب صرف 6 اضافے میں کیا جا سکتا ہے (کم سے کم اضافی سلسلہ کے لیے 7 کے بجائے): ایک اضافی سلسلہ کی طرح، ایک اضافی-گھٹاؤ سلسلہ بھی اضافی سلسلہ کے لیے استعمال کیا جا سکتا ہے: n کے لیے لمبائی L کے اضافی-گھٹاؤ سلسلے کو دیکھتے ہوئے، طاقت کا حساب x L اوقات سے ضرب یا تقسیم کر کے کیا جا سکتا ہے، جہاں گھٹاؤ تقسیم سے مطابقت رکھتے ہیں۔ یہ ممکنہ طور پر ان مسائل میں موثر ہے جہاں تقسیم ایک سستا عمل ہے، خاص طور پر الپٹک منحنی خطوط پر ایکسپونٹیشن کے لیے جہاں تقسیم محض علامت کی تبدیلی سے مطابقت رکھتی ہے (جیسا کہ مورین اور اولیووس نے تجویز کیا ہے، 1990)۔ کچھ ہارڈ ویئر ملٹی پلیئرز بائنری میں n کے ذریعہ بیان کردہ اضافی سلسلہ کا استعمال کرتے ہوئے n سے ضرب دیتے ہیں: n = 31 = 0 0 0 1 1 1 (بائنری)۔ دیگر ہارڈ ویئر ملٹی پلیئرز بوتھ انکوڈنگ میں n کے ذریعہ بیان کردہ اضافی-گھٹاؤ سلسلہ کا استعمال کرتے ہوئے n سے ضرب دیتے ہیں: n = 31 = 0 0 1 0 0 0 0 − 1 (بوتھ انکوڈنگ)۔ حوالہ جات کے اضافی سلسلے