Denkşekillilik Problemini Çözecek Algoritma Geliştirildi

Chicago Üniversitesi’nden matematikçi ve bilgisayar bilimci Macar asıllı Prof. László Babai, geçtiğimiz günlerde bilgisayar bilimleri camiasında heyecan yaratan bir açıklama yaptı: Çizge Denkşek..
Görsel Telif:

Chicago Üniversitesi’nden matematikçi ve bilgisayar bilimci Macar asıllı Prof. László Babai, geçtiğimiz günlerde bilgisayar bilimleri camiasında heyecan yaratan bir açıklama yaptı: Çizge Denkşekilliliği Problemi‘ni (İng. Graph Isomorphism Problem) çözen bir algoritma yani matematiksel bir reçete geliştirdiğini duyurdu. Çok biliniyor olmasa da, bu problemin çözülmesi ünlü Gezgin Satıcı Problemi’nin (İng. Traveling Salesmen Problem) çözülmesinden daha önemsiz değil. Yeni algoritma, bilgisayar bilimciler dışındaki insanların yaşamında şimdilik bir değişiklik yaratmayacak olsa bile bu gerçekten etkileyici bir başarı; çünkü bu alanda çalışan pek çok bilimci tarafından imkansız olduğu sanılıyordu.

Bilgisayar bilimleri temelde çok basittir. Bilgisayarın istenilen hesaplamayı yapmasını sağlamak demektir. Bir veritabanındaki kayıtları sıralayan algoritmanın geliştirilmesi yıllar önce büyük bir olay olarak algılanmıştı. Çünkü artık insanların elle bunu yapmak zorunda kalmayacağını müjdelemişti. Bununla beraber bazı istisnai hesaplamalar da vardır ki, bir bilgisayar için bunları çözmek çok zordur. Örneğin belli sayıda parametreye dayanarak bir seyyar satıcı için en iyi rotanın hangisi olacağını sormak gibi. Bilgisayarın bunu söyleyebilmesi için tüm seçenekleri teker teker denemesi gerekir. Birkaç uğrak yerinden ibaret olan rotalar için bunu becerebilse de, uğranacak yer sayısı yüzlerce ya da binlerce olduğunda, bilgisayarın çözebilmek için insan ömründen uzun zamana ihtiyacı olur.

Karmaşıklık kuramı alanında (bilgisayar kullanarak neyi çözmenin kolay, neyi çözmenin zor olduğunu araştıran alan) çalışan bilgisayar bilimciler, zaman içinde kolay ve basit algoritma hedefleri ile zor hatta imkansız görünenleri ayıracak bir etiketleme yöntemi geliştirdi. Nispeten kolay olanlar P (polinom zamanda çözülebilir anlamında) ile gösterilirken, zor olan diğerleri NP (nondeterministik polinomal anlamında) ile temsil edilmeye başlandı. İçlerinden en zorlarına da NP-tamam (NPC) kısaltması verildi. Hatta ünlü Simpsons TV dizisinin 1995 yılı Cadılar Bayramı bölümünde boyutlararası bir geçite giren Homer Simpson, yeşil ızgara çizgileri üzerinde uçuşan geometrik şekillerin ve denklemlerin arasında buluyordu kendini. Havada asılı duran eşitliklerden biri de, yanıltıcı biçimde basit görünen P=NP denklemiydi. Bu eşitlik muhtemelen kuramsal bilgisayar bilimi alanında üzerinde en çok tartışılan denklemdir. Zor görünen tüm denklemlerin aslında kolay bir yolu var mıdır, yok mudur? Bu sorunun genelleştirilmiş yanıtını bulana Clay Matematik Enstitüsü 1 milyon dolar vaad etmiş durumda.

Çizge denkşekilliliği problemi NP etiketi taşıyordu. NPC etiketi taşıması gerektiğini düşünen kişi sayısı da çoktu. Problem, iki farklı ağa (aralarında bağlantılar ve düğümler olan iki ağa) birden bakabilen bir algoritma yaratmayı gerektiriyordu. Bunları deneyecek ve aynı olup olmadıklarını söyleyecekti. Tabi ufak ağlar için oldukça basit görünen bu iş, karmaşıklık arttıkça içinden çıkılamaz hale geliyordu. Bu problemi çözmek için tüm olasılıkları deneyen değil, akıllıca bir yanıt arayan bir algoritma gerektiği açıktı. İşte Babai böyle bir algoritma yaratmayı başardığına inanıyor. Algoritmasının ne kadar karışık ve dolaşık olurlarsa olsunlar, iki farklı ağa bakıp, bunların aslında aynı olup olmadığını söyleyebildiğini belirtiyor. Massachusetts Teknoloji Enstitüsü’nden bilgisayar bilimci Scott Aaronson şu yorumu yapıyor: “Eğer bu doğruysa, muhtemelen kuramsal bilgisayar bilimi alanında son on yılda ulaşılan en önemli sonuçla karşı karşıyayız demektir.”

Babai’nin algoritması, karmaşıklık kuramcıları tarafından NP sınıfında olduğu düşünülen bir problemin sınıfını değiştirmesine neden olması bakımından dikkate değer bir buluş. P=NP denklemini genel anlamda kanıtlıyor olmasa da, doğruluğuna bir örnek teşkil etmesi açısından da heyecan verici. Ne yazık ki şu anda bu algoritmayı sınayabilecek bir algoritmamız yok ve bu nedenle gerçek bir başarı olarak kabul edilebilmesi için bu alanda çalışan diğer uzmanlar tarafından değerlendirilmesini bekliyoruz.

denksekillilik-problemini-cozecek-algoritma-gelistirildi-bilimfilicom

Çizge denkşekilliliği probleminde, görünüşte farklı iki çizgenin bu resimdeki gibi eşdeğer olacak biçimde düzenlenip düzenlenemeyeceği araştırılır.


Kaynaklar:

  • Phys.org, “Computer scientist claims to have solved the graph isomorphism problem”
    < http://phys.org/news/2015-11-scientist-graph-isomorphism-problem.html >
  • Sciencemag.org, “Mathematician claims breakthrough in complexity theory”
    < http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory >
  • Phys.org, “P vs. NP — The most notorious problem in theoretical computer science remains open”
    < http://phys.org/news/2009-10-p-np-notorious-problem.html >

Bu içerik BilimFili.com yazarı tarafından oluşturulmuştur. BilimFili.com`un belirtmiş olduğu “Kullanım İzinleri”ne bağlı kalmak kaydıyla kullanabilirsiniz.

Etiket
  • Projelerimizde bize destek olmak ister misiniz?
  • Dilediğiniz miktarda aylık veya tek seferlik bağış yapabilirsiniz.
  • Destek Ol
Yorum Yap (0 )

Yorum yapabilmek için giriş yapmalısınız.

Bunlar da ilginizi çekebilir

Bağış Yap, Destek Ol!
Projelerimizde bize destek olmak isterseniz,
Patreon üzerinden
bütçenizi zorlamayacak şekilde aylık veya tek seferlik bağışta bulunabilirsiniz.
E-Bülten Üyeliği
Duyurulardan e-posta ile
haberdar olmak istiyorum.
Reklam Reklam Ver
Arşiv