P ile NP Birbirine Eşit midir? Bu Ne Demektir?

“Biri bana öyle bir program yazsın ki, bu prog­ram, 1’den 50’ye kadar olan sayıların kareköklerini iki kümeye ayırsın. Bu iki kümedeki kareköklerin toplamları birbirine olabildiğince yakın olsun. Donald Knuth tarafından sorulan bu soru aslında fazla zor gözükmüyor değil mi? Sonuçta yapmamız gereken elli karekökü iki kümeye ayırmak. 1’in karekökü olan 1’i kümelerden birine koyarsak, ge­riye kalan 49 sayıyı o iki kümeye dağıtmamız la­zım. Ancak, Knuth’un bizden bir isteği daha var: Program en fazla 10 saniyede yanıtı versin. Şimdi burada duralım! Bu soru hem de çok zor.

50 sayı iki kümeye 249 biçimde ayrılabilir. Bilgisayarımıza tüm bu 249 se­çeneği teker teker denetiriz, kümelerdeki sayıları toplarız, farklarını alırız, farkları bir kenara yaza­rız, sonra en küçük farkı seçeriz. Ama belirlenen zaman diliminde bunu yapmak neredeyse imkansızdır. Bu türden problemler karmaşıklık kuramında “NP” olarak adlandırılır. Gizemli bir görünümü olan “P ile NP eşit midir?” sorusu ise, bilgisayar biliminin matematikle buluştuğu yerde ortaya çıkmış bir problemdir. Bu problem aynı zamanda 21. yüzyılın hayati problemlerinden biridir. Çünkü bilgisayar güvenliği açısından önemli sonuçları vardır.

P Nedir?

Bilgisayarlar algoritmalarla çalışır. Ancak bazı algoritmaları gerçekleştirmek sadece mikro saniyeler alırken, bazılarını gerçekleştirmek bugünkü hızla bile milyarlarca yıl alır. Burada kilit fikir, bir algoritmanın verimliliğidir. Şimdi basit bir algoritma düşünelim. Söz gelimi 5, 3, 4, 2, 1 sayılarını bilgisayarımız bir sıraya dizsin. Bunun için kullanılan yöntem “balon” ayıklama diye tabir edilen bir algoritmadır. Mantık oldukça basit. Ardışık sayı çiftlerini sistematik bir biçimde tara, biri diğerinden büyükse yerlerini değiştir, sıralamaları doğruysa dokunma.

Bilgisayar 5,3,4,2,1 dizisini ilk taradığında önce 5 ile 3’ün yerini değiştirir; böylece dizi 3,5,4,2,1 haline gelir. Bilgisayar ikinci çifte bakar, 5 ile 4’ün yerini değiştirir ve işlem böylece devam eder. Bilgisayarın doğru sıralamaya ulaşmak için on karşılaştırma yapması gerekir. Bunu genişletip elimizde dizilmesi gereken n sayı olduğunda, yapılan karşılaştırmaları da aynı biçimde sayabileceğimizi söyleyebiliriz. Gerekli adımların bir sınırı olacaktır; n2‘den kesinlikle az sayıda olacaktır bu adımlar…

Adım sayısının n’in bir kuvveti gibi olduğu bir algoritmanın “polinom” zamanda çözüleceği söylenir. Bilgisayarlar bu tür problemleri kolayca halleder. Bu algoritmalar da verimli algoritmalardır. Verilen iki sayının en küçük ortak katını bulma, bir sayının asal olup olmadığını sap­tama, dört işlem aritmetik hesapları P sınıfındaki problemlerdir.

Görsel Kaynak: https://www.youtube.com/

NP Nedir?

Şimdi NP problemlerini anlamaya çalışalım. Yazının başında verdiğimiz örnek bir NP problemi idi. Ne yapay, ne de doğal zeka, bazı problemlere makul bir zamanda cevap veremez. Diyelim ki size bir ülkedeki tüm şehirlerarası otobüs hatlarının fiyat bilgileri ve belli bir miktar para verildi. Otobüslerin uğradığı tüm şehirlerden geçen bir tur yap­maya bütçeniz yeter mi yetmez mi? Bu ünlü “Seyyar Sa­tıcı Problemi”dir.

Bize bir ülkenin karayol­ları trafik haritasındaki yol uzunluğu bilgileri verildiğinde, istenen iki şehir arasındaki en kısa yolu buluruz. Bu bir P problemidir. Ancak tüm şehirlerden geçen bir bütçe yapmanız gerekirse işler değişir. Problemin bu biçiminde girdisi n sayıda şehirdir; çıktı da “evet” ya da “hayır” kararı olacaktır. Daha ucuz bir yol bulmak için kaç bilgisayar adımına gerek vardır? Yaklaşık 100 şehir varsa, elimizde saniyede 1018 işlem yapabilecek bir bilgisayar bulunuyorsa problemin yukarıda bahsettiğimiz yaklaşımla çözülmesi 4000 yüzyıl alacaktır. İşte bu problemi çöze bilecek verimli bir algoritma henüz yoktur. Bu bir NP problemidir.

“P = NP?” Sorusu Nedir?

P sınıfındaki her problem NP sınıfındadır; çünkü polinom zamanda çözümü bulmak kendi kendisinin doğrulamasıdır. Asıl zor soru şudur: Bütün NP problemleri için bir polinom zaman algoritması bulmak mümkün müdür? P’nin NP’ye eşit olup olmadığı bilinmiyor. Genel kanı P≠ NP yönünde. Bir milyon ABD doları vaat edilen 7 sorudan biri de “P ile NP eşit midir?” sorusudur.

NPP’ye eşit olsa ne olur diye düşünüyorsanız acele etmeyin. P=NP durumunun doğrulanması demek bütün internet güvenliğinin altüst edebileceği demektir. Sonuçta şifrelemelerimizin hepsi çok büyük sayıların asal çarpanlara ayrılmasının çok zor olması, yani bu problemin NP olmasına dayanıyor. Eğer bu probleme P’de bir çözüm bulunursa vay halimize:)

Kaynak:

  • Tony Crilly; The big questions: mathematics, ISBN 978 1 84916240 1 
  • Chris Stephenson; “Donald Knuth’un Bir Sorusu“; Matematik Dünyası 2003
  • Cem Say; 50 Soruda Yapay Zeka; Bilim Ve Gelecek Yayınevi;

Matematiksel

Sibel Çağlar

Merhabalar. Matematik öğretmeni olarak başladığım hayatıma 2016 yılında kurduğum matematiksel.org web sitesinde içerikler üreterek devam ediyorum. Matematiğin aydınlık yüzünü paylaşıyorum. Amacım matematiğin hayattan kopuk olmadığını kanıtlamaktı. Devamında ekip arkadaşlarımın da dahil olması ile kocaman bir aile olduk. Amacımıza da kısmen ulaştık. Yolumuz daha uzun ama kesinlikle çok keyifli.

Bu Yazılarımıza da Bakmanızı Öneririz