Computational Complexity of Arranging Music

Erik D. Demaine, William S. Moses, Ron Graham

Research output: Chapter in Book/Report/Conference proceedingChapter


Music has long been an interesting subject of analysis for mathematicians and has led to many interesting questions in music theory and other fields. For the most part, computer scientists have looked into applying artificial intelligence to music [4] and finding algorithms and data structures to solve various musical problems. Prior work on these algorithms often involved computing various musical properties, such as the edit distance between two songs [5] or the optimal fingering [2]. These problems tend to be solvable in polynomial time using dynamic programming and have various applications, such as the music identification service Shazam [6] or
Original languageEnglish (US)
Title of host publicationThe Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity
EditorsJennifer Beineke, Jason Rosenhouse
PublisherPrinceton University Press
Number of pages15
ISBN (Electronic)9781400889136
ISBN (Print)9780691171920
StatePublished - Sep 2017
Externally publishedYes


Dive into the research topics of 'Computational Complexity of Arranging Music'. Together they form a unique fingerprint.

Cite this