Vikipedi

Cook-Levin teoremi: Revizyonlar arasındaki fark

Etkileşimli olarak geçmişe göz at
[kontrol edilmiş revizyon][kontrol edilmiş revizyon]
← Önceki sürümle aradaki farkSonraki sürümle aradaki fark →
İçerik silindi İçerik eklendi
GörselVikimetin
→‎İspat: düzeltme AWB ile
11. satır:
:<math>SAT=\left\{\langle\varnothing\rangle\vert\varnothing\, \text{dogrulanabilir boolean ifadedir}\right\}</math>
 
Örneğin <math>\varnothing=\left(\bar x\andland y\right)\orlor\left(x\andland z\right)</math> gibi herhangi bir boolean ifadenin sonucunun doğru olmasını inceleyen probleme SAT problemi denir.Bu örnekte x=doğru, y=yanlış, z= doğru için problem doğrulanabilirdir.
 
== NP-Tam Sınıfı ==
49. satır:
x<sub>i,j,s</sub> : ∅ formülünün değişkeni olup tablonun [i,j] gözünde s değeri varsa doğru yoksa yanlış değerini alır.
 
:<math>\begin{array}{l} \bigvee_{s\in C}x_{i,j,s}=x_{i,j,s_1}\andland x_{i,j,s_2}\andland\ldots\andland x_{i,j,s_l} \\ C=\{s_1,s_2,\ldots,s_l\} \end{array}</math>
 
Şimdi F ifadesinin ne gibi koşulları sağlaması gerektiğine bakalım.
"https://tr.wikipedia.org/wiki/Cook-Levin_teoremi" sayfasından alınmıştır