Christos Papadimitriou: Hesaplama Karmaşıklığının Yunan Yüzü

Bir bilim insanının matematik şenliği

Christos Papadimitriou (d. 1949, Atina) — modern teorik bilgisayar biliminin en popüler profesörlerinden, üç ciltlik karmaşıklık ders kitabı yazarı, neredeyse her büyük üniversitede ders vermiş.

Tek cümle: bilim insanlığını şenlik olarak yaşayan adam.

Yol

• Atina Polytechnic elektrik mühendisliği (1972).
• Princeton doktora (1976) — operasyonel araştırma.
• MIT, Harvard, Stanford, NTUA, UCSD, Berkeley, Columbia — çok geziyor!
• 1996-2018: UC Berkeley.
• 2018-: Columbia University.

Temel kitap: "Computational Complexity" (1994)

Modern karmaşıklık teorisinin referans kitabı. Lisansüstü standartı.

İçerik:

• Turing makineleri, P, NP, NP-complete.
• Uzay karmaşıklığı, PSPACE.
• Olasılıksal sınıflar (BPP, RP).
• Karmaşıklık hiyerarşisi.

Önce "Computers and Intractability" (Garey-Johnson 1979) vardı; Papadimitriou bunu modern teori ile birleştirdi.

PPAD sınıfı

2005 (Daskalakis ile): PPAD sınıfı tanımı.

PPAD = "Polynomial Parity Arguments on Directed graphs" — fixed point problemleri.

Önemli sonuç: Nash dengesi bulma PPAD-complete. Yani:

• Nash dengesi var diye biliyoruz (matematik kanıtı, 1950).
• Ama bulma muhtemelen $P$'de değil.

Bu, algoritmik oyun teorisinin temel sonucu.

"Algorithmic Game Theory" (2007)

Nisan, Roughgarden, Tardos, Vazirani ile editör. Modern algoritma + ekonomi kesişiminin standartı.

İçerik: Nash dengesi, mekanizma tasarımı, sosyal seçim, online algoritma.

"Logicomix" (2009)

Sürpriz: çizgi roman! Bertrand Russell'ın hayatını anlatır. Hem felsefi mantığın hem de modern matematik tarihinin görsel girişi.

Karısı (sanatçı) çizdi, Papadimitriou yazdı. Tüm dünyada satıldı.

"Algorithms" ders kitabı (2006)

Dasgupta, Vazirani ile. Üniversite algoritma dersi klasiği. CLRS'in daha kısa rakibi.

Türkçe çevirisi de var — Türk üniversiteleri kullanır.

Akademik etki

• Knuth Prize (2002) — TCS'nin Nobel'i.
• Gödel Prize (2012) — PPAD ve Nash kompleksitesi için.
• EATCS Award (2005).
• Member, US National Academy of Sciences.

Tarz

• Coşkulu öğretmen: ders kayıtlarında havadan dönen biri.
• Görsel hikaye anlatıcısı: Logicomix bunun göstergesi.
• Disiplin atlatıcı: TCS → oyun teorisi → biyoloji → felsefe.
• Yüksek üretkenlik: 300+ makale, 6 kitap.

"Mind-Brain" araştırması (2020s)

Son yıllarda: beyin nasıl bilgi işliyor? Sinir bilimi ile karmaşıklık teorisini birleştirme.

"Assembly calculus" — sinir hücrelerinin gruplar halinde nasıl hesapladığı.

Türkçe ve Yunan bağlantısı

• ODTÜ, Bilkent, Boğaziçi TCS derslerinde Papadimitriou ders kitabı kullanılır.
• Yunan bilim diyasporasının ABD'deki en görünür figürü.
• Türk ve Yunan akademisinin nadir "ortak hayranı".

"Algorithms her yerde" felsefesi

Papadimitriou'nun mesajı: algoritma sadece bilgisayar bilimi değil. Ekonomi, biyoloji, sinirbilim, sosyoloji — hepsi algoritmik düşünceyle yeniden yazılabilir.

Bu vizyon modern TCS'nin sınırını genişletti.

Kapanış

Christos Papadimitriou, kompleks teoriyi popüler kılan ve disiplinler arası köprü kuran nadir bilim insanlarından. Logicomix çizgi romanından PPAD teoremine, herkes için bir şey bulur. Hesaplama karmaşıklığının Yunan filozofu.