• 30 Yıldır Çözülemeyen Bilişim Varsayımı Çözüldü
43
8
5
2
0
Bilgisayar uzmanlarını yıllarca meşgul eden Boole fonksiyonunun hassasiyet konusuna bir çözüm getirildi. Hao Hung isimli bir profesör, yıllardır çözülemeyen soruya bir tweetlik bir cevap verdi.

Bu ay yayınlanan bir çalışma, bilgisayar devresi bloklarının temel yapısı hakkındaki yaklaşık 30 yıllık varsayımı sonuçlandırdı. Bu hassasiyet varsayımı, en yetkin bilgisayar profesörlerini yıllardır çaresiz bırakıyordu ancak ortaya çıkan yeni çözüm o kadar basitti ki tek bir tweet içerisinde anlatıldı.

Teksas Üniversitesi'nden Scott Aaronson, "Bu varsayım, teorik bilişim ve kombinasyon bilimlerindeki en karmaşık ve en utanç verici varsayım olarak biliniyordu. Dahası, bu varsayım üzerine araştırmalar yapıp başarısız olanların sayısı dahi bilinmiyor" şeklinde bir açıklama yaptı.

Bu varsayım, Boole fonksiyonunu temel alıyor. Boole fonksiyonuysa belirli sayıdaki girdileri (0'lar ve 1'ler) tek bir çıktıya dönüştürüyor. Bilgisayarlarda kullanılan tüm devreler de Boole fonksiyonunun bir kombinasyonu olarak karşımıza çıkıyor.

Yıllar ilerledikçe bilişim profesörleri bir Boole fonksiyonunun karmaşıklığını ölçebilecek yöntemleri ortaya çıkardı. Her ölçüm, girdinin nasıl bir çıktıya dönüştüğünü inceliyordu. Örneğin Boole fonksiyonunun (kabaca tabir etmek gerekirse) 'yolları'nın 'hassasiyeti', girdi bitinin çıktı bitini değiştirme ihtimalini hesaplıyor. Bunun yanı sıra 'sorgu karmaşası' da çıktıdan emin olmak için kaç adet girdi sorgulamanızı hesaplıyor.

varsayım

Her ölçüt, Boole fonksiyonunda nadir bir pencere sağlıyor ancak bilişim profesörleri, neredeyse tüm ölçütlerin tek bir çerçeveye uyduğunu, bu yüzden herhangi birinin değerinin diğer değerlerle aşağı yukarı benzediğini belirtti. Yalnızca bir karmaşıklık ölçütü uymuyordu; o da hassasiyetti.

1992 yılında Noam Nisan ve Mario Szegedy, 'hassasiyet'in bu çerçeveye uymadığını ileri sürdü. Bu da Boole fonksiyonu araştırmaları için müthiş bir varsayım halini aldı.

Emory Üniversitesi'ndeki matematikçi Hao Hung ise hassasiyet varsayımının küpün köşelerinin kombinasyonuyla ilgili olduğunu anlatan iki sayfalık dahice ancak son derece basit bir araştırma yayınladı.

fonksiyon

Fransız Ulusal Bilimsel Araştırma Merkezi'nden Claire Mathieu, Boole fonksiyonunu anlatırken bir banka senaryosunu örnek verdi. Bir krediye başvurulduğunu öne süren Mathieu, evet/hayır cevaplı soruların düşünülmesini söyledi. Test bittiğindeyse bankacı sonuçları hesaplayıp kişinin krediye uygun olup olmadığını belirtecekti. Bu işlem Boole fonksiyonunun bir örneğini oluşturuyordu. Cevaplarınız girdilerdi ve bankacının cevabıysa çıktıydı.

Başvurunuz reddedildiği zaman bazı verdiğiniz cevaplarda yalan söylemeniz durumunda krediyi alıp alamayacağınızı merak edebilirsiniz. Vereceğiniz cevap sonucunda çıktınızın değişme olasılığı varsa bilişim uzmanları Boole fonksiyonunun o özel soruya 'hassas' olduğunu belirtiyor. Eğer verdiğiniz cevapların yedi tanesini değiştirdiğinizde çıktınız değişikliğe uğruyorsa Boole fonksiyonunuzun hassasiyeti yedi oluyor.

Tabii ki hassasiyet, yalnızca tek bir ölçüt. Başka bir deyişle çok daha farklı değişkenler fonksiyon içerisinde yer alıyor. Örneğin size bir test verilmesi yerine bankacı size bizzat sorular sorabilir ve verdiğiniz cevaplara göre soruların sırasını değiştirebilir. Bankacının bir karar verebilmesi için sorması gereken maksimum soru sayısıysa Boole fonksiyonunun sorgu karmaşası olarak biliniyor.

matematik

Bu konsepti ilk kez 2012 yılında duyan Hung, konseptin basitliği ve zarafetine hayran kaldığını belirtti. Bunun üzerine bir çözüm üreten Hung, çözümünü bir tweette ve internet sayfasında paylaştı. Çözüm o kadar basitti ki, çözümün tüm profesörlere tek bir ders içerisinde anlatılabileceğini söyledi. Sorunun çözümü de onlarca yıldır süregelen tartışmalara bir son verdi.

Araştırmanın tam haline ulaşmak için bağlantıya tıklayabilirsiniz.

Kaynak : https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/
43
8
5
2
0
Emoji İle Tepki Ver
43
8
5
2
0