[Перевод] Как простая задача о голубях помогает математической теории сложности

Американцы говорят, что птица в руке стоит двух в кустах, но для компьютерных учёных две птицы в гнезде ещё лучше. А всё потому, что эти сожительствующие птицы являются героями обманчиво простой математической теоремы, называемой принципом голубятни. Её легко сформулировать в одном коротком предложении: если шесть голубей гнездятся в пяти гнёздах, то по крайней мере два из них должны жить в одном гнезде. Вот и всё.

«Принцип голубятни — это теорема, которая вызывает улыбку», — говорит Кристос Пападимитриу, учёный-теоретик из Колумбийского университета. «Это прекрасная тема для разговора».

Но принцип гнёзд подходит не только для птиц. Несмотря на то, что он звучит до боли просто, он стал мощным инструментом для исследователей, занимающихся центральным проектом теоретической информатики: составлением карты скрытых связей между различными задачами.

Читать далее