ดูต้นฉบับสำหรับ ปัญหาความสอดคล้องแบบบูล

{{ต้องการอ้างอิง}}
{{ลิงก์ไปภาษาอื่น}}
'''ปัญหาความสอดคล้องแบบบูล''' หรือ '''SAT''' ({{langx|en|Boolean satisfiability}})  เป็น[[ปัญหาการตัดสินใจ]]อย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้าน[[ทฤษฎีความซับซ้อนในการคำนวณ]] ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ [[นิพจน์บูลีน]] (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ  ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ 

ในกรณีที่เราสามารถกำหนด[[ค่าความจริง]]ให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น '''สามารถทำให้เป็นจริงได้''' (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหา[[เอ็นพีบริบูรณ์]] ([[:en:NP-complete|NP-complete]]) 

ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ใน[[รูปมาตรฐานแบบเชื่อม]] (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละ[[ประพจน์เลือก]] (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน  อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา [[ปัญหา 2-SAT|2-SAT]]) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ <math>2SAT \in P</math> หรือหากจะพูดให้ชัดเจนกว่านั้น <math>2SAT \in NL \subseteq P </math> (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น) 

== ความยากของปัญหา ==
{{โครงส่วน}}

== ขั้นตอนวิธีที่ใช้สำหรับปัญหา == 
{{โครงส่วน}}
{{โครงคอม}}

[[หมวดหมู่:ทฤษฎีการคำนวณ]]
[[หมวดหมู่:พีชคณิตแบบบูล]]