P, NP’ye Karşı

Teorik bilgisayar bilimleri ya da matematik ile ilgilenenler için ACM’in Communications dergisinin Eylül sayısında “The Status of the P Versus NP Problem” başlıklı, P ve NP problemleri üzerine yeni bir makale yayınlandı. Makaleye buradan ulaşabilirsiniz.

Daha önce duymuş olabilirsiniz, P, etkin bir çözüme sahip problem kümesini gösteriyor. Etkin çözümden kasıt, problemi çözen algoritmanın bir bilgisayar üzerinde çalıştırıldığında makul bir zaman dilimi içinde bir çözüm üretmesidir. Dolayısıyla bir P probleminin çözümü, girdisinin polinom şeklindeki bir ifadesiyle verilebilir. Fakat NP problemleri ise farklıdır. Şöyle ki: Eğer bir NP problemine bir çözümünüz var ise bu çözümün etkin olup olmadığını makul bir zaman dilimi içinde anlayabilirsiniz ama yeni bir çözümünü makul bir zaman dilimi içinde bulamazsınız. Bu yüzden bu tür problemlerin çözümleri, girdinin bir polinomsal ifadesi (nondeterministic Polynomial) olarak gösterilemezler ve bu yüzden de NP olarak adlandırılırlar.  Yani bu problemler çözümsüz değillerdir, sadece çözümleri, ciddi bir miktarda girdi için modern super-scalar makinalar üzerinde bile çok rahatlıkla ayları,  yılları ya da yüzyılları alabilir.

“Gezgin satıcı problemi” (traveling salesman problem) gibi mühendislikteki pek çok problem bu cinstendir. Çoğu zaman gündelik hayatımızda karşılaştığımız, mesela bir düğüne gelecek davetlilerin belli kısıtlar altında oturma planını çıkarmak gibi işler, aslında bu tür problemlerdendir. Biz genel olarak bu tür problemleri, hayatımızda karşılaşınca, deneme-yanılma (heuristically) yoluyla çözeriz, çünkü çoğu zaman girdi sayısı küçüktür.

Bu makale “P, NP’ye eşit değildir” iddiasını ispatlamaya çalışan yaklaşımları ele alıyor. Çünkü eğer P, NP’ye eşit olsaydı, hayatımız çok kolaylaşırdı, değil mi? Bilim adamlarının kanısı, bu iki problem kümesinin farklı olduğu yönünde.

Bu arada NY Times’ın haberine göre Clay Mathematics Institute,  P-NP probleminin çözümü için $1 milyon değerinde bir ödül koymuş durumda. Kuruma göre bu problem, bin yılın yedi probleminden birisi.

Bence bu makaleyi hemen okuyup, bu ödülü kapmaya başlamak için çalışmakta fayda var. 🙂 Bu arada haberi ve makaleyi bana bildiren, geleceğin bilgisayar bilimcisi, oğlum Selman’a da teşekkürler. 🙂

Linkler:

• http://bahtiyarhoca.com/2008/12/matematigin-iyiyse-1-milyon-dolar-kazanabilirsin/
• Matematik Dünyası’ndan güzel bir makale

Toplam görüntülenme sayısı: 2840