Zor problemleri çözmenin en iyi yolu nedir? Bu, bilgisayar biliminin hesaplamalı karmaşıklık teorisi adı verilen bir alt alanının kalbinde yer alan sorudur. Cevaplaması zor bir soru ama ters çevirirseniz daha kolay hale gelir. En kötü yaklaşım neredeyse her zaman deneme yanılma yöntemidir; bu, olası çözümleri biri işe yarayana kadar denemeyi içerir. Ancak bazı problemler için hiçbir alternatif yok gibi görünüyor; en kötü yaklaşım aynı zamanda en iyisidir.

Araştırmacılar uzun zamandır durumun gerçekten böyle olup olmadığını merak ediyorlardı. Rahul IlangoMassachusetts Teknoloji Enstitüsü'nde karmaşıklık teorisi üzerine çalışan bir yüksek lisans öğrencisi. “'Tahmin et ve kontrol et' yönteminin en uygun olduğu problemler var mı?' diye sorabilirsiniz.”

Karmaşıklık teorisyenleri birçok hesaplama problemini incelediler ve en zor olanları bile çoğu zaman bir çözüm bulmayı saf deneme yanılmadan biraz daha kolaylaştıran bir tür akıllı prosedür veya algoritmayı kabul ediyor. Birkaç istisna arasında, amacın bir veri kümesinin en kısa tanımını bulmak olduğu sıkıştırma sorunları da vardır.

Ancak geçen Kasım ayında iki grup araştırmacı bağımsız keşfetti Sıkıştırma sorunlarına yönelik başka bir algoritma — tüm olası yanıtları kontrol etmekten biraz daha hızlı olan bir algoritma. Yeni yaklaşım, 25 yıl önce kriptograflar tarafından farklı bir soruna çözüm bulmak için icat edilen bir algoritmanın uyarlanmasıyla çalışıyor. Tek bir kısıtlama var: Algoritmayı veri kümenizin boyutuna göre uyarlamanız gerekiyor.

"Bunlar gerçekten çok güzel ve önemli sonuçlar" dedi Eric AllenRutgers Üniversitesi'nde teorik bilgisayar bilimcisi.

Sertliğin Tanımlanması

Yeni sonuçlar, karmaşıklık teorisinin ortaya çıkmasından çok önce Sovyetler Birliği'nde ilk kez çalışılan bir soruyu araştıran en son sonuçlardır. Allender, "Ben ilkokula başlamadan önce Rusya'daki insanlar bunu formüle ediyordu" dedi.

Sovyet araştırmacıların üzerinde çalıştığı minimum devre boyutu problemi olarak adlandırılan özel hesaplama problemi, bilgisayar donanımı tasarımcılarının her zaman karşılaştığı probleme benzer. Bir elektronik devrenin nasıl davranması gerektiğine ilişkin tüm özellikler size verilmişse, işi yapacak en basit devreyi bulabilir misiniz? Hiç kimse bu sorunun, kabaca "kapsamlı arama" anlamına gelen Rusça bir kelime olan "perebor" olmadan nasıl çözüleceğini bilmiyordu.

Minimum devre boyutu problemi, sıkıştırma problemine bir örnektir. Bir devrenin davranışını uzun bir bit dizisiyle (0'lar ve 1'ler) tanımlayabilir ve ardından aynı davranışı daha az bit kullanarak yeniden üretmenin bir yolu olup olmadığını sorabilirsiniz. Olası tüm devre düzenlerini kontrol etmek, dizideki bit sayısıyla birlikte katlanarak artan bir zaman alacaktır.

Bu tür üstel büyüme, zor bir hesaplama probleminin tanımlayıcı özelliğidir. Ancak tüm zor problemler eşit derecede zor değildir; çalışma süreleri hala katlanarak artmasına rağmen bazılarının kapsamlı aramadan daha hızlı algoritmaları vardır. Modern anlamda asıl soru, sıkıştırma sorunları için bu tür algoritmaların mevcut olup olmadığıdır.

1959'da Sergey Yablonsky adındaki önde gelen bir araştırmacı, kapsamlı aramanın gerçekten minimum devre boyutu sorununu çözmenin tek yolu olduğunu kanıtladığını iddia etti. Ancak kanıtı bazı boşluklar bıraktı. Bazı araştırmacılar o dönemde kusurları fark etmişti ancak Yablonsky diğerlerinin çoğunu perebor sorunu üzerinde çalışmaktan caydıracak kadar etkiliydi.

Takip eden yıllarda çok az araştırmacı sıkıştırma problemleri üzerinde çalıştı ve perebor sorusu çoğunlukla karmaşıklık teorisinin tarihöncesinde bir dipnot olarak biliniyordu. Araştırmacılar, sıkıştırma sorunları ile kriptografinin temelleri arasında ilginç bir bağlantı keşfettikten sonra, bu soruya büyük ilgi ancak yakın zamanda geldi.

Tek yönlü trafik

Modern kriptografi, gizli mesajları korumak için zorlu hesaplama problemlerini kullanır. Ancak hesaplama sertliği yalnızca asimetrikse faydalıdır; kodlanmış mesajları deşifre etmek zor ama ilk etapta mesajları kodlamak zor değilse.

Her kriptografi şemasında, bu asimetrinin kaynağı, giriş bit dizilerini aynı uzunluktaki çıkış dizelerine dönüştüren, tek yönlü fonksiyon adı verilen matematiksel bir nesnedir. Tek yönlü bir fonksiyona bir girdi verildiğinde, çıktıyı hesaplamak kolaydır, ancak bir çıktı verildiğinde, fonksiyonu tersine çevirmek, yani ona ters mühendislik uygulamak ve girdiyi kurtarmak zordur.

Allender, "Kriptograflar gerçekten çok çok verimli bir şekilde hesaplanabilen, tersine çevrilmesi gerçekten çok zor olan tek yönlü işlevlere sahip olmak istiyorlar" dedi. Pek çok matematiksel fonksiyon bu özelliğe sahip gibi görünmektedir ve bu fonksiyonları tersine çevirmenin zorluğu, farklı hesaplama problemlerini çözmenin görünürdeki zorluğundan kaynaklanmaktadır.

Ne yazık ki, kriptograflar bu işlevlerden herhangi birinin tersine çevrilmesinin gerçekten zor olup olmadığından emin değiller; aslında gerçek tek yönlü işlevlerin mevcut olmaması mümkündür. Bu belirsizlik devam ediyor çünkü karmaşıklık teorisyenleri 50 yıl boyunca mücadele etti Görünüşte zor olan sorunların aslında zor olduğunu kanıtlamak için. Eğer öyle değilse ve araştırmacılar bu problemler için süper hızlı algoritmalar keşfederlerse, bu, kriptografi için felaket olur; bu, hız yapan arabaların tek yönlü bir caddede aniden her iki yöne yönlendirilmesine benzer.

Her ne kadar hesaplama sertliğinin kapsamlı bir şekilde anlaşılması zor olsa da, kriptograflar son zamanlarda tek yönlü fonksiyonların birleşik teorisine doğru heyecan verici ilerlemeler kaydettiler. 2020'de büyük bir adım atıldı; Tel Aviv Üniversitesi kriptografı Rafael Geçidi ve onun yüksek lisans öğrencisi Yanyi Liu tek yönlü fonksiyonların olduğunu kanıtladı yakından bağlantılı zamana bağlı Kolmogorov karmaşıklık problemi adı verilen özel bir sıkıştırma problemine.

Eğer bu problemin çoğu girdi için çözülmesi gerçekten zorsa, Pass ve Liu'nun sonucu, kanıtlanabilir derecede zor bir tek yönlü fonksiyonun nasıl inşa edileceğine dair bir tarif verir; diğer hesaplama problemleri çok daha kolay ortaya çıksa bile güvenli olması garantidir. araştırmacıların beklediğinden daha fazla. Ancak zamanla sınırlı Kolmogorov karmaşıklık problemini çözecek hızlı bir algoritma varsa, o zaman kriptografi başarısızlığa mahkumdur ve herhangi bir fonksiyon kolaylıkla tersine çevrilebilir. Bu sorunun zorluğuna dayanan tek yönlü bir işlev, mümkün olan en güvenli işlevdir; hepsine hükmedecek tek yönlü bir işlev.

Veri Yapılarından Yararlanma

Pass ve Liu'nun keşfi, kriptografinin temellerini daha iyi anlamak için karmaşıklık teorisini kullanan uzun bir araştırma serisinin son bölümüydü. Ancak aynı zamanda bu ilişkiyi tersine çevirmenin bir yolunu da önerdi: Zamana bağlı Kolmogorov karmaşıklığı problemi ile fonksiyonun ters çevrilmesi arasındaki eşdeğerlik, her iki probleme ilişkin içgörülerin diğeri hakkında daha fazla bilgi verebileceğini ima ediyor. Kriptograflar, şifreleme yöntemlerinin zayıf noktalarını daha iyi anlamak için onlarca yıldır fonksiyon ters çevirme algoritmaları üzerinde çalışıyorlar. Araştırmacılar, bu algoritmaların karmaşıklık teorisindeki asırlık soruların yanıtlanmasına yardımcı olup olamayacağını merak etmeye başladı.

Birçok hesaplama probleminde olduğu gibi, fonksiyonun ters çevrilmesi de kapsamlı arama ile çözülebilir. Bir çıkış dizesi verildiğinde, doğru yanıtı vereni bulana kadar mümkün olan her girişi işleve takın.

1980'de kriptograf Martin Hellman daha iyisini yapmanın mümkün olup olmadığını araştırmaya başladı; Sovyet matematikçilerinin onlarca yıl önce sıkıştırma problemleri hakkında sordukları sorunun aynısı. Cehennem adamı keşfetti evet, bu mümkün - veri yapıları adı verilen matematiksel nesneleri kullanarak önceden fazladan biraz çalışma yapmaya istekli olduğunuz sürece.

Bir veri yapısı, esasen, tersine çevrilecek fonksiyon hakkındaki bilgileri saklayan bir tablodur ve bir tablonun oluşturulması, stratejik olarak seçilmiş belirli girdiler için fonksiyonun çıktılarının hesaplanmasını gerektirir. Tüm bu hesaplamaların "çok uzun zaman alabileceğini" söyledi Ryan WilliamsMIT'de karmaşıklık teorisyeni. “Ama fikir şu ki, bu bir kez, bir kez ve sonsuza dek yapılıyor.” Birçok farklı çıktı verildiğinde aynı işlevi tersine çevirmeye çalışıyorsanız (örneğin, aynı şekilde şifrelenmiş birçok farklı mesajın kodunu çözmek için), bu işi önceden yapmak faydalı olabilir.

Tabii ki, bu fazladan bilgiyi depolamak alan gerektirir, bu yüzden bu stratejiyi en uç noktalara taşırsanız, herhangi bir bilgisayara sığmayan hızlı bir programa sahip olabilirsiniz. Hellman, algoritmasının çoğu işlevi, çok fazla yer kaplamadan kapsamlı aramadan biraz daha hızlı tersine çevirmesine olanak tanıyan akıllı bir veri yapısı tasarladı. Daha sonra 2000 yılında kriptograflar Amos Fiat ve Moni Naor genişletilmiş Hellman'ın tüm işlevlere ilişkin argümanları.

Pass ve Liu'nun 2020'deki atılımından sonra, bu eski sonuçlar birdenbire yeniden gündeme geldi. Fiat-Naor algoritması, keyfi işlevleri kapsamlı aramadan daha hızlı tersine çevirebilir. Sıkıştırma sorunları için de işe yarayabilir mi?

Üniforma Dışı

Bu soruyu gündeme getiren ilk araştırmacılar karmaşıklık teorisyeniydi. Rahul Santhanam Oxford Üniversitesi'nden ve yüksek lisans öğrencisi Hanlin Ren. Bunu bir şekilde yaptılar 2021 kağıt sıkıştırma sorunlarının ve işlevin tersine çevrilmesinin araştırmacıların düşündüğünden daha da iç içe olduğunu kanıtladı.

Pass ve Liu, eğer zamanla sınırlı Kolmogorov karmaşıklığı problemi zorsa, o zaman fonksiyonun ters çevrilmesinin de zor olması gerektiğini (ve bunun tersinin de geçerli olduğunu) kanıtlamışlardı. Ancak sorunlar zor olabilir ve yine de kapsamlı aramalardan biraz daha iyi çözümlere izin verebilir. Santhanam ve Ren, bir problem için kapsamlı aramanın gerekli olup olmadığı ile diğeri için gerekli olup olmadığı arasında yakın bir bağlantı olduğunu gösterdi.

Sonuçları, araştırmacıların sıklıkla üzerinde çalıştığı, "tek tip" ve "tekdüze olmayan" algoritmalar olarak adlandırılan iki geniş algoritma sınıfı için farklı anlamlara sahipti. Tek tip algoritmalar her giriş için aynı prosedürü izler; örneğin sayı listelerini sıralamak için tek tip bir program, listede 20 giriş de olsa 20,000 giriş de olsa aynı şekilde çalışacaktır. Düzgün olmayan algoritmalar bunun yerine farklı uzunluktaki girişler için farklı prosedürler kullanır.

Fiat-Naor algoritmasının kullandığı veri yapıları her zaman belirli bir fonksiyona göre uyarlanır. 10 bitlik bir dizeyi karıştıran bir işlevi ters çevirmek için, karıştırma benzer şekilde yapılsa bile, 20 bitlik bir dizeyi karıştıran bir işlevi ters çevirmek için ihtiyaç duyacağınızdan farklı bir veri yapısına ihtiyacınız vardır. Bu da Fiat-Naor'u tekdüze olmayan bir algoritma haline getiriyor.

Santhanam ve Ren'in sonucu, Fiat-Naor algoritmasını sıkıştırma problemlerini çözecek bir algoritmaya dönüştürmenin mümkün olabileceğini öne sürdü. Ancak algoritmayı bir problemden diğerine uyarlamak kolay değildi ve soruyu daha fazla takip etmediler.

Pass, bir yıl sonra, Naor'un kriptografiye katkılarını kutlayan bir atölyede Fiat'ın klasik algoritma hakkında bir konuşmasını dinledikten sonra aynı fikre kapıldı. "Fonksiyon ters çevirmeyi kullanma fikri o zamandan beri aklımın bir köşesindeydi" dedi. Daha sonra Tel Aviv Üniversitesi araştırmacısıyla bu sorun üzerinde ciddi olarak çalışmaya başladı. Noam Mazor.

Bu arada Ilango, Berkeley, Kaliforniya'daki Simons Bilgisayar Teorisi Enstitüsü'nü ziyaret ederken Santhanam da dahil olmak üzere diğer araştırmacılarla yaptığı görüşmelerden sonra soruna saldırmak için ilham aldı. Santhanam, "Bu, bir şeyleri etrafa fırlattığınız çok tesadüfi konuşmalardan birinden ortaya çıktı" dedi. Ilango daha sonra Williams'la güçlerini birleştirdi ve Shuichi HiraharaTokyo'daki Ulusal Bilişim Enstitüsü'nde karmaşıklık teorisyeni.

İşin zor kısmı, Fiat-Naor algoritmasının kalbinde yer alan veri yapısının, sıkıştırma problemlerini çözmek için tek biçimli olmayan bir algoritmaya nasıl yerleştirileceğini bulmaktı. Bu tür bir yerleştirmenin standart bir prosedürü vardır, ancak bu, algoritmayı yavaşlatır ve kapsamlı aramaya göre avantajını ortadan kaldırır. İki ekip, Fiat-Naor veri yapısını birleştirmenin daha akıllı yollarını buldu ve sıkıştırma sorunları için tüm girdiler üzerinde çalışan ve kapsamlı aramadan daha hızlı kalan algoritmalar elde etti.

İki algoritmanın ayrıntıları biraz farklıdır. Ilango ve ortak yazarlarınınki, aramayı en basit olasılıklarla sınırlasanız bile kapsamlı aramadan daha hızlıdır ve tüm sıkıştırma sorunlarına (zaman sınırlı Kolmogorov karmaşıklığı, minimum devre boyutu sorunu ve diğerleri) uygulanır. Ancak temel fikir her iki algoritma için de aynıydı. Kriptografi teknikleri bu yeni alanda değerini kanıtlamıştı.

Ters Çevirme Yakınsaması

Tek biçimli olmayan algoritmalara ilişkin yeni kanıt, doğal bir soruyu gündeme getiriyor: Peki tek biçimli algoritmalar hakkında ne düşünüyorsunuz? Sıkıştırma sorunlarını bunları kullanarak kapsamlı arama yapmaktan daha hızlı çözmenin bir yolu var mı?

Son zamanlardaki sonuçlar dizisi, bu tür herhangi bir algoritmanın, kriptografların onlarca yıldır başarısız bir şekilde aradığı bir şey olan, keyfi işlevleri tersine çevirmek için tek tip bir algoritmaya eşdeğer olacağını ima ediyor. Bu nedenle birçok araştırmacı bu olasılığı pek olası görmüyor.

Santhanam, "Çok şaşırırdım" dedi. “Tamamen yeni bir fikir gerektirecektir.”

Ancak Allender, araştırmacıların bu olasılığı göz ardı etmemesi gerektiğini söyledi. "Benim için iyi çalışan bir hipotez şuydu: Bir şeyi yapmanın tek tip olmayan bir yolu varsa, büyük olasılıkla tek tip bir yol da vardır" dedi.

Her iki durumda da bu çalışma, karmaşıklık teorisyenlerinin kriptografideki eski sorulara yeni ilgi duymasını sağladı. Yuval İşhaiİsrail'in Hayfa şehrindeki Technion'da kriptograf olan kriptograf, olayı en heyecanlı kılan şeyin bu olduğunu söyledi.

"Farklı topluluklar arasındaki bu ilgi yakınlaşmasını görmekten gerçekten mutluyum" dedi. “Bunun bilim için harika olduğunu düşünüyorum.”