Basit bir fikri asla küçümsemeyin çünkü bu fikirlerin bazen geniş kapsamlı etkileri olabilir. Böyle bir fikir için verilebilecek bir örnek, ilk olarak 1834’te Alman matematikçi Peter Gustav Lejeune Dirichlet (1805-1859) tarafından formüle edilen güvercin yuvası ilkesidir.
Eldeki bir kuşun çalıda iki kuştan daha değerli olduğu söylenir. Ancak bilgisayar bilimciler için bir deliği paylaşan iki kuş çok daha değerlidir. Çünkü bu durum, son derece basit gibi görünen ama oldukça derin anlamlar taşıyan matematiksel bir teoremin, güvercin yuvası ilkesi olarak bilinen kuralın temelini oluşturur.
Güvercin Yuvası İlkesi Nedir?
Bu ilke tek bir cümlede özetlenebilir: Altı güvercinin beş yuvaya yerleşmesi durumunda, en az iki güvercin aynı yuvayı paylaşmak zorundadır. İlke tamamen bundan ibarettir. Ancak bu ilke sadece kuşlarla ilgili değildir. Oldukça açık gibi görünse de, teorik bilgisayar biliminin temel amacına, yani farklı problemler arasındaki gizli bağlantıları haritalandırma çabasına güçlü bir katkı sağlar.
Güvercin yuvası ilkesi, nesnelerin kategorilere yerleştirildiği ve nesne sayısının kategori sayısını aştığı her durumda geçerlidir. Örneğin, 30.000 koltuk kapasiteli dolu bir futbol stadyumunda, bazı seyircilerin banka kartları için aynı dört haneli şifreyi (PIN) paylaşmak zorunda olduğu anlamına gelir.
Burada güvercinler futbolseverlerdir, yuvalar ise 0000’dan 9999’a kadar olan 10.000 farklı PIN seçeneğidir. Seçeneklerin sayısı insan sayısından az olduğu için, bazı şifreler kaçınılmaz olarak paylaşılır.
Güvercin Yuvası İlkesi Neden Önemlidir?
mutlaka bulunacaktır
Bu kanıtın dikkat çekici yanı yalnızca sadeliği değildir. Aynı zamanda neyi göstermediğidir. Matematikte çoğu ispat yöntemi “yapıcıdır”. Yani sadece bir şeyin var olduğunu göstermekle kalmaz. Aynı zamanda onu nasıl bulacağınızı da tarif eder.
Güvercin yuvası ilkesine dayanan ispatlar ise “yapıcı olmayan” türdendir. Stadyum örneğinde, bazı kişilerin aynı PIN’e sahip olduğunu bilsek de, kim olduklarını doğrudan belirleyemeyiz. Herkese sırayla sormak mümkündür, ama daha pratik bir yol var mıdır?
Bu tür sorular, bilgisayar biliminde “hesaplama karmaşıklığı teorisi” olarak bilinen alanın merkezindedir. Karmaşıklık kuramcıları, problemleri ortak özelliklerine göre sınıflandırarak inceler. Çoğu zaman ilerlemenin ilk adımı, daha önce birlikte ele alınmamış problemleri bir araya getiren yeni bir problem sınıfı tanımlamak olur.
1990’larda Papadimitriou ve diğer karmaşıklık teorisyenleri, çözümü güvercin yuvası ilkesi veya başka bir yapıcı olmayan ispatla garanti edilen yeni problem sınıflarını çalışmaya başladılar. Bu yaklaşım, kriptografiden algoritmik oyun teorisine kadar birçok bilgisayar bilimi alanında önemli gelişmelere yol açtı.
Papadimitriou, 2020 Ocak ayına geldiğinde, güvercin yuvası ilkesi üzerine otuz yıldır düşünüyordu. Bu yüzden sık görüştüğü bir meslektaşıyla yaptığı eğlenceli bir sohbet sırasında ilkeye küçük ama daha önce fark edilmemiş bir bakış açısıyla yaklaşmaları onu şaşırttı: Eğer güvercin sayısı yuva sayısından az olursa ne olur? Bu durumda bazı yuvaların boş kalacağı açıktır. Ancak bu ters çevirme, matematiksel olarak ilginç sonuçlar doğurur mu?
Güvercin Yuvası İlkesinin Tersi Boş Yuva İlkesi Nedir?
İlk bakışta, “boş yuva ilkesi” sanki özgün ilkenin başka bir şekilde söylenmesi gibi görünebilir. Ama değildir. Farklı doğası, onu hesaplama problemlerini sınıflandırmak için yeni ve verimli bir araç haline getirmiştir.
Boş yuva ilkesini anlamak için banka kartı örneğini küçük bir konser salonuna taşıyalım. Diyelim ki salon 3.000 koltuklu, bu da dört haneli PIN kombinasyonlarının sayısından (10.000) azdır. Boş yuva ilkesine göre, bazı PIN’ler salondaki hiç kimse tarafından kullanılmıyor olmalıdır. Ancak hangi PIN’lerin eksik olduğunu bulmak için herkese sormaktan daha iyi bir yol görünmemektedir. Şu ana kadar, boş yuva ilkesi özgün ilkeye çok benzemektedir.
Fark, çözümün doğrulanmasındaki zorlukta ortaya çıkar. Futbol stadyumu örneğinde, iki kişinin aynı PIN’e sahip olduğunu iddia eden biri varsa, sadece bu iki kişiye sorarak doğrulama yapabilirsiniz. Ancak konser salonunda, bir kişinin “hiç kimse 5926 PIN’ine sahip değil” dediğini düşünün. Bunu doğrulamak için herkese tek tek sormanız gerekir. Bu fark, boş yuva ilkesini karmaşıklık teorisyenleri için çok daha zorlayıcı hale getirir.
Boş Yuva İlkesi Ne İşe Yarayacak?
Papadimitriou, boş yuva ilkesini düşünmeye başladıktan iki ay sonra, bu konuyu bir doktora adayı ile yaptığı bir sohbette gündeme getirdi. Bu sohbeti özellikle hatırlıyor, çünkü Covid-19 karantinalarından önceki son yüz yüze görüşmesi olmuştu. Sonrasında evine kapanan Papadimitriou, problemin karmaşıklık teorisi üzerindeki etkileri üzerine yoğunlaştı. Sonunda, boş yuva ilkesi sayesinde çözüm garantisi olan arama problemleri üzerine bir makale yayımladı.
Geleneksel olarak karmaşıklık teorisinde kullanılan uzun kısaltma geleneğine uyarak, bu problem sınıfına “abundant polynomial empty-pigeonhole principle” ifadesinden türeyen APEPP adını verdiler.
Bu sınıftaki problemlerden biri, bilgisayar biliminin öncülerinden Claude Shannon’ın 70 yıl önce ortaya koyduğu ünlü bir ispatla bağlantılıdır. Shannon, hesaplama problemlerinin büyük kısmının doğası gereği çözülmesinin zor olduğunu göstermiştir. Bu sonuç, boş yuva ilkesinin temel fikrine dayanır, ancak Shannon bu ismi kullanmamıştır. Buna rağmen, bilgisayar bilimciler belirli bir problemin gerçekten zor olduğunu kanıtlamayı uzun yıllar boyunca başaramamışlardır.
Tarih boyunca, zor problemleri bulma süreci matematiksel bir arama problemi olarak ele alınmamıştı. Papadimitriou’nun yaklaşımı, bu süreci boş yuva ilkesine dayalı diğer arama problemleriyle birleştirerek yeni bir yöntem sundu. Bu yöntem karmaşıklık teorisini karmaşıklık teorisi kullanarak incelemek anlamına geliyordu.
Korten, Papadimitriou’nun pandemi öncesinde boş yuva ilkesi hakkında konuştuğu öğrenci adayıydı. Sonrasında Columbia Üniversitesi’ne geldi. İlk doktora yılında, zor problemleri aramanın APEPP sınıfındaki diğer tüm problemlerle yakından bağlantılı olduğunu ispatladı.
Matematiksel açıdan, bu tek problemde ilerleme kaydedilirse, bilgisayar bilimcilerin ve matematikçilerin uzun süredir çalıştığı birçok başka problemde de ilerleme sağlanacağı ortaya çıktı. Bunlar arasında, belirli basit alt yapıları olmayan ağları arama problemleri de bulunuyor.
Sonuç Olarak
Güvercin yuvası ilkesi, ilk bakışta açık gibi görünen ifadelerin bile matematikte büyük bir öneme sahip olabileceğini gösterir. Bu durum şaşırtıcı değildir. Çünkü matematiğin pek çok alanındaki çalışmalar, mümkün olduğunca basitleştirilmiş birkaç temel varsayıma dayanır. Sonuçta, basit sistemlerden son derece karmaşık sonuçlar ortaya çıkabilir.
Kaynaklar ve ileri okumalar:
- How a Problem About Pigeons Powers Complexity Theory. Yayınlanma tarihi: Kaynak iste: Quanta Magazine. Bağlantı: How a Problem About Pigeons Powers Complexity Theory
- Rittaud, B., Heeffer, A. The Pigeonhole Principle, Two Centuries Before Dirichlet. Math Intelligencer 36, 27–29 (2014). https://doi.org/10.1007/s00283-013-9389-1
- The World’s Simplest Theorem Shows That 8,000 People Globally. Have the Same Number of Hairs on Their Head. Yayınlanma tarihi: 20 mart 2023; bağlantı: The World’s Simplest Theorem Shows That 8,000 People Globally. Have the Same Number of Hairs on Their Head
Size Bir Mesajımız Var!
Matematiksel, matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
