Bool Tatmin Problemi

Yazan : Şadi Evren ŞEKER

Litartürde, Boolean Satisfiability Problem olarak geçen ve boole cebirindeki denklemlerin doğruluğunun sağlanması olarak özetlenebilecek olan problemdir. Ayrıca çeşitli kaynaklarda bu probleme, problemin İngilizce tanımında geçen Satisfiability kelimesinin kısaltması olan SAT kelimesi olarak da rastlanabilir.

Bu problemi, bilgisayar bilimleri açısından ilginç kılan yanı ise, problemin yapısal olarak bir NP-Tam (NP-Complete) sınıfı problem olmasıdır.

Boole Cebiri, aslında mantıksal bir gösterim ifade etmektedir. Dolayısıyla mantıktaki karşılığı olarak probleme önermeler mantığı (propositional logic, kaziye mantığı) tatmin problemi ismi de verilebilir.

Boole cebirinden alışıldığı üzere mantıksal kurgu için tanımlı olan ve bilgisayar bilimlerinde değişken (variable) olarak isimlendirilebilecek belirticiler (literal, lafziler) bulunmaktadır. Bunlar basit birer sembol ile gösterilir.

Örneğin x ile gösterilen bir sembol çoğu zaman gerçek hayattaki bir kaziyeyi (önerme, proposition) ifade etmektedir.

Bu lafzi gösterimlerin (literal, belirticiler) üzerinde tanımlı ve yine boole cebiri içerisinde kabul edilebilecek işlemler (operators) tanımlanabilir. En sık kullanılan bool cebiri işlemleri ve(and), veya (or), tersi (not) şeklinde sayılabilir. Bu işlemler kullanılarak kurulan bir dizilimin sonucunun yine bir lafzi gösterim (literal) cinsinden elde edilmesi ve ya doğru (true) ya da yanlış (false) olması beklenir.

Bu tanımın üzerine örneğin sadece 3 adet lafzi gösterim (literal)’in ve (and) bağlacı normal şeklinde (conjunction normal form) olması durumuna 3SAT veya 3CNFSAT isimleri verilir. Bu problem NP-TAM (NP-Complete) bir problemdir.

Benzer tanım sadece 2 adet lafzi gösterim’in (literal) ve bağlacı normal şeklinde (conjunction normal form) olması durumuna ise 2SAT veya 2CNFSAT ismi verilir ve bu problem de NL-Tam (NL-Complete) bir problemdir.

Boole tatmin probleminin diğer önemli bir yanı da tarihsel olarak, 3SAT problemlerin, ilk NP-Complete problem olmasıdır. Bu konuda çalışan Stephen Cooke 1971 yılında bu problem grubunun NP-Complete olduğunu göstermiştir.

Ayrıca boole tatmin probleminin birinci derece mantık (First order predicate calculus) içerisindeki çözümünün aranması da ayrıca bir problemdir.

Bilindiği üzere birinci derece mantığın, üzerinde tanımlı olduğu lafzi gösterimler (literals) için bir takın etki alanı tanımlamaları (domain) mümkündür. Bu tanımlamalar ile verilen bir boole cebiri, diziliminin çözümlenmesi bir seviye daha karmaşık hale gelmektedir.

Örneğin aşağıdaki problemin çözümünü bu anlamda değerlendirebiliriz:

∃a (Şadi (a) ∧ Mühendis(a)) → Öyle bazı a’lar vardır ki, bu a’nın ismi Şadi’dir ve bu a mühendistir.

Bu tip birinci derece mantık dizilimlerinin çözüm karmaşıklığı Co-NP problem olarak geçmektedir.

Yorumlar

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir