np-complete

• 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).