np-complete

• 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.
• 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.
• (bkz: aa nasil cozdun o problemi)
  (bkz: 40 yil dusunsem aklima gelmezdi valla)
  (bkz: self awareness) (bkz: cognitive science)
  (bkz: computability)
• 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).
• bu problemi bilgisayarla cozebileceginizi dusunuyorsaniz zaten hic yanina bile yaklasmamaniz gereken problemdir.
• deterministik olmayan turing makinesi ile polinomal zamanda cozulebilecegi iddia edilen degil, cozulebilecegi bilinen problemlerdir.
  
  ornek vermek gerekirse, set kaplama problemi bilinen bir np-complete bir problemdir.
  deterministik olmayan bir turing makinesi,
  1. random bir set kumesi sec.
  2. kumenin evren setini kaplayip kaplamadigini kontrol et.
  
  seklinde 2 adimli bir algoritma ile problemi dogru sekilde cozebilir.
  
  bu algoritmanin tamamlanma suresi evren kumesindeki n elemanla dogrusal iliskili oldugundan, tamamlanma suresi o(n) olarak yukaridan sinirlanir. bu da np-complete problemlerin deterministik olmayan turing makinesi ile polinomal zamanda cozulecegini kanitlar.
• olayla alakalı şöyle de bir şey var.
  
  http://xkcd.com/287/
• (bkz: np problem indirgemeleri)
• 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.
• http://en.wikipedia.org/wiki/np-complete
  
  adresinde ek bilgi var.