P ve NP Karmasikligi

P-NP Problemi

P-NP Problemi (P versus NP olarak da gecer) Matematik ve Bilgisayar Bilimlerinde halen cözülemeyen bir Problemdir. Özellikle Karmasiklik Teorisinde.

Asil merak edilen sey ise P ve NP arasinda ki karsilikli iliskinin ne oldugudur aslinda. 1970li yillarda birbirinden bagimsiz calisan Stephan Cook ve Leonid Levin tarafindan ilk defa üzerine gidilmistir.

P-NP Problemi Bilgisayar Biliminde Clay Mathematics Institute tarafindan Millenium Problemlerinden biri olan ve halen cözülemeyen bir Sorudur.

P ve NP

Karmasiklik Teorisi sorunu ortaya koymakla beraber Bilgisyarlar tarafindan da hesaplanabilindigini ….

https://de.wikipedia.org/wiki/P-NP-Problem#P_und_NP

P

P, Karmasiklik Teorisinde Problem kategorilerinde Karmasiklik Sinifidir.

Bu Sinifin icindeki her Problem icin bir deterministik Turing Makinesi mevcuttur. (Bir Algoritma ile yada Programlama ile bu Problemi cözen ve bir n^k seklinde bir Polinom (k bir sabittir)) ile Zaman Karmasikligi ile cözen ve Durumu n uzunlugunda sinirlandirir.

P sinifinda ki Problemler böylelikle deterministik ve Polinomial zamanda cözülebilirler.

Örnek olarak vermek gerekirse: Siralama Problemleri ve Devre Analiz Problemleri.

NP

Karmasilik Teorisi deterministik Turing Makinesinden baska Makinelerle de tanimlanmaktadir.
Ein önemlilerinden biri deterministik olmayan Turing Makineleridir, deterministik olanlarin gelistirilmis hali gibi.

Deterministik olmayan Turing Makineleri her Zaman diliminde potansiyel olarak daha cok Özellige sahiptir.
Hesaplamalari , Islem adimlari tam olarak takip edilemezdirler.

Bu yüzden teorik bir Modell olarak kabul edilir. Suan ki Bilgisayarlarda kullanilmamaktadir.

NP Karmasiklik Sinifi tam olarak deterministik olmayan Turingmakinalarini Polinomiel Zamanda cözülebilen Problemleri kapsar.

P Sinifinda ki Problemler deterministik olamayan Polinomial Zamanda da cözülebildiklerinden, P ayni zamanda NP sinifinin bir Altkümesidir.

P_NP_Karmasiklik