ปัญหาความสอดคล้องแบบบูล - วิกิพีเดีย

# ปัญหาความสอดคล้องแบบบูล

### จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

## [แก้] ความยากของปัญหา

## [แก้] อัลกอริทึมที่ใช้สำหรับปัญหา

## [แก้] อ้างอิง

| ปัญหาความสอดคล้องแบบบูล เป็นบทความเกี่ยวกับ คอมพิวเตอร์ อุปกรณ์คอมพิวเตอร์ หรือ เครือข่าย ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น

ข้อมูลเกี่ยวกับ ปัญหาความสอดคล้องแบบบูล ในภาษาอื่น สามารถหาอ่านได้จากเมนู ภาษาอื่น ๆ ด้านซ้ายมือ
ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%9B/%E0%B8%B1/%E0%B8%8D/%E0%B8%9B%E0%B8%B1%E0%B8%8D%E0%B8%AB%E0%B8%B2%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%AA%E0%B8%AD%E0%B8%94%E0%B8%84%E0%B8%A5%E0%B9%89%E0%B8%AD%E0%B8%87%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%9A%E0%B8%B9%E0%B8%A5.html".

หมวดหมู่: บทความเกี่ยวกับ คอมพิวเตอร์ ที่ยังไม่สมบูรณ์ | ทฤษฎีการคำนวณ

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Deutsch
- English
- Español
- Français
- עברית
- 日本語