Jack Edmonds: "Polinom Zaman" Kavramını Tanıtan ve Çiçek Algoritmasını Yazan Kanadalı

"Verimli algoritma" ne demek?

1960'ların başında bilgisayar bilimi henüz adını koymamıştı. Bilgisayarlar vardı, algoritmalar vardı, ama "iyi algoritma" tanımı yoktu. Bir algoritmayı "iyi" yapan ne? Çalışıyor olması mı? Az hata mı? Az hafıza mı?

Bir Kanadalı matematikçi — Jack Edmonds — 1965 yılında Canadian Journal of Mathematics'te 87 sayfalık bir makale yayımladı: "Paths, Trees, and Flowers". İçinde, bir cümle modern bilgisayar bilimi tarihini değiştirdi:

"Bir algoritmayı iyi sayalım, eğer çalışma süresi girişin boyutunda polinomla sınırlı ise."

Bu P sınıfının doğum belgesidir. "Verimli = polinom zaman" tezi. Bu tanım o kadar zarif ve verimli ki, modern bilgisayar bilimi karmaşıklık teorisi tamamen bu üzerine inşa edildi: P, NP, NP-tam, vs.

Felsefi netlik

Edmonds'un argümanı şuydu:

• Üstel zaman ($2^n$): pratikte yetersiz. $n = 50$ olunca evrenin yaşı yetmez.
• Polinom zaman ($n^k$): pratikte makul. Bilgisayar hızı arttıkça doğrusal ölçeklenir.

Yani algoritmik teori için doğru sınır üstel-polinom ikilemidir. Bu, hâlâ tüm bilgisayar biliminin temel paradigmasıdır.

İronik nokta: bazı polinom algoritmaları ($n^{100}$ gibi) pratikte berbat; bazı üstel algoritmalar ($1.001^n$ gibi) pratikte iyi. Ama asimptotik kategori olarak Edmonds'un ayrımı doğru çıktı — uzun vadede, polinom-üstel bölünmesi pratik etkili kategoriyi ayırıyor.

Erken yaşam

• Doğum: 5 Nisan 1934, Washington DC, ABD.
• Eğitim: Duke Üniversitesi (BS 1957), University of Maryland (MA 1960). PhD almadı — alışılmadık.
• İş: 1959'da National Bureau of Standards (ABD devlet matematik laboratuvarı), Washington.
• 1969: Kanada'ya, University of Waterloo'ya geçti. Hayatının geri kalanını orada geçirdi.

PhD'siz akademik kariyer 60'larda mümkündü; bugün neredeyse imkansız. Edmonds, derinden yetenekli olduğu için bu istisnayı yaşadı.

"Çiçek algoritması" (1965)

Edmonds'un teknik mucizesi: genel graflarda eşleştirme.

Bipartite (ikili) graflarda eşleştirme önceden çözülmüştü (Hopcroft-Karp, Ford-Fulkerson varyantı). Ama genel graflarda (tek kümeli) eşleştirme çok daha zordu — çünkü tek-uzunluklu döngüler (odd cycles) sorun yaratır.

Edmonds'un fikri: bir tek-döngüye rastlandığında onu tek bir süper-köşeye büz ("flower" → "blossom" — çiçek). Bu büzme adımı, eşleştirme arayışını basitleştirir. Çiçeğin içindeki yapı genişleyince geri açılır.

Bu algoritma $O(V^3)$ zamandan çalışır — polinom zaman. İlk genel graf eşleştirme polinom algoritması.

Pratik uygulamalar:

• Kidney exchange: organ uyum eşleştirmeleri.
• Hastane atama: hasta-yatak eşleştirme.
• Pazarlama: müşteri-ürün eşleştirme.

Edmonds-Karp algoritması (1972)

Richard Karp ile birlikte: max-flow için BFS arttırma yolu yöntemi. Karmaşıklık $O(VE^2)$. Önceki yazımızda gördük.

Matroid teorisi

Edmonds matroid kavramının modern teorisinin kurucularından. Matroidler soyut kombinatoryal yapılar — lineer cebir bağımsızlık kavramının soyutu. Modern matematik:

• Açgözlü algoritmalar ne zaman çalışır? Edmonds gösterdi: ⟺ yapı bir matroid.
• Edmonds matroid intersection algoritması: iki matroidin kesim eşleştirmesi.

Modern kombinatoryal optimizasyonun soyut katmanı.

Felsefi yazılar

Edmonds kombinatoryal optimizasyon felsefesi üzerine pek çok düşünce yazısı yazdı:

• "iyi karakterizasyon" kavramı: bir problemin "evet" cevabını ispatlamak için kısa kanıt (NP), "hayır" cevabını ispatlamak için de kısa kanıt (co-NP). Bunların kesişimi (NP ∩ co-NP) çoğunlukla polinom çözülür.
• Bu, Karp'ın 1972'de NP-tamlık kavramını formelleştirmesine zemin hazırladı.

Yani Edmonds felsefi yönden Karp'tan önce gelir; Karp da teknik yönden onu sistemleştirdi.

"Eğer ben size NP'nin P olmadığını ispat edersem..."

Edmonds P ≠ NP sanısının ilk savunucularındandır. 1966'da bir konuşmada şöyle dedi: "Bir 'iyi' algoritma yoksa, çoğu insanın bunu kanıtlamak için NP problemleri üzerine düşünmesi gerekecek." Bu, modern milenyum probleminin felsefi öngörüsüdür.

Akademik kariyer

• National Bureau of Standards (1959-69): yıllar boyunca George Dantzig, Alan Hoffman ile karşı taraf yarışlarda zaman geçirdi.
• University of Waterloo (1969-): bilgisayar bilimi kombinatoryal optimizasyon grubu kuruculuğu. Kanadalı bilgisayar bilimi tarihinin abidesi.
• Misafir profesörlükler: Berkeley, Bonn, Australian National University.

Ödüller

• John von Neumann Theory Prize (1985): operasyon araştırması ödülü.
• Killam Prize (1988): Kanada bilim ödülü.
• Royal Society of Canada üyesi.
• EATCS Award (2012): Avrupa Teorik Bilgisayar Bilimi Derneği.

Edmonds'un kişiliği

Edmonds dürüst, açık sözlü, dik fikirli bir adamdır. Birkaç akademik tartışmaya girdi:

• Algoritma karmaşıklığında "$O$" notasyonu kullanımı hakkında Knuth'la mektup tartışması.
• "Bipartite" yerine "bipartite-like" terimi tercih etmesi: küçük bir terminoloji savaşı.
• Modern derin öğrenmeye eleştirel yaklaşım: "polinom algoritmalar bizden bilim, deep learning bizden empiristik mühendislik gerektiriyor."

Bu özgün karakterli, bilim emin bir akademisyendir.

Mirası

• P sınıfı kavramı: modern karmaşıklık teorisinin temeli.
• Çiçek algoritması: genel graf eşleştirmesi.
• Edmonds-Karp: max-flow standardı.
• Matroid teorisi: kombinatoryal optimizasyonun soyut katmanı.
• NP ∩ co-NP karakterizasyonu: NP-tamlık öncülü.
• Felsefi etki: algoritmanın "iyi" tanımı.

90 yaşında, Edmonds hâlâ aktif — Waterloo'da makaleler yazıyor, konferanslarda konuşuyor.

Hayatı, bir kavramın gücünün örneği: "polinom zaman = verimli". Beş kelime, 60 yıl, milyonlarca öğrenci. Modern bilgisayar bilimi öğrencisi her gün — algoritma derslerinde, karmaşıklık derslerinde, optimizasyon derslerinde — Edmonds'un mirası ile karşılaşır.

Kanada'da, Waterloo Üniversitesi'nin tepelerinde yaşayan bu PhD'siz matematikçi, sessizce bilgisayar bilimi paradigmasını belirledi. "Çiçek" algoritmasında genel graf eşleştirmesini halletti, ama gerçek dehası felsefi sadelikti: "iyi algoritma = polinom algoritma."

Bu, bilim tarihinin en kısa ve etkili paradigma cümlesidir.