Bilgisayar Devresi Temel Yapı Taşları Hakkında Varsayım Çözüldü

Bu ay çevrimiçi olarak yayınlanan makale, bilgisayar devrelerinin temel yapı taşlarının yapısı hakkında yaklaşık 30 yıllık bir varsayımı çözdü. Bu “duyarlılık” varsayımı, yıllar içinde en önde gelen bilgisayar bilimcilerinin çoğunu şaşırttı, ancak yeni kanıt o kadar basit ki, bir araştırmacı bunu bir yazıda özetledi. tek tweet. 

 Austin, Texas Üniversitesi’nden Scott Aaronson bir blog yazısında, “Bu varsayım, tüm kombinatorik ve teorik bilgisayar bilimlerindeki en sinir bozucu ve utanç verici açık problemlerden biri olarak duruyor” diye yazdı. Bir e-postada, “Bunu çözmeye çalışan ve başarısız olan kişilerin listesi, ayrık matematik ve teorik bilgisayar biliminin kim olduğu gibidir,” diye ekledi. 

Tahmin, Boole fonksiyonlarıyla, bir dizi giriş biti (0s ve 1s) tek bir çıkış bitine dönüştürmek için kurallarla ilgilidir. Bu tür bir kural, giriş bitlerinden herhangi birinin 1 olması koşuluyla 1, aksi takdirde 0 çıkmasıdır; başka bir kural, dizenin 1 sayısı çiftse 0, aksi takdirde 1 çıktısını almaktır. Columbia Üniversitesi’nden Rocco Servedio, her bilgisayar devresi, Boole işlevlerinin bir kombinasyonudur ve onları “bilgisayar biliminde yaptığınız her şeyin tuğlaları ve harcı” yapar. 

 Yıllar içinde, bilgisayar bilimcileri belirli bir Boole fonksiyonunun karmaşıklığını ölçmek için birçok yol geliştirdiler. Her ölçü, girdi dizisindeki bilginin çıktı bitini nasıl belirlediğinin farklı bir yönünü yakalar. Örneğin, bir Boole işlevinin “duyarlılığı”, kabaca konuşursak, tek bir giriş bitini çevirmenin çıkış bitini değiştirme olasılığını izler. Ve “sorgu karmaşıklığı”, çıktıdan emin olmadan önce kaç tane giriş biti sormanız gerektiğini hesaplar.

Bilgisayar
Bilgisayar Devreleri

 Her ölçü, Boole işlevinin yapısına benzersiz bir pencere sağlar. Yine de bilgisayar bilimcileri, bu ölçülerin neredeyse tamamının birleşik bir çerçeveye oturduğunu, dolayısıyla herhangi birinin değerinin diğerlerinin değeri için kaba bir ölçü olduğunu bulmuşlardır. Yalnızca bir karmaşıklık ölçüsü uymadı: duyarlılık. 

1992’de, Kudüs İbrani Üniversitesi’nden Noam Nisan ve şimdi Rutgers Üniversitesi’nden Mario Szegedy, duyarlılığın gerçekten de bu çerçeveye uyduğunu tahmin ettiler. Ama kimse kanıtlayamazdı. Servedio, “Bu, muhtemelen Boole fonksiyonlarının çalışmasında göze çarpan açık soruydu” dedi. 

Carnegie Mellon Üniversitesi’nden Ryan O’Donnell, “İnsanlar en küçük ilerlemeyi sağlamaya çalışan uzun, karmaşık makaleler yazdılar” dedi. 

Şimdi, Emory Üniversitesi’nde matematikçi olan Hao Huang, küpler üzerindeki noktaların birleştiricileri hakkında ustaca ama basit iki sayfalık bir argümanla duyarlılık varsayımını kanıtladı. Fransa Ulusal Bilimsel Araştırma Merkezi’nden Claire Mathieu, bir Skype röportajı sırasında “Değerli bir inci gibi çok güzel” diye yazdı. 

Aaronson ve O’Donnell, Paul Erdős’in Tanrı’nın her teoremin mükemmel kanıtını yazdığı göksel bir kitap kavramına atıfta bulunarak, Huang’ın makalesini duyarlılık varsayımının “kitap” kanıtı olarak adlandırdılar. Aaronson, “Tanrı’nın bile Duyarlılık Sanısını bundan daha basit bir şekilde nasıl kanıtlayacağını bildiğini hayal etmekte zorlanıyorum,” diye yazdı. 

Mathieu, bir banka kredisi başvurusunda bir dizi evet/hayır sorusu doldurduğunuzu hayal edin. İşiniz bittiğinde, bankacı sonuçlarınızı puanlayacak ve size kredi almaya uygun olup olmadığınızı söyleyecektir. Bu süreç bir Boole işlevidir: Cevaplarınız giriş bitleridir ve bankacının kararı çıkış bitidir. 

Başvurunuz reddedilirse, tek bir soruya yalan söyleyerek sonucu değiştirip değiştiremeyeceğinizi merak edebilirsiniz – belki de gerçekten kazanmadığınız halde 50.000 dolardan fazla kazandığınızı iddia ederek. Bu yalan sonucu tersine çevirmiş olsaydı, bilgisayar bilimcileri Boole işlevinin o belirli bitin değerine “duyarlı” olduğunu söylüyorlar. Diyelim ki, her biri ayrı ayrı sonucu tersine çevirebilecek, söyleyebileceğiniz yedi farklı yalan varsa, o zaman kredi profiliniz için Boole fonksiyonunun duyarlılığı yedidir. 

Bu yazımız hakkındaki düşüncelerinizi yorumlarda bekliyoruz! 🙂

Yorum yapın