NP (karmaşıklık) sayfasının kaynağını görüntüle

[[Dosya:Complexity classes.svg|küçükresim|P ve NP karmaşıklık sınıflarının bir diagramı]]
Nen [[karar problemi|karar problemlerini]] içeren [[karmaşıklık sınıfı]]dır.

Bu sınıftaki problemler belirli [[Turing Makinesi]] ile çokterimli zamanda doğrulanabilirler ve bu şekilde doğrulanabilen her problem NP sınıfındadır. Bu nedenle NP, (belirli [[Turing Makinesi]] ile) çokterimli zamanda doğrulanabilen problemlerin sınıfı olarak da tanımlanabilir.

Belirli Turing makinesi aynı zamanda belirsiz Turing makinesi olduğundan, [[P (karmaşıklık)|P]] sınıfındaki bütün problemler aynı zamanda NP'dedir.
== NP-Zor ==

En az her bir NP problem kadar ''zor'' olan problemlerin bulunduğu sınıfa '''NP-Zor''' (NP-hard) denir. Daha resmi bir şekilde,

:<math> \mbox{NP-Zor}=\{ H~|~\forall L \in \mbox{NP},  L \leq_p H \} </math>

Burada <math>L \leq_p H </math>, ''L'' probleminin, ''H'' problemine [[çokterimli zamanda indirgeme|çokterimli zamanda indirgenebildiği]] anlamına gelir.

Bir başka deyişle, NP-Zor sınıfındaki herhangi bir problem çok terimli zamanda çözülebilirse, NP sınıfındaki bütün problemler çok terimli zamanda çözülebilir.

== NP-Tam ==

NP-Tam (NP-complete), hem NP olup hem NP-Zor olan problemlerin sınıfıdır. Dolayısıyla bu sınıftaki problemler NP sınıfının en zor problemleridir. Yukarıdaki tanımdan yola çıkarak, herhangi biri çokterimli zamanda çözülebilirse, bütün hepsi çok terimli zamanda çözülebilir.

=== NP-Tam örnekleri ===

* [[İkilik tatmin edilebilirlik]] (CNF-SAT)
* [[Dolaşan satıcı]] (TSP)
* [[Hamilton dönüşü]] ve [[Hamilton yolu]]
* [[Hamilton yolu problemi]]
* [[Cook-Levin teoremi]]
* [[Alt küme toplamı problemi]]
* [[Bağımsız küme problemi]]
* [[Düğüm kapsama problemi]]

Bunlardan CNF-SAT ya da kısaca SAT, tarihsel olarak NP-Tam olduğu ispatlanan ilk problemdir.

== İlgili bağlantılar ==

* [[Karmaşıklık]]
* [[P ile NP arasındaki ilişki]]

[[Kategori:Karmaşıklık teorisi]]