ปัญหาการตัดสินใจและเอ็นพี (ความซับซ้อน)

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ปัญหาการตัดสินใจและเอ็นพี (ความซับซ้อน)

ปัญหาการตัดสินใจ vs. เอ็นพี (ความซับซ้อน)

ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม. ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.

พหุนาม

upright พหุนาม ในคณิตศาสตร์ หมายถึง นิพจน์ที่สร้างจากตัวแปรอย่างน้อยหนึ่งตัวและสัมประสิทธิ์ โดยใช้การดำเนินการแค่ การบวก การลบ การคูณ และการยกกำลังโดยที่เลขชี้กำลังเป็นจำนวนเต็มที่ไม่เป็นลบเท่านั้น ตัวอย่างของพหุนามตัวแปรเดียวที่มี เป็นตัวแปร เช่น ซึ่งเป็นฟังก์ชันกำลังสอง พหุนามสามารถนำไปใช้ในสาขาต่าง ๆ ของคณิตศาสตร์และวิทยาศาสตร์ได้อย่างกว้างขวาง ตัวอย่างเช่น สมการพหุนาม ซึ่งสามารถนำไปใช้ในการแก้ปัญหาได้อย่างกว้างขวาง จากโจทย์ปัญหาพื้นฐาน ไปจนถึงปัญหาที่ซับซ้อนทางวิทยาศาสตร์ และยังใช้ในการนิยาม ฟังก์ชันพหุนาม ซึ่งนำไปใช้ตั้งแต่พื้นฐานของเคมีและฟิสิกส์ ไปจนถึงเศรษฐศาสตร์และสังคมศาสตร์ รวมถึงการนำไปใช้ในแคลคูลัส และการวิเคราะห์เชิงตัวเลข ซึ่งคล้ายคลึงกับฟังก์ชันต่าง ๆ ในคณิตศาสตร์ขั้นสูงนั้น พหุนามยังใช้ในการสร้างวงล้อพหุนาม และความหลากหลายทางพีชคณิต และเป็นแนวคิดสำคัญในพีชคณิต และเรขาคณิตเชิงพีชคณิตอีกด้ว.

ปัญหาการตัดสินใจและพหุนาม · พหุนามและเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »

ทฤษฎีความซับซ้อนในการคำนวณ

ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).

ทฤษฎีความซับซ้อนในการคำนวณและปัญหาการตัดสินใจ · ทฤษฎีความซับซ้อนในการคำนวณและเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »

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

ปัญหาความสอดคล้องแบบบูล หรือ SAT (Boolean satisfiability) เป็นปัญหาการตัดสินใจอย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete) ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ 2SAT \in P หรือหากจะพูดให้ชัดเจนกว่านั้น 2SAT \in NL \subseteq P (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น).

ปัญหาการตัดสินใจและปัญหาความสอดคล้องแบบบูล · ปัญหาความสอดคล้องแบบบูลและเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »

เอ็นพี (ความซับซ้อน)

ในทฤษฎีความซับซ้อนในการคำนวณ กลุ่มปัญหา เอ็นพี (NP: Non-deterministic Polynomial time) สามารถนิยามได้สองวิธี ซึ่งเราสามารถพิสูจน์ได้ไม่ยากนักว่านิยามทั้งสองแบบนี้สมมูลกัน.

ปัญหาการตัดสินใจและเอ็นพี (ความซับซ้อน) · เอ็นพี (ความซับซ้อน)และเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »

เซต (แก้ความกำกวม)

ซต สามารถหมายถึง.

ปัญหาการตัดสินใจและเซต (แก้ความกำกวม) · เซต (แก้ความกำกวม)และเอ็นพี (ความซับซ้อน) · ดูเพิ่มเติม »