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! Knuth’un sorusu öyle sanıldığı kadar basit de­ğil. Bu problemin özünde çok çok önemli bir baş­ka problem var. Soru zor, hem de çok zor.

Gizemli bir görünümü olan şu “P, NP’ye eşit midir?” sorusu, bilgisayar biliminin matematikle buluştuğu yerde ortaya çıkmış bir problemdir. “Hesaplamalı karmaşıklık kuramı’nın bir parçası olarak bu problem bilgisayarların yapabilecekleri şeylerin sınırlarıyla ilgilidir. Bu problem de Clay Enstitüsü’nün “en aranan” çözümler ve kanıtlar listesinde yer almaktadır. 21. yüzyılın hayati önemdeki problemlerinden biridir, çünkü bilgisayar güvenliği açısından sonuçları vardır.

Bilgisayarlar ancak algoritmalarla, yani yerine getirilecek emir dizileriyle çalışabilir; 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. Peki bunu nasıl gerçekleştirebilir? 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 halledebilir; bu algoritmalar da verimli algoritmalardır.

Şimdi bir bilgisayarın “gezgin satıcı problemi“ni nasıl çözebileceğine bakalım. Bu problemde belli sayıda şehir; şehirler arasında seyahat etmenin farklı maliyetleri vardır. Bir satıcının bütün şehirlerden geçen bir yol izlemesi istenirse, soru, daha ucuz bir yol olup olmadığı sorusu olur. Problemin bu biçiminde girdi, 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…

P, sıralama problemi gibi polinom zamanda çözülebilecek problemler sınıfını oluşturur.  NP ise, polinom zamanda doğrulanabilecek problemler sınıfıdır.

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.

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:

Büyük Sorular/ Matematik –  Tony Crilly

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, 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

Kalkülüs ve Optimizasyon

Optimizasyon eldeki kısıtlı kaynakları en verimli biçimde kullanmak olarak tanımlanabilir kısaca. Matematiksel olarak ifade etmek gerekirse …

Bir cevap yazın

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

ga('send', 'pageview');