Bilişimin En Büyük Problemi: P’ye Karşı NP

Matematikte yedi problem o kadar zor ve ilginç kabul edilmiştir ki Clay Matematik Enstitüsü bunlara Milenyum Problemleri adını vermiştir. Bu problemlerden birini çözen kişiye bir milyon dolar ödül verilir. Problemlerden biri bilgisayar bilimine de dokunur ve P’ye karşı NP problemi diye anılır. Gelin bu problemin aslında ne anlattığını açıklayalım.

Baştan söyleyeyim, bunu anlatmak kolay olmayacak. Sonuçta bu bir Milenyum Problemi. O yüzden git kendine güzel bir yeşil çay demle 🍵 ve başlayalım. Önce bilgisayar bilimi ve algoritmalar dünyasından dört farklı problem göreceğiz. Problemleri inceleyecek ve P ile NP harfleriyle nasıl bir ilişkileri olduğuna bakacağız.

Problem 1: En Küçük Sayıyı Bulma

P’ye karşı NP problemi algoritmalarla ve onların karmaşıklığıyla ilgilidir. Önüne yüz tane kâğıt döktüğümü düşün. Her kâğıdın üzerinde bir sayı yazıyor ve senden üzerinde en küçük sayı yazan kâğıdı bulmanı istiyorum. Bu ne kadar sürer?

Yarım dakika mı? İki dakika mı?

Bunlar, teorik bilgisayar biliminde bizi pek ilgilendirmeyen zaman birimleri. Bizi daha çok işlem sayısı ilgilendiriyor. Soruyu biraz farklı sorabiliriz: En küçük sayıyı bulduğumdan emin olmak için kaç kâğıdı kontrol etmem gerekir? Cevap şu: Bütün kâğıtlara bakmam gerekir, çünkü en küçük sayı en son kâğıtta olabilir. Önüne yüz kâğıt atarsam yüz kâğıdı kontrol etmen gerekir. Bin kâğıt atarsam bin kâğıdı kontrol edersin. Genel olarak, önüne n kâğıt atarsam n kâğıdı kontrol etmen gerekir.

Buna algoritmaların karmaşıklığı diyoruz. Önüne n kâğıt atıyorum ve en küçük sayıyı bulmak için n işlem yapman gerekiyor. Demek ki en küçük sayıyı bulan bu algoritmanın karmaşıklığı n’dir. Buna doğrusal karmaşıklık da deriz, çünkü karmaşıklık bir doğrusal fonksiyonla ifade edilir.

Peki, yüz kâğıdı taradın ve en küçük sayının 17 olduğunu söyledin. Doğru söylediğini nasıl kontrol edebilirim? Yine bütün kâğıtlara bakıp hiçbirinde daha küçük bir sayı olmadığını görmekten başka yolu yok. Yani en küçük sayıyı bulmak için sen n kâğıda bakmak zorundasın, ben de kontrol etmek istediğimde aynı şeyi yapmak zorundayım. Sonucun doğrulanmasının karmaşıklığı da n, yani doğrusal karmaşıklıktır.

Sonucu kontrol etmenin, sonucu bulmaktan daha kolay olduğu algoritmalar var mı?

Problem 2: Çiftin Çarpımı

Önüne aynı büyüklükte iki kâğıt yığını döktüğümü düşün. Her kâğıtta yine bir sayı yazıyor. Senden A yığınından bir sayı ve B yığınından bir sayı bulmanı istiyorum; bunların çarpımı 918 etmeli. Örnek olarak şu sayı yığınlarına bakalım:

$$\begin{array}{rcl}A& =& \{49,11,32,54,15\}\\ B& =& \{17,64,74,61,21\}\end{array}$$

Çarpımı 918 olan sayı çiftini nasıl bulabiliriz? Bütün olasılıkları denemek yeter. Kaç tane var? Epey çok: 25 tane. A yığınındaki ilk sayıyı, yani 49’u, B yığınındaki her sayıyla çarparak başlarız:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Hiçbir çift 918 vermiyor. O hâlde aynısını A yığınındaki öbür sayılarla da deneriz: 11 için beş çift daha, 32 için beş çift daha, 54 için beş çift daha ve 15 için son beş çift. Toplam 25 sayı çiftini deneyebiliriz. Sonunda 54 · 17 = 918 olduğunu buluruz.

Bu algoritmanın karmaşıklığı nedir? Kaç çifti çarpmak zorunda kaldığımız bizi ilgilendirecek. İki yığında da beşer kâğıt vardı ve ilk yığındaki beş sayının her birini ikinci yığındaki beş sayının her biriyle denememiz gerekti. Toplam 5 · 5 = 25 kombinasyon denedik. Önüne on kâğıtlık iki yığın atsaydım 10 · 10 = 100 kombinasyon denemen gerekirdi. Genelleştirirsek, önüne n kâğıtlık iki yığın atarsam n · n = n² kombinasyon denemelisin.

Bu algoritmanın karmaşıklığı n²’dir, yani ikinci dereceden karmaşıklığa sahiptir, çünkü karmaşıklığı bir ikinci dereceden fonksiyon ifade eder.

Peki sonucu kontrol etmek ne kadar zor? Bana 54 ile 17’nin çarpımının 918 ettiğini söylersen senin yaptığın gibi iki yığındaki bütün çiftleri taramama gerek kalmaz. Bu tek çifti, yani 54 · 17’yi çarpmam yeter; doğru söyleyip söylemediğini anlarım. Yani bu problemi çözmek için en fazla n² çarpım hesaplamak gerekirken, doğrulamak için yalnızca bir çarpım hesaplamak yeter. Doğrulamanın karmaşıklığı sabittir: 1.

Bu soru, hesaplamak ve sonra doğrulamak için aynı sayıda adıma ihtiyaç duyduğumuz bir önceki sorudan işte bu bakımdan çok farklıdır.

Bu soru ayrıca bir öncekinden mertebe olarak daha zordur. Önüne on bin kâğıt döküp en küçük sayıyı bulmanı isteseydim, muhtemelen bunu bir günde bulabilirdin. Ama önüne on binlik iki yığın döküp çarpımı aratsaydım, on bin kere on bin çarpımı, yani yüz milyon hesabı kontrol etmen gerekirdi. Saniyede bir çarpım denesen bile bu yaklaşık üç yıl sürerdi.

Problem 3: Alt Küme Toplamı

Üçüncü probleme bakalım. Bu kez önüne üzerinde sayılar yazan on iki kâğıt döküyorum ve senden toplamları sıfır olan istediğin sayıda kâğıdı bulmanı istiyorum. Örnek olarak:

$$A=\{24,-69,1,-15,-76,-60,16,-83,48,-22,54,-47\}$$

Bu sayılardan toplamı 0 olan herhangi bir grup seç. Örneğin

$$24+48-69+1$$

sayılarının toplamı 4 eder, dolayısıyla doğru cevap değil. Doğru cevap şu sayı grubu… Ama bak ne diyeceğim: Bunu ev ödevi olarak kendin bulmayı dene 😉. Toplamı 0 olan tek bir sayı grubu var. En azından bu problemin ne kadar zor olduğunu bizzat görürsün.

Şimdi bu problemin karmaşıklığını bilmemiz gerekiyor. Hesabın kendisi hiç de basit değil ve biraz meraklılara göre. Bu problemin karmaşıklığının nasıl hesaplanabileceğini merak ediyorsan okumaya devam et. Yoksa bir sonraki bölüme geçebilirsin. ⏩

Toplamı 0 olan sayı grubunu nasıl bulabiliriz? Sayıların bütün olası kombinasyonlarını denemek zorundayız. Bütün sayı ikililerini, bütün üçlüleri, dörtlüleri, beşlileri ve devamını denemeliyiz; her grup için toplamının sıfır olup olmadığını kontrol etmeliyiz. Böyle kaç kombinasyon var?

Bunu daha küçük bir sayı kümesi üzerinde gösterelim. B = {5, 7, 9} üç sayısından kaç farklı sayı grubu, yani alt küme oluşturabilirim? Toplam sekiz tane:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5,9\}\\ B_6& =& \{5,7\}\\ B_7& =& \{7,9\}\\ B_8& =& \{5,7,9\}\end{array}$$

Boş alt küme B₁’i de saydığımıza dikkat et. Şimdilik pek işe yaramıyor, ama düzen olsun diye orada bıraktık. Hesabı kolaylaştırmak için her alt kümeye bir ikili vektör karşılık getireceğiz. İkili vektör, 00101010 gibi sıfırlardan ve birlerden oluşan bir dizidir. Biz uzunluğu üç olan ikili vektörlerle çalışacağız. Vektörü şöyle eşleriz: 101 vektörünü, “asıl kümenin birinci ve üçüncü sayısını içeren, ama ikinci sayısını içermeyen” alt kümeye, yani {5, 9} kümesine karşılık getiririz. 110 vektörünü “asıl kümenin birinci ve ikinci sayısını içeren, ama üçüncü sayısını içermeyen” alt kümeye, yani {5, 7} kümesine karşılık getiririz ve bu böyle sürer.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5,9\}& \to & 101\\ B_6=\{5,7\}& \to & 110\\ B_7=\{7,9\}& \to & 011\\ B_8=\{5,7,9\}& \to & 111\end{array}$$

Her alt kümenin uzunluğu üç olan tam olarak bir ikili vektörü olduğunu görüyoruz. Uzunluğu üç olan her ikili vektör de tam olarak bir alt kümeye karşılık gelir. Demek ki uzunluğu n olan kaç farklı ikili vektör olduğunu hesaplarsak, girdide n farklı sayımız olduğunda oluşturabileceğimiz farklı kombinasyonların sayısını buluruz. Hadi hesaplayalım.

Uzunluğu bir olan iki ikili vektör vardır: 0 ve 1.

Uzunluğu iki olan ikili vektörleri şöyle elde ederiz: uzunluğu bir olan bütün ikili vektörleri alır ve her vektörün sonuna 0 ekleriz; 00 ve 10 vektörlerini elde ederiz. Uzunluğu 1 olan bütün vektörleri yine alır ve sonlarına 1 ekleriz: 01 ve 11. Böylece uzunluğu 2 olan bütün vektörleri elde ettik: 00, 01, 10 ve 11.

Uzunluğu üç olan ikili vektörleri şöyle elde ederiz: uzunluğu iki olan bütün ikili vektörleri alır ve sonlarına sıfır ekleriz: 000, 010, 100 ve 110; sonra bir ekleriz: 001, 011, 101 ve 111.

Sonraki her uzunluk için de böyle devam eder. İkili vektörün uzunluğunu bir artırdığımızda farklı ikili vektörlerin sayısının iki katına çıktığını görüyoruz. Uzunluğu dört olan vektörler için toplam 2 · 2 · 2 · 2, yani 16 farklı kombinasyon elde ederdik.

Genel olarak şunu çıkarabiliriz: n elemanlı bir M kümemiz varsa, bu M kümesinin bütün alt kümelerinin sayısı, uzunluğu n olan bütün farklı ikili vektörlerin sayısına eşittir ve bu sayı

$$\underset{n-\text{kez}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

değerine eşittir.

2ⁿ mi, n² mi — fark etmez mi? Ha Ali ha Veli 🤷‍♂

Demek ki n sayılık bir kümeden oluşturabileceğimiz 2ⁿ farklı alt küme vardır. Bizim örneğimizde n = 12 sayımız var; dolayısıyla 2¹² farklı kombinasyonu, yani 4096 kombinasyonu kontrol etmemiz gerekir. Bu problemin karmaşıklığı 2ⁿ’dir, yani üstel karmaşıklığa sahiptir, çünkü onu bir üstel fonksiyon ifade eder.

Bir önceki problemin karmaşıklığı n² idi, bu problemin karmaşıklığı ise 2ⁿ. Birbirine çok benziyor, değil mi? Ama üssün sabit olmasıyla yerinde n değişkeninin olması arasında büyük fark var. n = 4 olduğunda şunu elde ederiz:

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Tamam, şimdilik ikisi de aynı çıkıyor. Peki n = 10 olsa?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Vay, üstel fonksiyon fırladı ve birden ikinci dereceden fonksiyonun yaklaşık on katı oldu. n = 20 için ne elde ederiz?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1048576\end{array}$$

n = 20 için üstel karmaşıklığın değeri, ikinci dereceden karmaşıklığın yaklaşık 2.600 katıdır. Demek ki üstel fonksiyon, ikinci dereceden fonksiyondan çok daha hızlı büyür. Bir daha nüfus içinde üstel hızla yayılan bir salgın başımıza geldiğinde bunu hatırla.

Yani önüne yirmi kâğıt atsaydım, 1.048.576 kombinasyonu kontrol etmen gerekirdi. Bu hayli fazla.

Sonucun Doğruluğunu Nasıl Kontrol Ederiz?

Ortaya çıkan sayı grubunun toplamının gerçekten 0 olduğunu doğrulamam ne kadar sürer? Oldukça hızlı olur: bu tek sayı grubunu toplarım; toplamı 0 ise doğru kâğıt grubunu bulmuşsun, toplam başka çıkarsa yanlış kâğıt grubunu bulmuşsun demektir.

Yine görüyoruz ki sonucu kontrol etmek, onu bulmaktan mertebe olarak daha kolaydır.

Problem 4: Gezgin Satıcı Problemi

Gezgin satıcı problemi, algoritmik problemlerin en ünlülerinden biridir. Kabaca anlatırsak, yağmur satan bir gezgin satıcımız var. Bu satıcı geçimini sağlamak için çok seyahat etmek zorunda. Bu yüzden Türkiye’nin en büyük 14 şehrini ziyaret etmeye karar verdi. İsraf etmek de istemediği için bu şehirlerin hepsinden geçen mümkün olan en kısa yolu bulmaya karar verdi. Bizim görevimiz de bu en kısa yolu bulmak.

Bu en kısa yolu nasıl bulabiliriz? Bütün olasılıkları deneriz.

İşi basitleştirebiliriz. Her iki şehir arasında tam olarak bir en kısa yol olduğunu düşünelim. Bütün şehirler arasındaki en kısa yolu nasıl bulabiliriz? Toplam 14 şehrimiz var. Yani nereden başlayacağımıza dair 14 seçeneğimiz var. Diyelim ki Ankara’dan başladık. Ankara’dan nereye gidebiliriz? Teorik olarak diğer herhangi bir şehre gidebiliriz. Yani geriye kalan 13 şehir arasından seçebiliriz.

Şimdiden ilk iki şehri ziyaret etmenin toplam 14 · 13 yolu olduğunu hesaplayabiliriz — nereden başlayacağımıza dair 14 seçeneğimiz var, sonra geriye kalan 13 şehir arasından seçiyoruz.

İkinci şehre vardığımızda devam etmemiz gerekir. İki şehirde zaten bulunduk, dolayısıyla geriye kalan 12 şehirden birine gidebiliriz. Böylece ilk üç şehri ziyaret etmenin toplam 14 · 13 · 12 yolu olur.

Üçüncü şehri ziyaret ettikten sonra geriye kalan 11 şehirden birini seçmemiz gerekir, sonra geriye kalan 10 şehirden birini ve bu böyle sürer.

Hepsini ziyaret ettiğimizde toplam şu kadar seçeneğimiz olduğunu görürüz:

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

Bu sana ünlem işaretiyle gösterdiğimiz faktöriyeli hatırlatabilir. Dolayısıyla bu çarpımın 14! olduğunu söyleyebiliriz:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

Yani bu 14 şehrin hepsinden geçen 14! yol vardır. Bu çok mu? Epey, çünkü

$$14!=87178291200.$$

Genel olarak n şehir arasındaki en kısa yolu arasaydık, n! farklı yolu denememiz gerekirdi. Bu çözümün karmaşıklığı da n!’dir.

Doğru sonucu bulduğumuzu nasıl doğrularız? Bana en kısa yolun şu şehirden şu şehre, sonra şuraya vb. olduğunu söylesen, doğru söylediğini nasıl kontrol edebilirim? Hiç kolay değil 🤷‍♂. Çünkü o yola baktığımda tam da bu yolun en kısa olup olmadığını kolayca doğrulayamam. Aslında bütün hesabı baştan yapmam gerekir. Sonucu doğrulamanın karmaşıklığı da n!’dir.

P ve NP Sınıfları

Dört problemi ve onları çözen algoritmaları tanıttık; çözümü bulmanın ne kadar zor, bu çözümü kontrol etmenin ne kadar zor olduğunu inceledik. Bunu şu tabloda özetleyebiliriz:

Şimdi problemlerimizi iki gruba ayıracağız. İlk gruba çözmesi kolay olan problemler girecek. Bunlar karmaşıklığı n ya da n² ya da n³ ya da n⁴ vb. olan problemlerdir. n² gibi ifadelere polinom dediğimiz için bu problem sınıfını P harfiyle gösteririz. Yani P sınıfı, polinom zamanda çözülebilen problemleri içerir (karmaşıklıkları örneğin n² ya da n⁷ olan problemler). Genel olarak bunlar az çok kolayca çözülebilen problemlerdir.

Böylece 1. problem olan en küçük sayıyı bulma P sınıfına girer, çünkü çözümünün karmaşıklığı n’dir; 2. problem olan çiftin çarpımı da girer, çünkü çözümünün karmaşıklığı n²’dir. İkisi de polinomdur.

İkinci sınıf NP sınıfıdır. Bu sınıf, polinom zamanda doğrulanabilen problemleri içerir. NP sınıfına sonuncusu hariç bütün problemlerimiz girer. Gezgin satıcı problemini polinom zamanda doğrulayamıyoruz. Önceki üç problem ise polinom zamanda doğrulanabilir.

Gezgin satıcı problemini polinom zamanda ne çözebiliyoruz ne de doğrulayabiliyoruz. Gezgin satıcı problemi için daha da zor problemleri içeren bir sınıfa daha ihtiyacımız olurdu. Bu sınıf var, ama şu an bizim için ilgi çekici değil.

P sınıfının NP sınıfının alt kümesi olduğu açıktır. Yani P sınıfındaki her problem aynı zamanda NP sınıfındadır. Bu mantıklı — bir problemi polinom zamanda çözebiliyorsak sonucu polinom zamanda doğrulayabiliriz de.

P’ye Karşı NP Problemi

Peki bu tersi için de geçerli mi? NP sınıfındaki her problem aynı zamanda P sınıfında mı? Yani bir problemin sonucunu polinom zamanda doğrulamanın bir yolu varsa, o problemi polinom zamanda çözen bir algoritma da var mıdır?

Örneğin 3. problemin, yani alt küme toplamı probleminin sonucunu polinom zamanda doğrulayabildiğimizi biliyoruz. Ama onu çözmek için polinom olmayan bir algoritma kullandık; kullandığımız algoritmanın karmaşıklığı üsteldir: 2ⁿ. Peki bu problem için polinom karmaşıklıklı hiçbir algoritmanın olmadığını kesin olarak biliyor muyuz?

Bilmiyoruz!

Polinom zamanda doğrulanabilen her problem için o problemi polinom zamanda çözen bir algoritma olması çok iyi mümkün. Bunu bilmiyoruz. Böyle bir algoritmanın var olduğunu ispatlayamıyoruz, ama var olmadığını da çürütemiyoruz.

NP sınıfındaki her problem için onu polinom zamanda çözen bir algoritma olsaydı, bu NP sınıfının aslında P sınıfına eşit olduğu anlamına gelirdi. P sınıfındaki bütün problemler NP sınıfında, NP sınıfındaki bütün problemler de P sınıfında olurdu — iki sınıf birbirine eşit, aynı olurdu.

Dolayısıyla P’ye karşı NP problemi, P sınıfının NP sınıfıyla aynı olup olmadığı, yoksa iki farklı problem sınıfı mı söz konusu olduğu sorusudur.

Yani ya P = NP geçerlidir ya da P ≠ NP geçerlidir. Bunu kimse bilmiyor ve bunu çözersen seni bir milyon dolarlık ödül, ölümsüz şöhret ve büyük ihtimalle bilgisayar bilimcilerin Nobel’i sayılan Turing Ödülü bekliyor.

P = NP Olsaydı Ne Olurdu?

P = NP olsaydı ne olurdu? Ne olacağını söylemek pek kolay değil. NP sınıfındaki bütün problemler için onları polinom zamanda çözen bir algoritmanın var olduğunu bilirdik. Örneğin 3. problemimiz olan alt küme toplamı için onu polinom zamanda çözen bir algoritma olduğunu bilirdik. Ama bunun üç tuzağı var:

• Böyle bir algoritmanın var olduğunu bilmemiz, onu bulabileceğimiz anlamına gelmez. Yani evet, problemi polinom zamanda çözen bir algoritma var diye bilirdik, ama belki daha yüz yıl onu kuramazdık. Bu, genel görelilik kuramının kara delikleri öngörmesine rağmen kara deliğin ilk “fotoğrafını” çekebilmemizin birkaç on yıl daha sürmesine benzer.
• Polinom zamanda çalışan bir algoritmanın var olması maalesef onun hızlı olduğu anlamına gelmez. Karmaşıklığı n¹⁰⁰ olan bir algoritma bulabilirdik. Çünkü n¹⁰⁰ ifadesi de bir polinomdur. 2ⁿ ile n¹⁰⁰ karmaşıklıklarını karşılaştırırsak, n nispeten küçük olduğu sürece karmaşıklığı 2ⁿ olan algoritmanın hâlâ daha az işleme ihtiyaç duyduğunu görürüz. Örneğin n = 20 için 2²⁰ = 1.048.576 olur, oysa 20¹⁰⁰ ifadesi yaklaşık 130 basamaklı bir sayıya yol açar; bu sayı 1.048.576’dan yaklaşık 120 mertebe büyüktür. Yani polinom algoritmamız gerçekte üstel olandan daha yavaş olurdu. En azından n nispeten küçük olduğu sürece.
• Yine de polinom zamanda çalışan hızlı bir algoritma bulabilseydik, pek çok problemi daha hızlı ve daha büyük doğrulukla çözebilirdik. Bu elbette olumlu bir haber, ama olumsuz yanları da var. Bazı problemlerin zor çözülebilir olmasına güvenen bir alan var: kriptografi, yani şifreleme. Dolayısıyla günümüzün şifrelerini kırmak mertebe olarak çok daha kolay hâle gelebilirdi.

Ara not: Buraya kadar okuduğun için ödül olarak sana söyleyeyim, 3. problemin çözümü 24 + 1 − 60 + 16 − 83 + 48 + 54’tür.

P ≠ NP Olsaydı Ne Olurdu?

P ile NP problem sınıfları farklı olsaydı pek bir şey olmazdı, çünkü bu az çok mevcut durumdur. Şu an NP sınıfından zor bir problemi polinom zamanda çözen hiçbir algoritmamız yok ve biri P ≠ NP olduğunu kanıtlasa bile bu sonsuza dek öyle kalırdı. P = NP olduğunun kanıtı çok daha büyük bir sansasyon olurdu.