The Complexity of Songs
"گانوں کی پیچیدگی" 1977 میں کمپیوٹر سائنسدان ڈونلڈ نوتھ کا ایک علمی مضمون ہے، جو کمپیوٹیشنل پیچیدگی کے نظریہ کے بارے میں ایک مذاق کے طور پر ہے۔ مضمون میں مقبول گانوں کے طویل اور مواد سے بھرپور گیتوں سے انتہائی بار بار دہرائے جانے والے متن میں منتقل ہونے کے رجحان کا فائدہ اٹھایا گیا ہے جس میں بہت کم یا کوئی بامعنی مواد نہیں ہے۔ مضمون میں نوٹ کیا گیا ہے کہ لمبائی N الفاظ کا گانا یاد رکھتے ہوئے تیار کیا جا سکتا ہے، مثال کے طور پر، صرف الفاظ (گانے کی "جگہ کی پیچیدگی") یا اس سے بھی کم۔ آرٹیکل کا خلاصہ نوتھ لکھتے ہیں کہ "ہمارے قدیم آباؤ اجداد نے گانوں کی جگہ کی پیچیدگی کو کم کرنے کے لیے باز رہنے کا تصور ایجاد کیا"، جو اس وقت اہم ہو جاتا ہے جب گانوں کی ایک بڑی تعداد کو کسی کی یادداشت کے لیے وقف کرنا ہوتا ہے۔ نوتھ کی لیما 1 میں کہا گیا ہے کہ اگر این کسی گانے کی لمبائی ہے، تو بازگشت گانے کی پیچیدگی کو سی این تک کم کر دیتی ہے، جہاں عنصر سی <1 ہے۔ نوتھ او () پیچیدگی کے ساتھ گانے تیار کرنے کے طریقے کا مزید مظاہرہ کرتا ہے، ایک نقطہ نظر "او میکڈونلڈ نامی ایک سکاٹش کسان کے ذریعہ مزید بہتر کیا گیا"۔ زیادہ ذہین طریقوں سے پیچیدگی O () کے گانے ملتے ہیں، ایک کلاس جسے "دیوار پر بیئر کی m بوتلیں" کہا جاتا ہے۔ آخر میں، 20 ویں صدی کے دوران پیش رفت-اس حقیقت سے حوصلہ افزائی ہوئی کہ "جدید منشیات کی آمد نے اب بھی کم میموری کے مطالبات کو جنم دیا ہے"-حتمی بہتری کی طرف لے جاتا ہے: خلائی پیچیدگی O (1) کے ساتھ من مانی طور پر لمبے گانے موجود ہیں، مثال کے طور پر۔ ایک گانا جس کی وضاحت تکرار کے تعلق سے کی گئی ہے 'یہ راستہ ہے،' 'مجھے یہ پسند ہے،'، سب کے لیے 'آہ ہا،' 'آہ ہا' مزید پیش رفت سان ڈیاگو اسٹیٹ یونیورسٹی کے پروفیسر کرٹ آئزمین نے کمیونیکیشنز آف اے سی ایم کو اپنے خط میں مؤخر الذکر بظاہر ناقابل شکست تخمینے کو مزید بہتر بنایا ہے۔ وہ اس مشاہدے سے شروع کرتے ہیں کہ عملی ایپلی کیشنز کے لیے بگ اوہ نوٹیشن میں "پوشیدہ مستقل" سی کی قیمت فزیبلٹی اور ناقابل عملیت کے درمیان فرق کرنے میں اہم ہو سکتی ہے: مثال کے طور پر 1080 کی مستقل قیمت کسی بھی معروف ڈیوائس کی صلاحیت سے تجاوز کر جائے گی۔ انہوں نے مزید نوٹ کیا کہ قرون وسطی کے یورپ میں ایک ایسی تکنیک پہلے ہی معلوم ہو چکی ہے جس کے تحت ایک صوابدیدی دھن کے متن کو تکرار کے تعلق کی بنیاد پر ریکارڈ کیا جا سکتا ہے، جہاں، بگ-اوہ مستقل c کی قیمت 2 کے برابر ہوتی ہے۔ تاہم یہ پتہ چلتا ہے کہ ایک اور ثقافت نے O (0) کی مطلق نچلی حد حاصل کی۔ جیسا کہ پروفیسر آئزمین کہتے ہیں: "جب مئی فلاور کے مسافر پہلی بار ان ساحلوں پر اترے تو مقامی امریکیوں کو معلومات کے ذخیرے اور بازیافت کے نظریہ میں اپنی کامیابی پر فخر تھا، سب سے پہلے اجنبیوں کا مکمل خاموشی کے ساتھ استقبال کیا۔ اس کا مقصد گانوں کی پیچیدگی میں ان کی چوٹی کی کامیابی کو ظاہر کرنا تھا، یعنی یہ مظاہرہ کہ c = 0 جتنی کم حد واقعی قابل حصول ہے۔ " تاہم یورپی اس تصور کو سمجھنے کے لیے تیار نہیں تھے، اور سرداروں نے، اپنی کامیابیوں کو پہنچانے کے لیے ایک مشترکہ بنیاد قائم کرنے کے لیے بعد میں بار بار تعلق کے ذریعے بیان کردہ نقطہ نظر کا مظاہرہ کرنے کے لیے آگے بڑھے، جہاں، c = 1 کے ذریعے دی گئی ذیلی پیچیدگی کے ساتھ۔ او (1) خلائی پیچیدگی کے نتیجے کو گائے ایل اسٹیل، جونیئر نے بھی نافذ کیا تھا، جسے شاید نوتھ کے مضمون نے چیلنج کیا تھا۔ ڈاکٹر اسٹیل کے ٹیل نیٹ سونگ میں ایک مکمل طور پر مختلف الگورتھم کا استعمال کیا گیا ہے جو ایکسپونینشیل ریکرشن پر مبنی ہے، جو ٹیل نیٹ کے کچھ نفاذ پر ایک پیروڈی ہے۔ درہ شاوی نے تجویز کیا کہ انسانی گانوں کا پیچیدگی کا تجزیہ طلباء کو پیچیدگی کا نظریہ سکھانے کے لیے ایک مفید تدریسی آلہ ہو سکتا ہے۔ پروفیسر ایلن شرمین کا مضمون "آن سپر پولی لوگرتھمک سب ایکسپونینشیل فنکشنز" لکھتا ہے کہ نوتھ کا مضمون افعال کی ایک خاص کلاس کے تجزیے کے لیے بنیادی تھا۔ حوالہ جات بیرونی روابط "گانوں کی پیچیدگی"، نوتھ، ڈونلڈ ای۔ (1984)۔ کمپیوٹیشنل پیچیدگی تھیوری موسیقی کی ریاضی ان جوکس کمپیوٹر مزاح ڈونلڈ نوتھ 1977 دستاویزات کمپیوٹر سائنس کے کاغذات موسیقی اور مزاح