Оценка сложности песен

«Оценка сложности песен» () — статья, опубликованная теоретиком компьютерных наук Дональдом Кнутом в 1977 году, представляющая собой «шутку для посвящённых», связанную с теорией вычислительной сложности. Основной темой статьи является тенденция в эволюции популярной песни, связанная с переходом от длинных и наполненных содержанием баллад к текстам с высокой степенью повторяемости и малым (или вообще отсутствующим) осмысленным содержанием. В статье отмечается, что некоторые песни могут достичь уровня сложности, соответствующего формуле , где N  — число слов в песне.

Содержание статьи 
Кнут делает утверждение, согласно которому «наши далёкие предки изобрели концепцию припева», чтобы уменьшить пространственную сложность песен, которая становится важным фактором, когда необходимо запомнить большое число песен. Лемма 1 в статье устанавливает, что если длина песни обозначена N, то добавление припева уменьшает сложность песни до cN, где коэффициент c < 1.

Далее Кнут демонстрирует способ построения песен со сложностью O(), указывая, что этот подход «позже был улучшен шотландским фермером по имени С. Макдональд».

Ещё более сложный подход дают песни сложностью O(). Это класс песен, известный как «m бутылок пива на стене».

Наконец, в ходе XX века прогресс, стимулируемый тем фактом, что «распространение современных наркотиков привело к потребности в ещё меньшем использовании памяти», привёл к тому, что появились песни произвольной длины с пространственной сложностью O(1), например, песня, определяемая следующим рекуррентным соотношением:

 
  'That’s the way,'  'I like it,' ,  
  'uh huh,' 'uh huh'

Последующие исследования 
Профессор Курт Айземанн из университета Сан-Диего в письме в журнал Communications of the ACM делает дальнейшие улучшения последней, представлявшейся не подлежащей улучшению оценки, O(1). Он начинает с наблюдения, согласно которому в практических приложениях значение «скрытой константы» c в нотации «O» большого может иметь критическое значение, проводя грань между приемлемостью и неприемлемостью: например, значение константы 1080 приведёт к тому, что объём информации превысит ёмкость любого из известных науке средств хранения информации. Далее он отмечает, что уже в средневековой Европе была известна техника, с использованием которой текстовое содержание любой произвольной мелодии может быть описано рекуррентным соотношением , где , что даёт значение константы c, равное 2. Однако, как оказалось, другая культура достигла абсолютного нижнего предела сложности O(0)! Профессор Айземанн формулирует это следующим образом:

Когда путешественники с «Мейфлауэра» сошли на этот берег, коренные американцы, гордые своими достижениями в теории хранения и доступа к информации, сперва встретили незнакомцев полным молчанием. Это было средством донести их высшее достижение в сложности песен, а именно продемонстрировать, что низший предел c=0 действительно является достижимым.

Однако европейцы оказались неподготовленными к восприятию этого понятия, и индейские вожди, чтобы найти общую почву для передачи своих достижений, впоследствии продемонстрировали подход, описываемый рекуррентным соотношением , где , с субоптимальной сложностью, которую даёт значение c=1.

Примечания

Ссылки 
 «The Complexity of Songs», Knuth, Donald E. (1984).
 Перевод статьи .

Теория сложности вычислений
Теория музыки
Компьютерный юмор
Дональд Кнут
Произведения 1977 года
Научный юмор