![[DEV]AB](/data/avatars/s/2135/2135420.jpg?1657747839){kind=avatar}
Türkiye'de ilk Mobil & PC Aynı Anda Metin2 Oyna. Triarchonline kalıcı ve uzun ömürlü yapısı ile 24 Temmuz'da açılıyor. | 1-99 Mobil Metin2 Triarch HEMEN TIKLA!
Giriş
Başlıkta adları anılan problemlerinin dataylarına ve indirgeme işlemine başlamadan önce, öncelikle konu anlatılması sırasında birkaç tanım üzerinde durulacak. Sonra bu problemlerin yer aldığı sınıf özellikleri ve birbirinin cinsine çevirilme işlemleri yapılacak.
İndirgeme: A problemi B problemine indirgenebiliyorsa, B problemin çözümü Anın çözümü için kullanılabilir.
Karmaşıklık, anlaşılması zor parçalardan oluşan bir sistemi tanımlama yöntemidir.
Karmaşıklık Kuramı sırasında ise, çözümleri zor olan problemerlerin birbirine indirgeyerk çözümlerini kolaylaştırılmaya çalışılıyor. Bununla ilgili olan P =? NP sorusunun cevabı da, aynı şekilde ilk başta problemleri indirgeyerek basitleştirmeye çalışılır, sonra da çözümleri olan problemleri kullanarak daha karmaşık olanların çözümlerine bakılır. Bu şekilde P ve NP sınıflarındaki problemleri arasında bir ilişki bulunursa, çözüme dogru gidebiliriz.
NP sınınfında problemlerini çözmek için de, aynı şekilde indirgemeye başvurulur ama bu defa Çokterimli zamanda indirgeme olur.
Polinom Zamanda İndirgeme
A dili B diline polinom zamanda indirgenebilir A \le p B, ancak ve ancak f : \Sigma^* \rightarrow \Sigma^* diye polinom zamanda çalışan bir hesaplama funksiyonu varsa ve her w için w \in A \iff f(w) \in B geçerlidir.
Başlıkta adları anılan problemlerinin dataylarına ve indirgeme işlemine başlamadan önce, öncelikle konu anlatılması sırasında birkaç tanım üzerinde durulacak. Sonra bu problemlerin yer aldığı sınıf özellikleri ve birbirinin cinsine çevirilme işlemleri yapılacak.
İndirgeme: A problemi B problemine indirgenebiliyorsa, B problemin çözümü Anın çözümü için kullanılabilir.
Karmaşıklık, anlaşılması zor parçalardan oluşan bir sistemi tanımlama yöntemidir.
Karmaşıklık Kuramı sırasında ise, çözümleri zor olan problemerlerin birbirine indirgeyerk çözümlerini kolaylaştırılmaya çalışılıyor. Bununla ilgili olan P =? NP sorusunun cevabı da, aynı şekilde ilk başta problemleri indirgeyerek basitleştirmeye çalışılır, sonra da çözümleri olan problemleri kullanarak daha karmaşık olanların çözümlerine bakılır. Bu şekilde P ve NP sınıflarındaki problemleri arasında bir ilişki bulunursa, çözüme dogru gidebiliriz.
NP sınınfında problemlerini çözmek için de, aynı şekilde indirgemeye başvurulur ama bu defa Çokterimli zamanda indirgeme olur.
Polinom Zamanda İndirgeme
A dili B diline polinom zamanda indirgenebilir A \le p B, ancak ve ancak f : \Sigma^* \rightarrow \Sigma^* diye polinom zamanda çalışan bir hesaplama funksiyonu varsa ve her w için w \in A \iff f(w) \in B geçerlidir.
