เร็วกว่าเบราว์เซอร์!
4 ความสัมพันธ์: ทฤษฎีความซับซ้อนในการคำนวณค่าความจริงปัญหาการตัดสินใจเอ็นพีบริบูรณ์
ทฤษฎีความซับซ้อนในการคำนวณ
ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).
ใหม่!!: ปัญหาความสอดคล้องแบบบูลและทฤษฎีความซับซ้อนในการคำนวณ · ดูเพิ่มเติม »
ค่าความจริง
ค่าความจริง (Truth value) ในทางตรรกศาสตร์และคณิตศาสตร์ หมายถึง ค่าที่ใช้บ่งบอกว่าประพจน์ใดเป็นความจริง ในเรื่องของตรรกศาสตร์แบบฉบับ (classical logic) ค่าความจริงมีเพียงสองอย่างเท่านั้นคือ ค่าจริง (true) และค่าเท็จ (false) แต่สำหรับตรรกศาสตร์คลุมเครือ (fuzzy logic) หรือตรรกศาสตร์หลายค่า (multi-valued logic) ค่าความจริงอาจจะมีค่าอย่างอื่นที่นอกเหนือจากนั้นก็ได้ เซตของค่าความจริง ทำให้เกิดพีชคณิตแบบบูล (Boolean algebra) ซึ่งคำนวณด้วยวิธีที่คล้ายพีชคณิตแล้วให้ผลเฉพาะในเซตเท่านั้น ส่วนพีชคณิตแบบอื่นอาจมีการใช้เซตของค่าความจริงในตรรกศาสตร์ที่ไม่ได้เป็นแบบฉบับ ตัวอย่างเช่น ตรรกศาสตร์สหัชญาณนิยม (intuitionistic logic) หรือพีชคณิตเฮย์ทิง (Heyting algebra) เป็นต้น ในการเขียนโปรแกรม คอมพิวเตอร์จะให้ความหมายของค่า 0 เป็นค่าเท็จ และค่าอื่นที่ไม่ใช่ 0 (รวมทั้ง 1) หมายถึงค่าจริง และภาษาโปรแกรมบางภาษาอาจมีค่าว่าง (null) อยู่ด้วย ซึ่งไม่ใช่ทั้งค่าจริงและค่าเท็จ หมวดหมู่:ตรรกศาสตร์.
ใหม่!!: ปัญหาความสอดคล้องแบบบูลและค่าความจริง · ดูเพิ่มเติม »
ปัญหาการตัดสินใจ
ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.
ใหม่!!: ปัญหาความสอดคล้องแบบบูลและปัญหาการตัดสินใจ · ดูเพิ่มเติม »
เอ็นพีบริบูรณ์
อ็นพี เอ็นพีบริบูรณ์ และเอ็นพีแบบยาก สำหรับทั้งสองกรณีที่พีเท่ากับเอ็นพี และพีไม่เท่ากับเอ็นพี ในทางทฤษฎีความซับซ้อนในการคำนวณ เอ็นพีบริบูรณ์ (NP-complete.) เป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี กล่าวคือปัญหาใด ๆ ในกลุ่มปัญหา เอ็นพี สามารถลดรูป (Reduce) มาเป็นปัญหาใน เอ็นพีบริบูรณ์ ได้ แม้ยังไม่ได้รับการพิสูจน์แต่เชื่อกันว่าเป็นกลุ่มปัญหาที่ไม่น่าจะมีขั้นตอนวิธีที่มีประสิทธิภาพใช้แก้ไขได้ ปัญหาในกลุ่มเอ็นพีบริบูรณ์สามารถเปลี่ยนแปลงไปมาเป็นปัญหาอื่นในกลุ่มเดียวกันได้ด้วย polynomial time ดังนั้นการที่มีขั้นตอนวิธีที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งในเอ็นพีบริบูรณ์ ส่งผลให้เราสามารถแก้ปัญหาทั้งหมดในกลุ่มเอ็นพีได้อย่างมีประสิทธิภาพ กลุ่มความซับซ้อนเอ็นพีบริบูรณ์ในบางครั้งถูกเรียกสั้น ๆ ว่า NP-C.
ใหม่!!: ปัญหาความสอดคล้องแบบบูลและเอ็นพีบริบูรณ์ · ดูเพิ่มเติม »
