• Ağustos 3, 2022

Kriptografiyi kırabilecek milyon dolarlık problem: P vs NP problemi

Kriptografiyi kırabilecek milyon dolarlık problem: P vs NP problemi

P vs NP problemi, teorik bilgisayar bilimindeki en zor problemlerden biridir. Bu, eğer geçerli bir kanıt sağlanırsa çözücünün 1 milyon dolar alacağı bir Milenyum Ödül Problemi.

Genellikle, bir sorunun çözümünü doğrulayabilirsiniz. Bölme için çarpmayı kullanmak veya bir değişken için cevabı eklemek yoluyla ya da farklı yöntemler kullanarak okullarda tüm matematik öğretmenleri cevabınızı kontrol etmenizi söyler.

Diyelim ki bir çözümü kolayca doğrulayabiliyorsunuz, peki o çözümü bulmak da o kadar kolay mı?

Bu, P’ye karşı NP problemidir, eğer geçerli bir kanıt sağlanırsa çözücünün 1 milyon dolar alacağı bir Milenyum Ödül Problemi.

P vs NP problemi nedir?

P harfi “polynomial”, NP harfleri ise “non-deterministic polynomial” ifadelerini temsil ediyor. Türkçe karşılıkları “polinom” ve “belirleyici olmayan polinom”dur. “P eşittir NP?” ise Hesaplama Teorisi’nin en temel problemidir.

Bilgisayar bilimlerinde algoritmaların verimliliği çok önemlidir. Çoğu algoritmanın, polinom zamanı adı verilen bir standartta çözülebilirse “hızlı” olduğuna inanılır. Polinom zamanı bir problemin, girdinin karmaşıklığı verilen bir polinom faktörü tarafından ölçeklenen adımlarda çözülebildiği zamandır. Diyelim ki girdinin karmaşıklığı bir n sayısı olsun, bir polinom zaman algoritması bir problemi nk adımda çözebilecek.

Esasen, P vs NP şu soruyu soruyor: Çözümleri polinom zamanında doğrulanabilen problemlerin, aynı zamanda cevapları polinom zamanında çözülüyor mu?

En belirgin alt problemlerden biri NP-tamamlanmış problemlerdir. NP-tamamlanmış problemler, hızlı bir şekilde doğrulanabilen ve diğer tüm NP-tamamlanmış problemlerini simüle etmek için kullanılabilen problemlerdir. Bu nedenle, bu problemlerden birini polinom zamanında çözmek, P’ye karşı NP’yi çözmek için büyük bir destektir.

Bu sorunlardan bazıları, Battleship gibi oyunları ve NxNxN Rubik Küpü için en uygun çözümü içerir. Ancak aynı zamanda gezgin satıcı problemi gibi ünlü teorik soruları da içerir. Bunlardan herhangi biri için bir çözüm bulunursa, NP-tam problemler için de genel bir çözüm bulunabilir.

Ciddi sonuçları olabilir

P’nin NP’ye eşit olduğu kanıtlanırsa, ciddi sonuçlar ve faydalar olabilir. Açık anahtarlı kriptografi alt üst olacağı ve birçok şifre kırılabileceği için siber güvenlik büyük bir sorun haline gelecektir. Bununla birlikte, daha iyi tamsayı programlama ve gezgin satıcı probleminin çözülmesi nedeniyle protein yapısı tahmini ve genel hesaplama araştırmalarında da gelişmeler olacaktır.

P’nin NP’ye eşit olmadığı kanıtlanırsa, neredeyse hiçbir dezavantaj ve fayda olmayacaktır. Araştırmacılar daha sonra, gerçekten çok fazla değişmeyecek olan tüm NP-tamamlanmış problemlere genel bir çözüme daha az odaklanacaklardır.

P vs NP, bilgisayar bilimlerinde ciddi etkileri olabilecek kritik bir çözülmemiş problemdir. Problem hakkında varılan fikir birliği, P’nin NP’ye eşit olmadığı olsa da yaygın olarak kabul edilen herhangi bir kanıt, bilim dünyasını sarsacaktır.