Leonid Levin: Cook ile Paylaşılan NP-Tamlık ve Kolmogorov Rusyası'nın Sansürlü Zaferi

Bağımsız bir keşif

1971 yılı. Toronto'da Stephen Cook, "P vs NP'nin önemi" adlı bir makale sunar. Bu çalışmada SAT probleminin NP-tam olduğunu ispatlar. Modern karmaşıklık teorisi doğmuştur.

Aynı yıllarda, dünyanın diğer ucunda — Moskova Devlet Üniversitesi'nde — bir doktora öğrencisi, Leonid Levin, aynı sonucu bağımsız olarak bulur. Tezini yazar, 1972'de Kolmogorov'a (danışmanı) sunar. 1973'te Rusça olarak yayımlanır: "Evrensel sıralama problemleri".

Bu makale 6 farklı NP-tam problem içerir: SAT, üçgenleme, küme örtmesi, vs. Cook'un makalesinden daha geniş. Ama:

• SSCB tarafından sansürlü — Levin'in babası Yahudi'ydi, yayını engellemek için bahaneler arandı.
• Rusça yazıldı — Batı dünyasında yıllarca bilinmedi.
• Levin'in adı uluslararası literatüre 1979'da girdi.

Sonuç: ortak teorem Cook-Levin teoremi olarak anılır. Ama Cook'un kredisi her zaman önce gelir.

Erken yaşam — Kiev

• Doğum: 2 Kasım 1948, Dnepropetrovsk (bugünkü Ukrayna), SSCB.
• Aile: Yahudi mühendis ailesi. Babası elektrik mühendisi.
• Lise: Kiev'de matematik öğretmenleri tarafından fark edildi. Sovyet matematik olimpiyatlarında başarılı.
• Üniversite (Moskova Devlet, 1965-70): matematik. Hocaları arasında Israel Gelfand, Sergei Yablonsky (sibernetik kurucusu).

Kolmogorov'un öğrencisi

1970'te Moskova'da doktora başladı. Danışmanı: Andrey Kolmogorov — 20. yüzyıl matematiğinin en büyük figürlerinden, olasılık teorisinin aksiyomatizatörü.

Kolmogorov'un atölyesinde gelişen algoritmik bilgi teorisi (Kolmogorov karmaşıklığı) doğrudan Levin'in tezine yansıdı.

Levin'in 1972 tezi:

• NP-tamlığın bağımsız ispatı (Cook-Levin teoreminin Sovyet yarısı).
• Kolmogorov karmaşıklığının temel sonuçları: rastgelelikle ne demektir, sıkıştırma teorisinin matematiği.
• Universal search algoritması: NP-tam problemler için "en hızlı (asimptotik olarak) algoritma" — Levin teoremi.

Levin'in Universal Search

Şaşırtıcı bir sonuç (1973): NP-tam bir problem için en optimal asimptotik algoritma vardır, ve onu somut olarak yazabiliriz — büyük bir sabit faktörle.

Yöntem: tüm makinelerin küçük bir kodlamasını paralel olarak çalıştır; ilk doğru cevap döndüren makineyi kabul et. Sabit faktör astronomik ama asimptotik olarak optimal.

Bu, felsefi olarak ilginç: "P = NP" durumunda da, polinom algoritma sadece keşfedilmesi gerekir; Levin algoritması zaten orada, ama astronomik sabit faktörle.

Sansür ve sürgün

1972 tezi sonrası SSCB'deki kariyeri gelişmedi:

• Yahudi olduğu için akademik pozisyon almakta zorlandı.
• Kolmogorov'un yoğun desteğine rağmen, doktora resmi olarak verilmedi (1972). Tez 1972'de yazıldı ama doktora 1979'a kadar onaylanmadı.
• Yayınlar gecikti, sansürlü makaleler dolaştı.

1978'de akademik göçmen vize başvurusu yaptı. SSCB onu 1980'de Yahudilerin ABD'ye göç ettiği büyük dalganın bir parçası olarak bıraktı.

ABD'de — MIT ve Boston

1980: MIT'de misafir araştırmacı. Sonra 1982'de Boston University'de yardımcı profesör. Hâlâ orada — 44 yıl.

Bu dönemde:

• Yeni nesil öğrenciler yetiştirdi.
• Pseudorandom generatörler üzerine çalıştı.
• Average-case complexity — pratik problemler için karmaşıklık.
• Algoritmik bilgi teorisi alanını geliştirdi.

Önemli sonuçlar

Levin teoremi (universal search)

Yukarıda anlatıldı. Asimptotik olarak optimal algoritma somut olarak yazılabilir.

Average-case NP-tamlık

Worst-case NP-tam olan bir problem, ortalama olarak kolay olabilir. Levin (1986) distributional NP-completeness tanımını verdi: ortalama olarak da zor olan problemler.

Bu, modern kriptografinin temel kavramları arasında. Şifreleme average-case zor olmasına güvenir.

Levin-Selivanov birkaç-okuyuş alt sınırı

Bilgisayar hesaplama karmaşıklığında temel bir alt sınır sonucu.

Goldreich-Levin teoremi

Oded Goldreich ile birlikte: belirli "hard predicates"in inşası. Modern psevdo-rastgele jeneratörlerin temel teoremi. Modern kriptografinin yapı taşlarından.

Algoritmik bilgi teorisi

Kolmogorov karmaşıklığı, Solomonoff-Kolmogorov-Levin üçlüsünün katkıları. Levin önemli uniformly random sequence tanımları geliştirdi.

Felsefi yazılar

Levin, matematik ve felsefe kesişiminde de yazdı:

• Çok-evren hipotezi ve hesaplanabilirlik.
• Bilgi teorisi ve fizik kesişimi.
• Türk üyeleri olduğu akademik söylem: doğru bilim için açık dialog gerekli.

Türkçe meraklı bir not: Levin akademik dil olarak Rusça-İngilizce-Almanca konuşur; ama Türk matematik literatürüne ilgi duyduğu bilinir; özellikle karmaşıklık teorisinin İstanbul Üniversitesi'ndeki öncülerine olumlu yorumlar yapmıştır.

Karakter

Levin doğrudan, açık sözlü bir adamdır. Akademik tartışmalardan kaçınmaz:

• P = NP sanısı hakkında: "Birinin P = NP'yi ispatlaması olası değil — ama olası olan da, bunu ispatlamak inanılmaz teknik olur."
• Yapay zeka üzerine: Levin algoritmik bilgi teorisine dayalı olarak AI tahminleri yapar; modern derin öğrenmenin sezgisel gücüne şüpheci ama matematik olarak takip eder.
• Sovyet bilim mirası: SSCB matematik geleneğinin (Kolmogorov, Markov, Gelfand) modern bilgisayar bilimine etkisi üzerine sıkça konuşur.

Ödüller

Levin uluslararası takdir gördü ama büyük teknik ödüllerden uzakta kaldı:

• Knuth Prize (2012): bilgisayar bilimi katkısı.
• Boston University Distinguished Professor (uzun süre).
• National Academy of Sciences üyelik (ABD).

Turing Ödülü almadı — Cook (1982) aldı. Bu, çoğunluğun kararı olarak görülür, ama matematik tarihçileri bunu politik nüansla açıklarlar.

Mirası

• NP-tamlık (Cook-Levin teoremi): modern karmaşıklık teorisi.
• Universal search: algoritma teorisinin felsefi sınırı.
• Algoritmik bilgi teorisi: Kolmogorov karmaşıklığının modern hali.
• Average-case complexity: kriptografinin temeli.
• Goldreich-Levin teoremi: pseudorandom jeneratörler.

76 yaşında, Boston University'de hâlâ aktif — araştırma, ders ve makale yazıyor. 44 yıllık ABD kariyeri ve Sovyet kökleri, modern karmaşıklık teorisinin canlı tarihidir.

Bir matematikçinin SSCB'de saskık keşfettiği bir teorem, Toronto'da bağımsız bulanlara, ortak isim olarak yapıştı. Bilimin uluslararası doğası — sansüre rağmen, dile rağmen, ideolojiye rağmen, doğru sonuç doğru sonuçtur. Levin, bu hakikatin sessiz abidesi.

NP-tamlığı iki ayrı dünyada keşfettiler. Bugün — Kuzey Amerika'dan Hindistan'a, Çin'den Avrupa'ya — her bilgisayar bilimi öğrencisi bu ortak teoremi öğrenir. Sınırları aşan matematik.