şükela:  tümü | bugün soru sor
  • matematik veya bilgisayarla alakalı olmayıp, felsefi bir tartışma konusudur. araştırmalar sürmektedir.
  • herhangi bir algoritmayla optimal sonucuna ulaşilamayan problemlerdir.
  • bir dilin np hard olabilmesi icin np sinifindaki her dilin o dile polinom zamanda indirgenebilir olmasi gerekir.
  • np complete problemlerin maksimizasyon/optimizasyon versiyonlarının dahil olduğu problem kümesi. en büyük clique, en kısa hamilton yolu* gibi. polinomsal doğrulayıcıları* bilinmemektedir.
  • felsefe np-hard problem sınıfına girer. sürekli sorarak bilinmeyenin en iyisi aranır, ama bilim gibi net bir sonuca ulaşılmaz. dünya üzerinde şimdiye kadar, üzerine kafa yorulan felsefik konuların neredeyse hiçbirinde en iyi sonuca ulaşılmamıştır. herhangi bir filozofun üzerine kafa yorduğu belli bir konuya/probleme farklı zamanlarda başka filozoflar farklı yaklaşımlarla eğilerek çıtayı bulunduğu noktadan yukarıya çıkarmışlardır. aynı problem kümesine farklı yöntemlerle, bazen de melez fikirlerle çözüm aranmıştır. henüz herkesin mutabık olacağı bir düşünce ortaya konmadığından polinom zamanda çözümü zaten mümkün olmamıştır. çünkü fikirler, ideolojiler, vs. bünyesinde sayısız bilinmeyeni barındırır, aynı zamanda boyutu her an değişen bir büyüklüğe sahiptir.
    düşünmeye başlayınca, sormak için ağzınızı açtığınızda, problemin çözümü için en kıymetli makineniz olan beyninizi çalıştırmaya başlamışsınız demektir. optimum sonuca ulaşamasanız da sizin için iyi olana, kabul edilebilire razı olur köşenize çekilirsiniz. benden bu kadar, başkaları da kafa yorsun dersiniz. haklısınız.
  • np-hard problemlerini anlamak için p, np ve np-complete kavramlarını anlamak gerekir. derin bir nefes alarak başlayalım:

    p, polynomial'in baş harfini temsil eder. p(x) = x^3 + 5x gibi polinomlar. bir sorunu çözmek için polinomsal bir zamana ihtiyaç duyuyorsanız bu iyi bir haberdir, problem çözülebilir bir boyutta demektir. diğer taraftan exponential complexity'ye sahip bir problemi çözmeye çalışınca işler karışıyor.

    bu iki zamansal kavramı anlamak önemli, çünkü tam da bu fark bize p vs. np mileniyum problemini anlatıyor. p ve np'nin ikisi de problemler kümesidir, p np'nin alt kümesidir. yani her p problemi ayrıca bir np problemidir. peki tam olarak neyi temsil eder bu kümeler?

    polinomsal ve exponensiyel zaman gerektiren problemlerin farkından bahsettik. p problemleri çözümü günümüzde insancıl zamanlarda realize edilebilen, yine elimizde olan süper bilgisayarlarla kolaylıkla alt edilebilecek problemlerdir. örneğin rubix cube. zeka küpünün boyutları ne olursa olsun, komplex bir bilgisayar o kübü çözebilecek durumdadır ve bunun için net bir algoritma mevcuttur. gelin bir de sudoku'ya bakalım. klasık 9x9 sudokuyu bilgisayarlar hızlı bir şekilde çözebilir. 11x11, 15x15... peki sudokunun çok büyük boyutları olduğunu varsayalım. n x n boyutunda. işte burada işler biraz sarpa sarıyor, çünkü günümüz bilgisayarları bu büyüklükteki bir problemi çözemiyor, küçük sudokular için mevcut algoritmaların uygulanması için gereken zaman problemin büyüklüğü ile exponensiyel bir şekilde artıyor. işte böyle problemlerin bulunduğu kümeye np diyoruz.

    peki neden her p problemi np kümesinin içinde?

    np içinde yer alan problemlerden biri için cevabınız var diyelim. büyük bir n sayısı için n x n sudokusunu çözdünüz ve bunun doğruluğunu tespit etmek istiyorsunuz. bu tespit bir bilgisayarın fazla zamanını almayacaktır, yapması gereken tek şey her satır ve sütunda n dahil olmak üzere n'e kadar olan doğal sayılardan her birinin yalnızca bir defa yazılmış olmasını kontrol etmektir. np problemlerinin ortak yönü budur, her biri için 0'dan bir çözüm bulmak mümkün değildir fakat elinizde bir çözüm bulunduğu zaman bunun doğruluğunu kontrol etmek sadece polinomsal bir zaman gerektirir. her p problemi için de bunu yapabileceğinizden dolayı alt küme ilişkisi ortaya çıkar.

    mileniyum sorularından biri olan p=np denkleminin doğruluğunu veya yanlışlığını kanıtlamak ise zordur. denklemin tanımladığı ise şudur; her np problemi p problemine indirgenebilir mi? her problem için polinomsal zamanda çözülebilir bir algoritma bulunabilir mi? bilgisayar bilimcilerin uzun yıllardan beridir çözmeye çalıştığı bir problemdir ve çoğunluk denklemin eşitsizliğinden yanadır.

    bu iki küme için de önemli bir ortak nokta şudur: ikisi de decision problems ile ilgilenir. problemlerinizin cevabı evet veya hayır'dır. örneğin,

    "bu zeka küpü çözülebilir mi? (p)" "bu sudoku çözülebilir mi? (np)" "n ve m olarak karakterize edilmiş iki sayı için, 1 ve m arasında bulunan ve n'i bölen bir f sayısı var mıdır? (np)"

    np-complete kümesi ise np kümesindeki bir problem setini tanımlamak için kullanılır. bu problem setinin özelliği ise şudur: np kümesindeki diğer her problem bu kümedeki problemlere indirgenebilir. yani eğer np-complete içindeki bir problemin çözümü bilinirse, o halde diğer np problemleri de çözülebilir. örneğin, boolean bilinmeyenlerle oluşturulmuş bir denklem için doğruluğu kanıtlanabilir bir model bulunup bulunmayacağı np-complete kümesi içindedir (bkz: sat) (bkz: boolean satisfiability problem).

    bu kümeyi önemli kılan ise, içindeki problemlerden birine polinomsal bir çözüm bulunduğu taktirde diğer np problemlerinin her birine polinomsal bir çözüm bulunacağıdır.

    gelelim np-hard kümesine. buradaki problemlerin çözümü en az np-complete kümesindekiler kadar zordur. diğerlerinden farkı ise decision problem'lardan oluşma zorunluluğu taşımamasıdır. np-complete kümesindeki problemler np-hard kümesindekilere indirgenebilir. burada da aynı şey geçerli: eğer içindeki problemlerden birine polinomsal bir çözüm bulunduğu taktirde diğer np problemlerinin her birine polinomsal bir çözüm bulunacaktır. np-complete'ten bir diğer farkı ise sadece np problemlerinden oluşmuyor olduğudur. bu kümedeki problemlerin hepsi çok zor olduğundan, birini çözüp np problemleri açığa kavuşturmak şimdilik imkansız görünüyor.