Para ilmuwan komputer berupaya mengetahui berapa banyak langkah yang diperlukan oleh suatu algoritma tertentu. Misalnya, algoritma lokal manapun yang dapat menyelesaikan masalah router dengan hanya dua warna pasti sangat tidak efisien, namun algoritma lokal yang sangat efisien dapat ditemukan jika penggunaan tiga warna diperbolehkan.
Dalam presentasi yang dihadiri Bernshteyn, pembicara membahas ambang batas ini untuk berbagai jenis masalah. Ia menyadari, salah satu ambang batas tersebut terdengar sangat mirip dengan ambang batas yang ada dalam dunia teori himpunan deskriptif—terkait jumlah warna yang diperlukan untuk mewarnai graf tak hingga tertentu dengan cara yang terukur.
Bagi Bernshteyn, ini terasa lebih dari sekadar kebetulan. Bukan hanya karena ilmuwan komputer juga ibarat pustakawan, yang mengelompokkan masalah berdasarkan efisiensi algoritmanya. Bukan pula hanya karena masalah-masalah ini juga dapat dirumuskan dalam bentuk graf dan pewarnaan.
Mungkin, pikirnya, kedua rak buku itu memiliki lebih banyak kesamaan. Mungkin hubungan antara kedua bidang ini jauh, jauh lebih dalam.
Mungkin semua buku, beserta rak-raknya, sebenarnya identik—hanya ditulis dalam bahasa yang berbeda dan memerlukan seorang penerjemah.
Membuka Pintu
Bernshteyn berusaha menjabarkan koneksi ini secara eksplisit. Ia ingin menunjukkan bahwa setiap algoritma lokal yang efisien dapat diubah menjadi metode pewarnaan graf tak hingga yang terukur-Lebesgue (dan memenuhi beberapa properti penting tambahan). Dengan kata lain, salah satu rak paling penting dalam ilmu komputer setara dengan salah satu rak terpenting dalam teori himpunan (yang berada di hierarki tinggi).
Ia memulai dengan kelas masalah jaringan dari kuliah ilmu komputer, berfokus pada aturan utamanya—bahwa algoritma pada suatu simpul hanya menggunakan informasi tentang lingkungan lokalnya, baik graf tersebut memiliki seribu atau satu miliar simpul.
Agar berjalan dengan benar, algoritma hanya perlu memberi label setiap simpul dalam lingkungan tertentu dengan nomor unik, sehingga dapat mencatat informasi tentang simpul terdekat dan memberikan instruksi. Hal ini cukup mudah dilakukan dalam graf hingga: Cukup beri setiap simpul dalam graf tersebut nomor yang berbeda.