np-complete

• en meşhur örneklerinden ikisi traveling salesman ve hamilton cycle olan problemler kümesini de tanımlayan terimdir.
• carpanlara ayirmak da boyle bir problemdir. bir cok iste kullanilan rsa encryption da bu gercege dayanmaktadir.
• np complete problemlerde complexity arttikca hesaplama zamani limitsiz arttiginda bu tur problemler gunumuz hesaplama (computation) methodlarina gore hesaplanamaz olarak da belirtilir.
  
  gerci quantum computerlarin rsa gibi bazi np complete problemlerin hakkindan geldigi gorulmustur.
• ayrica bu siniftaki bir problemin polinomsal algoritmasinin bulunmasi demek, diger tum problemler icinde bir polinomsal algoritma bulmak demektir, cunku np-complete olan her problem deterministik bir algoritmayla polinom zamanda birbirine donusturulebilir.
• x problemi np sınıfındaysa ve np sınıfındaki tüm problemler x problemine polinom zamanda indirgenebiliyorsa
  bu x np complete tir.
• (bkz: np problem indirgemeleri)
• aslinda tam dogru soylemek gerekirse, traveling salesman np-complete degil, np-hard sinifina giren bir problemdir. bu da travaling salesman problemine deterministik olarak p zamanda cozen bir insanin yine p zamanda diger tum np-complete problemleri de cozebilecegi anlamina gelir. ancak bu ifadenin tersi dogru olmak zorunda degil.
  quantum bilgisayarlarin bile isin icine girmesi bugune kadar np?=p sorusuna yeni bir acilim getiremedi. rsa'nin cozumu olarak bahsedilen carpanlara ayirma probleminin quantum algoritmalari ile polinom adimda cozulebildigi dogru. sorun, bu carpanlara ayırma algoritmasının np-complete olduğunun bugüne kadar gösterilememiş olması.
  dolayısıyla tekrar edelim, carpanlara ayırma np-complete bir problem degildir. (en azından bugüne kadar oyle olduğu gösterilemedi ve quantum np != quantum p önermesi doğru ise, asla da gösterilemez).
• (bkz: aa nasil cozdun o problemi)
  (bkz: 40 yil dusunsem aklima gelmezdi valla)
  (bkz: self awareness) (bkz: cognitive science)
  (bkz: computability)
• hesaplama teorisinde (theory of computation) polinom zamanli problemler zaman kullanimi acisindan verimli kabul edilir. deterministic polinom zamanda cozulemeyen problemler (non-deterministic polinomial ya da kisaca np) icin ise ayni sey soylenemez. bunlar icin deterministik eksponansiyel zamanli algoritmalara sahibiz. np problemler icin deterministik polinom zamanli algoritmalar surekli olarak arastirilmaktadir.
  
  np-complete problemler ise np problemlerin bir alt kümesi olmakla birlikte geri kalan np problemlerden farkli olarak degisik bir ozellik barindirir. butun np problemler np-complete kümesinden herhangi bir probleme deterministik polinom zamanda cevrilebilir. bu durumda np-complete problemler, polinom zamanli algoritma arayisinda arastirmacilarin odagi haline gelmistir. oyleki, eger herhangi bir np complete problem icin deterministik polinom zamanli bir algoritma bulunursa, bu demek olur ki np kümesindeki butun problemler icin aslinda deterministik polinom zamanli bir cozum vardir. nasil mi? herhangi bir np problemi once deterministik polinom zamanda bahsi gecen np-complete probleme cevirir, daha sonrada bu problemi deterministik polinom zamanda cozeriz dolayisiyla np problem icin deterministik polinom zamanli bir cozum bulmus oluruz. eger tek bir np-complete problem deterministik polinom zamanda cozulebilirse bilgisayar bilimi acisindan cok ciddi bir devrim olacagi ve bunu basaran kisinin o sene turing odulunu alacagi kesindir.
• eger bir dil np sinifinda ise ve np hard olma kosulunu sagliyorsa o dil np complete sinifindadir.