Nedir Bu P=NP Problemi?

“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 ve bu iki kümedeki kareköklerin toplamları birbirine olabildiğince yakın olsun.”

bu soruyu Bilgisayar Biliminden Seçilmiş Makaleler adlı kitabında Donald Knuth sormuştur:

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.

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…

Ancak, Knuth’un bizden bir isteği daha var: Program çağdaş bir bilgisayarda en fazla 10 saniyede yanıtı versin…

Şimdi burada duralım!

Önce neden 50 kök? Sonra neden 10 saniye? Elbette burada önemli olan 50 ve 10 sayıları değil, olabildiğince çabuk yanıtı veren bir program yazabilmek.

Knuth’un sorusu öyle sanıldığı kadar basit de­ğil. Bu problemin özünde çok çok önemli bir baş­ka problem var.

Her şeyden önce “birbirine olabildiğince yakın olsun” ne demek? En yakın olsun mu denmek is­teniyor? Yoksa aradaki fark önceden verilmiş bir sayıdan küçük mü olmalı?

Soru zor, çok zor. Bu çok zor soruya şöyle yak­laşalım: Verilen zaman içinde (burada 10 saniye) yapabileceğimizin en iyisini yapmaya çalışalım.

“Birbirine olabildiğince yakın olsun”u birinci anlamda, yani “mutlak yakınlık” anlamında yo­rumlayacak olursak, ya 249 seçeneği ( tam 14 basamak)teker teker deneyip en küçük farkı veren kümeleri bulmalıyız ya da konuya kuramsal yaklaşıp matematiksel bir teoremin yardımıyla en iyi sonucu şıp diye bulmalıyız.

“Birbirine olabildiğince yakın olsun”u ikinci anlamda yorumladığımızı varsayalım. Ne yapaca­ğız? Akla ilk gelen çözüm şu: Sayıları kümelere ayır, kümelerdeki sayıları ayrı ayrı topla, toplam­ların farkını al ve önceden verilmiş sayıyla karşılaş­tır. Aradaki fark daha küçükse dur. Değilse, önce­den verilmiş elli sayıyı bir başka türlü iki kümeye ayır. Bu işlemi en az bir kez en fazla 249 kez yapa­cağız… Üstelik istediğimiz sonucu bulacağımız bi­le kuşkulu: belki de 249 denemeden sonra bile top­lamların arasındaki fark istediğimiz kadar küçük ol­mayacak.

Knuth’un sorusunun ikinci versiyonu şu özel­liğe sahip: Çözümü polinom zamanda (  problemin büyüklüğü doğrusal artarken hesaplanmasi icin gereken vaktin bir polinom fonksiyonuna bağlı olarak artmasi haline verilen isim) bulması­nı bilmiyoruz, ancak bulunmuş bir çözümün doğru olup olmadığını polinom zamanda kont­rol edebiliriz. Bu özelliğe sahip sorular kümesi­ne NP (non-deterministic polynomial time) de­nir. Polinom zamanda çözülen sorulara da P adı verilir.

İşte bu, bilgisayar biliminin en önemli proble­midir: n sayısıyla ilgili bir soru, eğer yanıtının doğruluğu n cinsinden bir polinom zamanda kont­rol edilebiliyorsa, o problemi gene n cinsinden bir polinom zamanda çözen bir bilgisayar yazılı­mı var mıdır?

P’nin NP’ye eşit olup olmadığı bilinmiyor. Bu soruyu çözene Clay Enstitüsü bir milyon dolarlık bir ödül verecek. Genel kanı P≠ NP yönünde.

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: Matematik Dünyası 2003 – Yaz – “Donald Knuth’un Bir Sorusu” – Chris Stephenson

Matematiksel

Yazıyı Hazırlayan: Sibel Çağlar

Kadıköy Anadolu Lisesi, Marmara Üniversitesi İngilizce Matematik Öğretmenliği, ardından uzun süre özel sektörde matematik öğretmenliği, eğitim koordinatörlüğü diye uzar gider özgeçmişim…

Önemli olan katedilen değil, biriktirdiklerimiz ve aktarabildiklerimizdir bizden sonra gelenlere…

Eğitim sisteminin içinde bulunduğu çıkmazı yıllarca iliklerimde hissettikten sonra, peki ama ne yapabilirim düşüncesiyle bu web sitesini kurmaya karar verdim.

Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı.

Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bunlara da Göz Atın

Regiomontanus Problemi

Yüzyıllar boyunca bir çok matematikçi Euclid’in elemanlar eserini okuyarak geometri ve matematik öğrendiler. Birçok fizikçi …

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

ga('send', 'pageview');