The Complexity of Songs
"গানের জটিলতা" 1977 সালে কম্পিউটার বিজ্ঞানী ডোনাল্ড নুথের একটি পাণ্ডিত্যপূর্ণ নিবন্ধ, যা গণনামূলক জটিলতা তত্ত্ব সম্পর্কে একটি রসিকতা হিসাবে। নিবন্ধটি দীর্ঘ এবং বিষয়বস্তু সমৃদ্ধ ব্যালেড থেকে খুব কম বা কোনও অর্থবহ বিষয়বস্তু সহ অত্যন্ত পুনরাবৃত্তিমূলক গ্রন্থে পরিণত হওয়ার জনপ্রিয় গানের প্রবণতাকে পুঁজি করে। নিবন্ধটি উল্লেখ করেছে যে দৈর্ঘ্য এন শব্দের একটি গান মনে রেখে তৈরি করা যেতে পারে, উদাহরণস্বরূপ, শুধুমাত্র শব্দ (গানের "স্থান জটিলতা") বা তারও কম। নিবন্ধের সারসংক্ষেপ নুথ লিখেছেন যে গানের স্থান জটিলতা হ্রাস করার জন্য "আমাদের প্রাচীন পূর্বপুরুষরা বিরতির ধারণাটি উদ্ভাবন করেছিলেন", যা যখন একজনের স্মৃতিতে প্রচুর সংখ্যক গান প্রতিশ্রুতিবদ্ধ করতে হয় তখন তা অত্যন্ত গুরুত্বপূর্ণ হয়ে ওঠে। নুথের লেম্মা 1-এ বলা হয়েছে যে যদি এন একটি গানের দৈর্ঘ্য হয়, তবে বিরতিটি গানের জটিলতা সিএনএ-তে হ্রাস করে, যেখানে ফ্যাক্টর সি <1। নুথ আরও ও () জটিলতার সাথে গান তৈরির একটি উপায় প্রদর্শন করে, যা "ও ম্যাকডোনাল্ড নামে একজন স্কটিশ কৃষক দ্বারা আরও উন্নত"। আরও দক্ষ পদ্ধতির ফলে জটিলতার গান পাওয়া যায় ও (), একটি শ্রেণী যা "দেওয়ালে বিয়ারের এম বোতল" নামে পরিচিত। পরিশেষে, বিংশ শতাব্দীর অগ্রগতি-এই সত্য দ্বারা উদ্বুদ্ধ যে "আধুনিক ওষুধের আবির্ভাব এখনও কম স্মৃতির চাহিদার দিকে পরিচালিত করেছে"-চূড়ান্ত উন্নতির দিকে পরিচালিত করেঃ স্থান জটিলতা ও (1) সহ নির্বিচারে দীর্ঘ গান বিদ্যমান, যেমন। পুনরাবৃত্তির সম্পর্ক দ্বারা সংজ্ঞায়িত একটি গান 'এটাই উপায়', 'আমি এটি পছন্দ করি', সকলের জন্য 'উহ হু', 'উহ হু' আরও উন্নয়ন সান দিয়েগো স্টেট ইউনিভার্সিটির অধ্যাপক কার্ট আইসম্যান এসিএমের যোগাযোগে তাঁর চিঠিতে পরেরটি আপাতদৃষ্টিতে অপরাজেয় অনুমানকে আরও উন্নত করে। তিনি একটি পর্যবেক্ষণ দিয়ে শুরু করেন যে ব্যবহারিক প্রয়োগের জন্য বিগ ওহ স্বরলিপিতে "লুকানো ধ্রুবক" সি-এর মান সম্ভাব্যতা এবং অসম্ভবতার মধ্যে পার্থক্য করতে গুরুত্বপূর্ণ হতে পারেঃ উদাহরণস্বরূপ 1080-এর একটি ধ্রুবক মান যে কোনও পরিচিত যন্ত্রের ক্ষমতা অতিক্রম করবে। তিনি আরও লক্ষ্য করেছেন যে মধ্যযুগীয় ইউরোপে ইতিমধ্যে একটি কৌশল জানা গেছে যার মাধ্যমে একটি স্বেচ্ছাচারী সুরের পাঠ্য বিষয়বস্তু পুনরাবৃত্তির সম্পর্কের ভিত্তিতে রেকর্ড করা যেতে পারে, যেখানে, বড়-ওহ ধ্রুবক সি এর মান 2 এর সমান। তবে দেখা যাচ্ছে যে অন্য একটি সংস্কৃতি ও (0) এর পরম নিম্ন সীমা অর্জন করেছে। অধ্যাপক আইসম্যান যেমন বলেছেন, "যখন মেফ্লাওয়ার সমুদ্রযাত্রীরা প্রথম এই উপকূলে অবতরণ করেছিল, তখন স্থানীয় আমেরিকানরা তথ্য সঞ্চয় এবং পুনরুদ্ধারের তত্ত্বে তাদের কৃতিত্বের জন্য গর্বিত হয়েছিল, প্রথমে সম্পূর্ণ নীরবতার সাথে অপরিচিতদের স্বাগত জানিয়েছিল। এর উদ্দেশ্য ছিল গানের জটিলতায় তাদের শীর্ষ কৃতিত্ব প্রকাশ করা, অর্থাৎ সি = 0-এর মতো একটি সীমা প্রকৃতপক্ষে অর্জনযোগ্য। যাইহোক, ইউরোপীয়রা এই ধারণাটি বোঝার জন্য প্রস্তুত ছিল না এবং প্রধানরা, তাদের অর্জনগুলি জানানোর জন্য একটি সাধারণ ভিত্তি প্রতিষ্ঠার জন্য পরে পুনরাবৃত্ত সম্পর্ক দ্বারা বর্ণিত একটি পদ্ধতির প্রদর্শন করতে এগিয়ে যায়, যেখানে, সি = 1 দ্বারা প্রদত্ত একটি উপ-অনুকূল জটিলতা সহ। ও (1) স্থান জটিলতার ফলাফলটি গাই এল স্টিল, জুনিয়র দ্বারাও প্রয়োগ করা হয়েছিল, সম্ভবত নুথের নিবন্ধ দ্বারা চ্যালেঞ্জ করা হয়েছিল। ডঃ স্টিলের টেলনেট গানটি এক্সপোনেনশিয়াল রিকার্শনের উপর ভিত্তি করে একটি সম্পূর্ণ ভিন্ন অ্যালগরিদম ব্যবহার করেছে, যা টেলনেটের কিছু বাস্তবায়নের উপর একটি প্যারডি। দারাহ শাভে পরামর্শ দিয়েছিলেন যে মানব গানের জটিলতা বিশ্লেষণ শিক্ষার্থীদের জটিলতা তত্ত্ব শেখানোর জন্য একটি দরকারী শিক্ষামূলক যন্ত্র হতে পারে। অধ্যাপক অ্যালান শেরম্যানের "অন সুপারপোলিলোগারিদমিক সাবএক্সপোনেনশিয়াল ফাংশনস" নিবন্ধে লিখেছেন যে নুথের নিবন্ধটি একটি বিশেষ শ্রেণীর ফাংশন বিশ্লেষণের জন্য মৌলিক ছিল। রেফারেন্স বাহ্যিক লিঙ্ক "গানের জটিলতা", নুথ, ডোনাল্ড ই। (1984)। গণনামূলক জটিলতা তত্ত্ব সঙ্গীতের গণিত ইন-জোকস কম্পিউটার হাস্যরস ডোনাল্ড নুথ 1977 নথি কম্পিউটার বিজ্ঞান গবেষণাপত্র সঙ্গীত এবং হাস্যরস