Matematik Ne İşe Yarar?

Gezgin Satıcı Problemi Nedir ve Neden Önemlidir?

Sabah uyandınız ve o gün içinde yapmanız gereken bir çok iş olduğunu fark ettiniz diyelim. Bankaya uğramalısınız, alışveriş yapmalısınız, çocukları okuldan almalısınız, en son olarak da doktora uğrayıp reçete yazdırmalısınız. Bunları halletmek için bir arabaya sahip olabilirsiniz ancak benzin fiyatları ortada. Bu durumda araba sürmeniz gereken mesafenin mümkün olduğunca kısa olması için bunları hangi sırayla yapmalısınız? Matematik ne işe yarar diyenlere bu giriş bir hatırlatma olsun. Çünkü yukarıda aktardığımız senaryo matematikçilerin uzun zamandır üzerinde çalışmalar yaptığı gezgin satıcı problemi ile ilgilidir. Üstelik bu, matematikçileri büyüleyen bir problemdir. Bunun nedeni, genel olarak çözmesi çok zor ve matematikteki cevaplanmamış sorulardan birinin kapısını açmasıdır.

Büyük kargo firmalarının operasyonlarının merkezinde, herhangi bir sürücünün gidebileceği en kısa rotayı belirleme süreci vardır. Bir teslimat rotasında gereğinden bir kilometre daha fazla giden bir sürücü, şirkete yılda milyonlarca liralık zarara mal olur. Her rotayı olabildiğince kısa ve verimli hale getirme işi bu nedenle çok önemlidir. Mümkün olan en iyi rotayı bulma problemi de gezgin satıcı problemi ile ilişkilidir.

Kısacası 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?

Diyelim ki çok sayıda şehre uçmanız gerekiyor. En düşük uçuş maliyetini sağlayacak biçimde bu şehirleri hangi sırayla ziyaret etmelisiniz? Şehirler arası gidişi kuş bakışı olarak kabul edersek aşağıdaki örnek harita ile problem tam olarak anlaşılacaktır. Çizgiler alternatif bir rotayı temsil etmektedir.

Gezgin Satıcı Problemi İle İlgili Sorun Nedir?

Elbette cevap, makul ile ne demek istediğinize bağlıdır. Bir algoritmanın görevini tamamlaması için gereken süre, yürütmesi gereken adım sayısıyla orantılıdır. Belki n tane yer için problemi çözmek için n2 adım atan bir algoritma bulabilirsiniz. Bu, on yeri ziyaret etmek istiyorsanız 100 adım ve 20 yer için 400 adım anlamına gelir. Bu rakamlar size kötü gibi gözüktü ise hazır olun. Bir başka algoritmanın sorunu çözmek için 2n adım attığını hayal edin. O zaman on yer için 1.024 adım gerekecektir. Sayı büyüdükçe de ortaya çıkan adım sayısı korkutucudur.

Matematikçiler, bu bağlamda “makul” bir süre ile ne kastettikleri konusunda net bir fikre sahiptir. Bu nedenle n2, n3 veya n4 gibi n’nin kuvvetlerini içeren ifadelere n’ye bağlı polinomlar denir. Bir algoritma n sayısının büyümesi ile orantılı bir biçimde büyür ise bu makul bir büyüme kabul edilir ve polinom zamanlı algoritma denir. Peki gezgin satıcı problemini çözmek için bir polinom zamanlı algoritma var mı? Cevabı henüz kimse bilmiyor. Henüz hiç kimse ne bulmayı neden olmadığını göstermeyi başaramadı.

NP olarak gösterilen başka bir problem sınıfı ise çözümün polinom zamanda doğrulanabildiği problemleri içerir. Gezgin satıcı problemi bu sınıfa girer. Sonuçta verilen bir rotanın herhangi bir başka rotadan daha kısa olup olmadığı kontrol edilebilir. Bu sınıftaki diğer bir problem, büyük sayıların asal sayılara nasıl çarpanlarına ayrılacağıdır. Bir sayının asal çarpanlarını öğrendikten sonra bunların doğru olup olmadığını kontrol etmek kolaydır. Ancak ilk etapta bu çarpanları bulmak için hiç kimse herhangi bir polinom zamanlı algoritma bilmemektedir.

Bu bizi büyük soruya götürüyor: NP sınıfındaki problemler için henüz keşfedilmemiş herhangi bir polinom zamanlı algoritma var mı? Soru, P’ye karşı NP problemi olarak bilinir, çünkü polinom zamanında çözülebilen problemlerin sınıfına P denir. P=NP problemi matematikteki en zor açık problemlerden biridir. Bu o kadar önemli bir soru ki Clay Matematik Enstitüsü ispatlayabilen kişilere 1.000.000 dolar ödül vaat ediyor.

Gezgin Satıcı Problemi Çözülürse Ne Olur?

quantum-şifreleme
NP problemlerinin cevapları, şifreli mesajların anahtarı olarak kullanılabilir.

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.

Esasen, bir NP sorununun yanıtı (örneğin, büyük bir sayının asal çarpanları), bir mesajın kodunu çözmek için ihtiyaç duyduğunuz anahtar olarak kullanılır.NP problemlerini hızlı bir şekilde çözecek bilinen bir algoritma olmaması, anahtarın kırılmasının çok zor olduğu anlamına gelir. İşte bu nedenle, gezgin satıcı problemini çözmek için verimli bir algoritma bulduğunuz zaman, dünyanın en gizli kodlarının anahtarı olan milyon dolarınızı alacaksınız ve muhtemelen hayatınız artık güvende olmayacaktır. Biri bunun hakkında bir film yapmalı diye düşünebilirsiniz. Aslında yapıldı…

Beyazperdede Gezgin Satıcı Problemi

 Timothy Lanzone tarafından yazılıp yönetilen film bu problem çözülürse dünyamızın nasıl etkileneceğini irdeliyor.

Gezgin Satıcı sorunu 2012 yılında beyaz perdeye de yansıdı. Traveling Salesman adlı bir film, ABD ordusuna P = NP problemine bir çözüm verip vermemeye karar vermesi gereken dört matematikçinin hikayesini anlatıyordu. Matematikçiler ise bu noktada işin ahlaki boyutuna odaklanıyorlardı. Çünkü, ordu çözüme sahip olduğunda dünyadaki herhangi bir kod kırılır hale gelebilirdi. Filmin fragmanına buradan göz atabilirsiniz.


Göz atmak isterseniz


Kaynaklar ve İleri Okumalar:

Matematiksel

Başa dön tuşu