The Complexity of Songs Nikolaos Petros Triantafyllidis, AEM:1843 Theory of Computation The Complexity of Songs Concept proposed by Donald Knuth Published in 1977 on ACM SIGACT news. And in 1984 on ACM Communications In-Joke An attempt to determine the spatial complexity in the texts of songs • A fair attempt in being funny… • • • • • Donald Knuth • The father of Analysis of Algorithms • The Art of Computer Programming • TeX • Turing Award 1974 • Pretty badass… The Complexity of Songs • Computer Science concepts are applicable to areas that have nothing to do with computers • Popular songs in terms of modern Complexity Theory • Could try an information theory approach too but… • Big O…!!! • Missed it? The Complexity of Songs • A song of a length n usually requires a text of length ~n • Too many songs à Too Much text, No memory L • So our ancient ancestors invented refrain • Refrain provides a complexity of cn, c<1 • (wow) Lemma 1 • Let S be a song containing m verses of length V and a refrain of length R where the refrain is to be sung first, last, and between adjacent verses. Then, the space complexity of S is (V/(V + R)) n + O(1) for fixed V and R as mà+oo. PROOF • Some math follows… • The length of S when sung is n =R+(V+R)m (1) while its space complexity is c = R + Vm. (2) By the Distributive Law and the Commutative Law , we have c= n- (V+R)m + mV =n-Vm-Rm +Vm (3) =n-Rm. The lemma follows. The Complexity of Songs • Not bad but we can do better… • Jewish song “Ehad Mi Yode’a” • A cumulative song structure that produces a complexity of: O( n) • But we can go further down thanks to Mr. Old McDonald... Lemma 2 • Given positive integers a and X, there exists a song whose complexity is (20 + ! + " ) + n / (30 + 2 ! ) + !(1) PROOF PROOF (2) The Complexity of Songs • That was really pleasant but let’s leave some of the pleasure to the audience… • Other songs fall into that category too… That f*cker is (20 + ! + " ) + n / (30 + 2 ! ) + !(1) The Complexity of Songs • An improvement was proposed for a song with a complexity of O( 3 n) • Wrong definition, the actual complexity was O( n / log n) • Minor improvement but showed that the square root barrier could be broken The Complexity of Songs • Square root complexity is rather fine but can we go further? • Alcohol is always the solution… • Beer time! Theorem 1 • There exist songs of complexity O(log n). PROOF • Consider the schema Vk = TkBW’,’ TkB’;’ If one of those bottles should happen to fall, Tk-1BW’.’ where B = ‘bottles of beer’ W = ‘on the wall’ and where Tk is a translation of the integer k into English. PROOF (2) • It requires only O(m) space to define Tk for all k < 10m since we can define Tq*10m+r = Tq ’times 10 to the’ Tm ‘plus’ Tr , for 1 ≤ q ≤ 9 and 0 ≤ r ≤ 10m-1. (14) Therefore the songs Sk defined by So = ε, Sk = VkSk-1 for k ≥ 1 (15) have length n ≈ k log k, but the schema which defines them has length O(log k); the result follows. The Complexity of Songs • Logarithmic complexity is a charm but we can go even further • In Knuth’s own words: • “However, the advent of modern drugs has led to demands for still less memory, and the ultimate improvement of Theorem 1 has consequently just been announced” • (don’t do drugs) Theorem 2 • There exist arbitrarily long songs of complexity O(1). PROOF • (due to Casey and the Sunshine Band). Consider the songs Sk defined by (15), but with Vk = 'That's the way,' U 'I like it, ' U U = 'uh huh,' 'uh huh' The Complexity of Songs • Last remark on the paper: • It remains an open problem to study the complexity of nondeterministic songs. Applications • • • • • • • • Education (Introduction to Complexity Theory) Fun (for a rather special audience…) Songwriting schools Quantum computation Exploration of space Cosmology Human Cloning I am lying. Further Study • Prof Kurt Eisemann of San Diego State University has made some remarks about the impact of the hidden c constant. • Proposes an O(0) approach • "When the Mayflower voyagers first descended on these shores, the native Americans proud of their achievement in the theory of information storage and retrieval, at first welcomed the strangers with the complete silence. This was meant to convey their peak achievement in the complexity of songs, namely the demonstration that a limit as low as c = 0 is indeed obtainable." Further Further Study • I would propose another approach to achieve O(0) … • Numbers say that the most popular song on the planet for the current year comes from far in the east • Thus: Oppan Gangnam Style • You can’t speak Korean • Your audience can’t understand Korean • O(0)…! Furthest Study • What is the complexity of MUSIC? • Bearing in mind that it is largely a matter of definition • We might take a long shot in trying to get some insight on the complexities of musical information • An Information theory approach could be employed • Let’s define the musical pattern as the basic unit of information. The Complexity of Songs • Since the dawn of time musicians have devised tricks to help them organize their musical expression and reduce the amount of actual musical text that had to be memorized • Scales, Chords, Rhythms, Forms and a broad set of Empirical Rules/Traditions • These can be found in both folk/popular and art music of the western world. • So what makes a musical opus more or complex? • Personal estimate : The ability of the human ear (trained or not) to recognize patterns and connect them to a set of rules Popular Songs • Popular songs throughout the history of mankind vary dramatically but common patterns can be detected in large within the songs of the same period • Different songs of the same period can easily be reduced into the same class of songs that share the same ‘recipe’ that produces them. • Rather simple and easy listening forms and chord progressions • Since the era of J.S.Bach the western human ear has been tuned on the most simple cadences I-IV-I, I-V-I and the 4/4 time • Popular songs of the last half of the 20th century songs tend to converge into uniformity • Axis of Awesome – Four Chord Songs Blues/Folk Music Relied upon the experience of the musicians Largely improvised Traditions and forms are the main focus A lot to remember but the actual musical text to memorize is minimal • The same patterns occur in different songs and are rather easy to spot • • • • Minimal/Experimental/ Electronic Music • Patterns are extremely straight forward and recognizable • Repeated by machines in large extent • Thank you Tiesto you solved our problem! • Minimal classical music can have a pattern repeated for several minutes (or hours!) on a single instrument • But how complex are those patterns after all? Jazz • Totally Improvised • The set of rules is broader than that of classical music • The set of traditional songs performed over the decades is huge • The harmonies are complicated and difficult for the ear to grasp • The concept of entropy seems to take effect • Complexity hits a peak • Still produced by a recipe Classical Music Tons of dense musical information Technically challenging Years to master Kinda impossible to memorize the extent of the classical works • Rather easily explainable… • • • • Iannis Xenakis (math music) • Sounds like pure noise • Largely hated (sentenced to death by the greek government…….) • The amount of entropy is large • But it also has a set of rules that produces and explains it • Very formal. Very mathematical. Free Jazz/Free Impro No rules No Forms No Rehearsals between musicians No repetitive patterns The amount of entropy can make the listener eat their own liver • Do we have a winner? • • • • • Conclusions • People will always find ways to compress information • People will always find ways to make information non compressible • Diversity is complexity • Repetition is simplicity • Beauty can be found on either end • We can apply our knowledge on nearly anything • Computer Science rules! THANKS A TON! J

© Copyright 2018