theory of computation'ın problemleri karmaşıklıklarına göre sınıflandırmakla ilgilenen alt dalıdır. bu yazıyı okuyanlar arasında alanı bilgisayar veya matematik olmasa bile p versus np (p =? np) problemini duymuş olanlar olabilir. İlgi çekmek için baştan bahsedeyim dedim çünkü bu problemin değeri tam 1 milyon dolar. tabi bu sadece bir matematik enstitüsünden alacağınız ödül. dünyanın en ünlü insanlarından biri olacaksınız, tarihe adınızı kazıyacaksınız vs. yazının sonlarına doğru bu ilişkinin ne anlama geldiğini ve neden bu kadar önemli olduğunu anlatmaya çalışacağım ama önce biraz teorik bilgi:

elimden geldiğince basit anlatmaya çalışacağım. öncelikle karmaşıklık sınıflarının gösterildiği bir diyagrama şuradan ulaşabilirsiniz. ben içten dışa doğru bu sınıfları açıklamaya çalışacağım:

P (Polynomial time) sınıfı, çözülme zamanı en az olan yani en basit problemleri kapsayan sınıftır. isminden de anlaşılacağı üzere bu problemler polinom zamanda çözülebilir. yani bir algoritmaya giren n tane inputunuz varsa algoritmanın çalışma zamanı n + 4 yada n^3 + 15 yada n^5 + n^2 + 5 gibi bir polinom olacaktır. yani big-O notasyonuyla problemin karmaşıklığın O(n^k) olması gerekiyor. sorting problemi,en kısa yol problemi gibi birçok ünlü problem bu sınıfa dahildir.

NP (nondeterministic polynomial time) sınıfındaki problemler nondetermenistic turing machine tarafından sabit uzayda polinom zamanda çözülebilen problemleri kapsayan sınıftır. bu tanım bilgisayarcılar içindi. çünkü bilgisayarcıların turing makinesinin ne olduğunu, nondeterministic'in ne anlamda kullanıldığını bilmeleri gerekir. nondeterministic kelimesi bilgisayar biliminde fizik ve felsefedeki anlamıyla tam olarak aynı anlamda kullanılmıyor. turing makinesini bilmek ise karmaşıklık teorisini en azından giriş düzeyinde anlamak için çok gerekli değil. onu bir kara kutu olarak düşünebiliriz. bir algoritma, girdiler alıyor çıktılar veriyor. şimdi herkes için bir tanım yapmaya çalışayım:

NP sınıfı "şanslı algoritmalar" tarafından polinom zamanda çözülen problemleri kapsar. şanslıdan kasıt o kadar şanslı ki eğer bir çözüm varsa o çözüme algoritma mutlaka ulaşır. algoritma çözüme ulaşana kadar bir dizi tahmin yapar ama öyle tahminler yapar ki eğer problemin bir çözümü varsa yaptığı tahminler dizisi algoritmayı çözüme götürür. bu size manyakça gelebilir. ki öyle de. tahmin edebileceğiniz gibi gerçekte böyle bir algoritma yok. daha doğrusu böyle bir hesaplama modelini gerçekleştirebilen bir bilgisayar yok. yani nondeterministic turing machine gerçeklenmesi bildiğimiz kadarıyla mümkün olmayan, tamamen teorik bir hesaplama modelidir. tabii ki matematiksel olarak tutarlı bir modeldir. yani ne işimize yarıyor derseniz problemleri sınıflandırmamıza yarıyor. zaten genel olarak
theory of computation "bilgisayarların teorik sınırları nelerdir?" sorusuyla ilgilenir.

np-hard en az NP sınıfındaki en karmaşık problem kadar karmaşık olan problemleri kapsar. kabaca NP'nin bittiği yerde np-hard başlar diyebiliriz. np-hard sınıfındaki problemler NP olabilirler fakat olmak zorunda değillerdir. hatta undecidable (çözülemez) bile olabilirler.

np-complete ise NP sınıfındaki en zor problemleri barındırır. dolayısıyla her np-complete problem aynı zamanda NP sınıfına da dahildir. aslında başka karmaşıklık sınıfları da var ama hala bu yazıyı birkaç kişinin okuma ihtimali olduğunu düşünerek bu kadarıyla yetiniyorum.

ve son olarak bütün bu sınıfları kapsayan uzay var. hayal edebildiğimiz en güçlü hesaplama modeli olan nodeterministic turing machine'in bile çözemeyeceği problemler var. bunlara undecidable problemler diyoruz. halting problem gibi. (bkz: computability theory) aslına bakarsanız evrendeki problemlerin neredeyse tamamı bu türden çözülemez problemlerdir. bunun da basit ve güzel bir kanıtı var ama ona da değinmeyeceğim.

şimdi tekrar dönelim p vs np'ye. soru şu: p kümesiyle np kümesi aynı küme midir? yani yukarıda bahsettiğmiz çılgın makine problemleri gerçek bilgisayarlarla simule edebildiğimiz bilgisayarlar kadar hızlı bir şekilde çözebilir mi? sezgisel olarak açıkça görüyoruz ki fantezi model gerçekleyebildiğimiz modelden çok daha güçlü. yarı tanrı gibi bir şey aslında. ama sezgilerimizle bilimin son zamanlarda çok da iyi anlaşmadığını düşünürsek bence "neden olmasın?" diyebiliriz. işte tam da bu sorunun cevabı 1 milyon dolar ,sınırsız şöhret vs.vs.

peki biri çıkıp da manyakça olanı kanıtlaysaydı ne olurdu? yani p=np'yi. aslında tek başına bunu ispatlayan bir matematiksel kanıt gerçek hayatta pek bir şey değiştirmez. ama np problemlerin polinom zamanda gerçek bilgisayarla çözülebileceğinin kanıtlanması çok büyük etkilere sebep olacak algoritmaların yazılmasının kapısını aralar diyebilirim. bu da kriptolojiden yapay zekaya kadar birçok konuda çok önemli gelişmelere sebep olur. bunun dışında aslında bir de p=np doğruysa yapabileceğimiz sezgisel felsefi çıkarımlar var. yine manyakça gibi görünüyor ama p=np, bir problemi çözmenin çözümü kontrol etmekle aynı zorlukta olduğunu ifade ediyor. yukarıda bahsetmedim ama np problemler için yapılan tanımlardan biri de bu. yani np problemler np zamanda çözülebilirler fakat p zamanda tanınabilirler, yada daha türkçe söylersek kontrol edilebilirler. dolayısıyla p=np ise bir problemin çözümünü kontrol etmekle, problemi çözmek aynı zorluk derecesindedir demek zorunda olacağız. yani p=np izafiyet teorisini anlayabiliyorsan izafiyet teorisini ortaya atabilecek kadar zekisin demek olabilir. mozart'ın müziğini tam olarak takdir edebiliyorsan mozart kadar iyi bir müzisyensin demek olabilir. yani yaratıcılık eskisi kadar özel bir şey omayabilir. dijkstra'nin söylediğini sandığım doğru bir söz var: "bilgisayar bilimi artık astronomi ne kadar teleskop ile ilgiliyse ancak o kadar bilgisayarla ilgili" dolayısıyla p=np'nin kanıtlanmasının dünyayı değişterceğini söylemek hiç de fazla değil gibi görünüyor. son olarak sevdiğim bir sözle bu yazıya burada nokta koyayım:

"one day i will find the right words, and they will be simple." jack kerouac

edit: olayı basitleştirmeye çalışırken çok önemli bir hata yapmışım. yazı boyunca nondeterministic turing makinelerinin deterministic turing makinlerinden daha güçlü olduğunu birkaç defa tekrarladım. bu aslında tam olarak doğru değil. gerçekte bütün turing makineleri eşit güçtedir ama bu bu yazıyı basit tutmak adına değinmek istemediğim bir şeydi. ama bir açıdan da doğru gibi diyeblirim. bilgisayar biliminde bunu "effective" olarak isimlendirirler. yani ntm'ler problemleri dtm'lerden daha kısa zamanda çözseler de ntm'lerin polinom zamanda çözdüğü tüm problemleri dtm'ler de polinom zamanda çözebilirler. (bkz: savitch'in teoremi) yazıda bir yerde bunun tersi anlamına gelen bir ifade kullanmışım. o ifadeyi " yukarıda bahsettiğmiz çılgın makine problemleri gerçek bilgisayarla rla simule edebildiğimiz bilgisayarlar kadar hızlı bir şekilde çözebilir mi?" şeklinde değiştirdim. güçlü ifadesini kullanmakta çok sorun görmediğim için o kısımları değiştirmedim. dediğim gibi sonuçta burada makale yazmıyoruz. elimden geldiğince bilimsel jargondan kaçınmaya türkçe kelimeler kullanmaya çalıştım. sonuçta burada yaklaşık 30 yıldır dünyanın en iyi matematikçilerinin çözemediği bir problemi olabilidiğince herkesin anlayabileceği bir şekilde açıklamaya çalıştım. takdir edersiniz ki kolay değil. o yüzden hatalarımız hala da varsa affola. ki var.^:swh^ son olarak yazıyı baştan sona iyi bir şekilde takip edenler şu an bunun p=np'nin doğru olduğu anlamına geldiğini düşünebilir ama aslında öyle değil. bunun yazıda bahsetmediğim psace, npspace sınıfları ile alakası var. onları da savitch'in teoremi başlığı altında açıklamaya çalıştım. (bkz: #111617)