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. Şimdi gelin konuyu basitçe anlamaya çalışalım.
Diyelim ki Amerika’da eğitim gören çok sayıda arkadaşınız var. Siz de uçak bileti parasını ayarladınız ve yanlarına gitmeye karar verdiniz. Sonuçta eliniz boş gitmek istemeyeceksiniz. Bu durumda hepsine hediye almanız gerekiyor. Ancak ufak bir sorununuz var. Tüm bu hediyeleri valizinize sığdırmanız mümkün değil.
Sonucunda arkadaşlarınızın kesin seveceğine inandığınız ancak havayolunun koyduğu ağırlık sınırını aşmayan bir hediye kombinasyonunu yanınıza almaya karar veriyorsunuz. Peki ama bu seçimi nasıl yapacaksınız?
Akla gelen ilk çözüm elbette olası tüm kombinasyonları denemek olacaktır. Sonuçta bunların değerini ve ağırlığını hesaplayabilir, sonrasında da ağırlık sınırının altında olan ancak değeri en fazla olan kombinasyonu seçebilirsiniz.
Ziyaret edeceğiniz arkadaş sayısı sınırlı ise kesinlikle bunu deneyin. Ancak çok çok fazla arkadaşınız var ise bu çözüm pek de pratik olmayacaktır. Bu durumda bir algoritmaya ihtiyaç duyarsınız. Bu sayede bilgisayarda gerekli tüm kombinasyonları kolayca deneyebilirsiniz.
P ile NP 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.
Neyse ki bir algoritmanın verimli olup olmadığını anlamak için bu işe kafa yoranların ellerinde verimli bir matematiksel araç vardır. Örneğin, girdi boyutunun (hediye sayısı) n olduğunu varsayalım. Problemi çözmek için geçen süre kabaca n, veya n2 veya n3 veya nk gibi herhangi bir k doğal sayısı için büyürse, n “kolay” kabul edilmektedir.
Diğer bir deyişle, adım sayısının n’in bir kuvveti gibi olan bir algoritmanın “polinom” zamanda çözüleceği söylenir. Yani 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ı saptama, dört işlem aritmetik hesapları P sınıfındaki problemlerdir.
Yazının başında verdiğimiz örnek bir NP problemi idi. Bu problem, olası bir çözüm (hediyelerin bir kombinasyonu) verildiğinde, doğru olup olmadığını kontrol etmenin çok kolay olması gibi hoş bir özelliğe sahiptir: yalnızca ağırlıkları ve değerleri toplamanız gerekir ve bunu polinom zamanında yapabilirsiniz.
Ancak, sorunu sıfırdan çözmek için bir polinom zaman algoritmasının var olup olmadığı bilinmemektedir. Bu, sırt çantası problemini NP adı verilen bir problem sınıfına sokar.
“P = NP” Sorusu Nedir?
P sınıfındaki problemlerin kolay olduğu düşünülür. Sonucunda bir bilgisayar algoritması bunları uygun bir sürede çözecektir. Ancak NP sınıfındaki problemlerin genellikle daha zor olduğu düşünülür. Sonucunda çözüm bir bilgisayar bile milyarlarca yıl zaman alabilir.
Sadece bu kadar da değil. Karmaşıklığında kendi içinde bir sıralaması vardır. NP tam ( complete) problemleri, NP’deki en zor problemler olarak kabul edilmektedir. En az her bir NP problem kadar zor olan problemlerin bulunduğu sınıfa NP-Zor (NP-hard) denir.
Ve aslında bunların hepsi eşdeğerdir. Bu nedenle bir tanesini çözmeyi başarırsanız aslında hepsini çözmüş olursunuz. Artan karmaşıklığa göre sınıflandırmayı aşağıdaki çizimde görebilirsiniz.
P sınıfı, polinom zamanda çözülebilen tüm problemleri içerir. NP sınıfı, potansiyel bir çözümün polinom zamanında kontrol edilebileceği tüm sorunları içerir. NP sınıfının P sınıfına eşit olması mümkündür, ancak bunun olup olmadığını kimse bilmiyor, bu yüzden iki diyagram var: biri P=NP olduğu durum için ve biri olmadığı durum için.
Bu karmaşıklık hiyerarşisi, matematiğin en ünlü sorularından birine yol açar: NP’de gerçekten P’den daha zor problemler var mı, yoksa onları çözmek için en iyi algoritmaları henüz bulamadık mı? Bu P’ye karşı NP problemi olarak bilinir.
Genel kanı P≠ NP yönünde. Bir milyon ABD doları vaat edilen 7 sorudan biri de “P ile NP eşit midir?” sorusudur. Daha fazlasını bu yazımızda bulacaksınız. Henüz Kimsenin Çözemediği Milenyum Soruları Nelerdir?
P ile NP Birbirine Eşit Olursa Ne Olur?
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.
P ile NP probleminden bahsedildiği zamanlarda akla ilk olarak en ünlü örnek olarak Gezgin Satıcı problemi gelecektir. Aralarındaki mesafeyi bildiğiniz, ziyaret edilmesi gereken bir sürü yeri olan, ve her yeri tam olarak bir kez ziyaret ettikten sonra, en sonunda başa dönmeniz gereken her durumda en kısa rotayı bulmanız gezgin satıcı problemi ile ilgilidir.
Az sayıda yer varsa, tüm olası rotalara bakarak cevabı kolayca bulabilirsiniz. Ancak gidilmesi gereken yer sayısı arttıkça, bu hesaplama inanılmaz derecede sıkıcı hale gelir.
Bunu yapmak için daha iyi bir yöntem, yer sayısı çok fazla olsa bile size makul bir sürede cevap verecek bir algoritma var mıdır? Cevabı henüz kimse bilmiyor. Henüz hiç kimse ne bulmayı neden olmadığını göstermeyi başaramadı.
Gördüğünüz gibi bu problem yazıdaki sırt çantası problemi ile eşdeğer mantıktadır. Bu yüzden biri çözülürse diğerleri de çözülecektir.
Bu problemler NP-zor sınıfına girmektedir. Ancak bu, bir gün birisinin onları çözmek için en uygun algoritmayı bulamayacağı anlamına da gelmemektedir.
Gezgin satıcı problemi için bir polinom zamanlı algoritma bulduğunuzu hayal edin. Bu, NP’deki her problemin polinom zamanında çözülebileceği anlamına gelir. P=NP’yi kanıtlamış olursunuz ve gidip 1 milyon dolarınızı alabilirdiniz.
Ancak alacağınız ödülün yanında bunun başka anlamları da olurdu. Bu ödül karşılığında güvenliğinizden vazgeçmeniz gerekebilirdi. Bunun nedeni şudur. NP sınıfından gelen problemler genellikle kriptografide kullanılır. Bu sayede de internet işlemlerinizi güvenli bir şekilde yapabilirsiniz.
Problem hakkında daha fazla bilgiyi bu yazımızda bulacaksınız. Gezgin Satıcı Problemi Nedir ve Neden Önemlidir?
Kaynaklar ve ileri okumalar:
- An extremely superficial look at some complexity classes. Yayınlanma tarihi: 25 Ocak 2018; Bağlantı: https://plus.maths.org/content/conversation-stephen-cook
- Tony Crilly; The big questions: mathematics, ISBN 978 1 84916240 1
- Maths in a minute: The knapsack problem. Yayınlanma tarihi: 13 Nisan 2017; Bağlantı: https://plus.maths.org
Size Bir Mesajımız Var!
Matematiksel, 2015 yılından beri yayında olan ve Türkiye’de matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak veya Patreon üzerinden ufak bir bağış yaparak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
