5 ความสัมพันธ์: พี (ความซับซ้อน)กลุ่มความซับซ้อนทฤษฎีความซับซ้อนในการคำนวณปัญหาการตัดสินใจเครื่องทัวริง
พี (ความซับซ้อน)
ในเชิงของ ทฤษฎีความซับซ้อนในการคำนวณ พี เป็นกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้ในเวลาที่เป็นฟังก์ชันพหุนามกับขนาดของอินพุต (polynomial time) พี ประกอบด้วย ปัญหาที่สำคัญหลายอย่างที่มีประโยชน์ในชีวิต เช่น ปัญหาการหาตัวหารร่วมมากระหว่างจำนวนสองจำนวน ปัญหาการจับคู่มากที่สุด (Maximum Matching) ปัญหาจำนวนเฉพาะ ปัญหากำหนดการเชิงเส้น (Linear program) พี เป็นกลุ่มความซับซ้อนที่นักวิจัยเรียกว่า "ง่าย" แม้ว่าในความเป็นจริงแล้วปัญหาที่ใช้เวลาในการหาคำตอบ n^ ไม่น่าจะถือว่าง่ายก็ตาม.
ใหม่!!: พี (ความซับซ้อน)และพี (ความซับซ้อน) · ดูเพิ่มเติม »
กลุ่มความซับซ้อน
หน้านี้ประกอบด้วยกลุ่มความซับซ้อนที่สำคัญทั้งหมดในด้านของทฤษฎีความซับซ้อนในการคำนวณ.
ใหม่!!: พี (ความซับซ้อน)และกลุ่มความซับซ้อน · ดูเพิ่มเติม »
ทฤษฎีความซับซ้อนในการคำนวณ
ทฤษฎีความซับซ้อนในการคำนวณ (Computational Complexity Theory) เป็นสาขาหนึ่งของทฤษฎีการคำนวณ ที่มุ่งเน้นไปในการวิเคราะห์เวลาและเนื้อที่สำหรับการแก้ปัญหาหนึ่ง ๆ โดยปกติแล้วคำว่า "เวลา" ที่เราพูดถึงนั้น จะเป็นการนับจำนวนขั้นตอนที่ใช้ในการแก้ปัญหา ส่วนในเรื่องของ "เนื้อที่" เราจะพิจารณาเนื้อที่ ๆ ใช้ในการทำงานเท่านั้น (ไม่นับเนื้อที่ ๆ ใช้ในการเก็บข้อมูลป้อนเข้า).
ใหม่!!: พี (ความซับซ้อน)และทฤษฎีความซับซ้อนในการคำนวณ · ดูเพิ่มเติม »
ปัญหาการตัดสินใจ
ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.
ใหม่!!: พี (ความซับซ้อน)และปัญหาการตัดสินใจ · ดูเพิ่มเติม »
เครื่องทัวริง
รื่องจักรทัวริง (Turing machine) คือเครื่องจักรนามธรรมที่แอลัน ทัวริงได้คิดค้นขึ้นใน..