The Complexity of Songs
"பாடல்களின் சிக்கலானது" என்பது 1977 ஆம் ஆண்டில் கணினி விஞ்ஞானி டொனால்ட் க்னுத் எழுதிய ஒரு அறிவார்ந்த கட்டுரையாகும், இது கணக்கீட்டு சிக்கலான கோட்பாட்டைப் பற்றிய நகைச்சுவையாக உள்ளது. நீண்ட மற்றும் உள்ளடக்கம் நிறைந்த பாடல்களில் இருந்து குறைவான அல்லது அர்த்தமுள்ள உள்ளடக்கம் இல்லாத மிகவும் மீண்டும் மீண்டும் உரைகளுக்கு மாறும் பிரபலமான பாடல்களின் போக்கை இந்தக் கட்டுரை மூலதனமாக்குகிறது. N சொற்களின் நீளம் கொண்ட ஒரு பாடல் நினைவில் வைக்கப்படலாம், எ. கா., சொற்கள் மட்டுமே (பாடலின் "இட சிக்கலானது") அல்லது அதற்கும் குறைவாக இருக்கலாம் என்று கட்டுரை குறிப்பிடுகிறது. கட்டுரையின் சுருக்கம் க்னுத் எழுதுகிறார், பாடல்களின் இட சிக்கலைக் குறைக்க "நமது பண்டைய மூதாதையர்கள் விலகல் என்ற கருத்தை கண்டுபிடித்தனர்", இது ஒருவரின் நினைவகத்திற்கு அதிக எண்ணிக்கையிலான பாடல்களை அர்ப்பணிக்க வேண்டியிருக்கும் போது முக்கியமானது. க்னுத்தின் லெம்மா 1 கூறுகிறது, N என்பது ஒரு பாடலின் நீளம் என்றால், பாடல் சிக்கலை cN ஆகக் குறைக்கிறது, அங்கு காரணி c <1 ஆகும். க்னுத் மேலும் ஓ () சிக்கலான பாடல்களைத் தயாரிக்கும் வழியை நிரூபிக்கிறார், இது "ஓ. மெக்டொனால்ட் என்ற ஸ்காட்டிஷ் விவசாயியால் மேலும் மேம்படுத்தப்பட்டது". மேலும் புத்திசாலித்தனமான அணுகுமுறைகள் சிக்கலான O () பாடல்களைத் தருகின்றன, இது "சுவரில் m பாட்டில்கள் பீர்" என்று அழைக்கப்படும் ஒரு வகுப்பாகும். இறுதியாக, 20 ஆம் நூற்றாண்டின் முன்னேற்றம்-"நவீன மருந்துகளின் வருகை இன்னும் குறைவான நினைவாற்றலுக்கான தேவைகளுக்கு வழிவகுத்துள்ளது" என்ற உண்மையால் தூண்டப்பட்டது-இறுதி முன்னேற்றத்திற்கு வழிவகுக்கிறதுஃ இட சிக்கலான ஓ (1) உடன் தன்னிச்சையாக நீண்ட பாடல்கள் உள்ளன, எ. கா. மீண்டும் நிகழும் தொடர்பால் வரையறுக்கப்பட்ட ஒரு பாடல் 'அதுதான் வழி', 'எனக்கு இது பிடிக்கும்', அனைவருக்கும் 'உஹ் ஹஹ்', 'உஹ் ஹஹ்' மேலும் முன்னேற்றங்கள் சான் டியாகோ மாநில பல்கலைக்கழகத்தின் பேராசிரியர் கர்ட் ஐசமான் ஏசிஎம்மின் தகவல்தொடர்புகளுக்கு எழுதிய கடிதத்தில் பிந்தையது தோற்கடிக்க முடியாத மதிப்பீட்டை மேலும் மேம்படுத்துகிறது. நடைமுறை பயன்பாடுகளுக்கு பிக் ஓ குறியீட்டில் உள்ள "மறைக்கப்பட்ட மாறிலி" சி இன் மதிப்பு சாத்தியக்கூறு மற்றும் சாத்தியமற்ற தன்மைக்கு இடையிலான வேறுபாட்டைச் செய்வதில் முக்கியமானதாக இருக்கலாம் என்ற அவதானிப்புடன் அவர் தொடங்குகிறார்ஃ எடுத்துக்காட்டாக, 1080 இன் நிலையான மதிப்பு எந்தவொரு அறியப்பட்ட சாதனத்தின் திறனையும் தாண்டும். இடைக்கால ஐரோப்பாவில் ஏற்கனவே ஒரு நுட்பம் அறியப்பட்டிருப்பதை அவர் மேலும் கவனிக்கிறார், இதன் மூலம் ஒரு தன்னிச்சையான பாடலின் உரை உள்ளடக்கத்தை மீண்டும் நிகழும் உறவின் அடிப்படையில் பதிவு செய்யலாம், அங்கு, பெரிய-ஓ மாறிலி c இன் மதிப்பை 2 க்கு சமமாக வழங்குகிறது. இருப்பினும், மற்றொரு கலாச்சாரம் O (0) இன் முழுமையான கீழ் வரம்பை அடைந்தது என்று மாறிவிடும். பேராசிரியர் ஐசமான் கூறுவது போல்ஃ "மேஃப்ளவர் பயணிகள் முதன்முதலில் இந்த கரைகளில் இறங்கியபோது, பூர்வீக அமெரிக்கர்கள் தகவல் சேமிப்பு மற்றும் மீட்டெடுப்பு கோட்பாட்டில் தங்கள் சாதனையைப் பற்றி பெருமிதம் கொள்கிறார்கள், முதலில் அந்நியர்களை முழு மௌனத்துடன் வரவேற்றனர். இது பாடல்களின் சிக்கலான நிலையில் அவர்களின் உச்ச சாதனையை வெளிப்படுத்துவதாகும், அதாவது c = 0 போன்ற குறைந்த வரம்பு உண்மையில் பெறக்கூடியது என்பதை நிரூபிக்கிறது ". எவ்வாறாயினும், ஐரோப்பியர்கள் இந்த கருத்தைப் புரிந்துகொள்ளத் தயாராக இல்லை, மேலும் தலைவர்கள், தங்கள் சாதனைகளை வெளிப்படுத்த ஒரு பொதுவான அடித்தளத்தை நிறுவுவதற்காக பின்னர் தொடர்ச்சியான உறவால் விவரிக்கப்பட்ட ஒரு அணுகுமுறையை நிரூபிக்கத் தொடங்கினர், அங்கு, c = 1 ஆல் வழங்கப்பட்ட ஒரு துணை சிக்கலான சிக்கலுடன். ஓ (1) விண்வெளி சிக்கலான முடிவை கை எல். ஸ்டீல், ஜூனியர் என்பவராலும் செயல்படுத்தப்பட்டது, ஒருவேளை க்னுத்தின் கட்டுரையால் சவால் செய்யப்பட்டது. டாக்டர் ஸ்டீலின் TELNET பாடல் அதிவேக மறுநிகழ்வை அடிப்படையாகக் கொண்ட முற்றிலும் மாறுபட்ட வழிமுறையைப் பயன்படுத்தியது, இது TELNET இன் சில செயல்பாடுகளில் ஒரு பகடி. மனித பாடல்களின் சிக்கலான பகுப்பாய்வு மாணவர்களுக்கு சிக்கலான கோட்பாட்டை கற்பிப்பதற்கு ஒரு பயனுள்ள கற்பித்தல் சாதனமாக இருக்கும் என்று தர்ரா சாவே பரிந்துரைத்தார். பேராசிரியர் ஆலன் ஷெர்மன் எழுதிய "ஆன் சூப்பர்போலிலோகரிதமிக் சப்எக்ஸ்போனென்ஷியல் ஃபங்ஷன்ஸ்" என்ற கட்டுரை, க்னுத்தின் கட்டுரை ஒரு சிறப்பு வகை செயல்பாடுகளை பகுப்பாய்வு செய்வதற்கான அடிப்படை என்று எழுதுகிறது. குறிப்புகள் வெளிப்புற இணைப்புகள் "பாடல்களின் சிக்கலானது", க்னுத், டொனால்ட் ஈ. (1984). கம்ப்யூடேஷனல் சிக்கல் கோட்பாடு இசையின் கணிதம் நகைச்சுவையில் கணினி நகைச்சுவை டொனால்ட் க்னுத் 1977 ஆவணங்கள் கணினி அறிவியல் தாள்கள் இசை மற்றும் நகைச்சுவை