np-complete

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