ผลต่างระหว่างรุ่นของ "ทฤษฎีความซับซ้อนในการคำนวณ"

กลุ่มความซับซ้อนของปัญหา [[กลุ่มความซับซ้อน พี และ เอ็นพี|พี]] ([[:en:complexity classes P and NP|P]]) คือเซตของปัญหาการตัดสินใจที่สามารถหาคำตอบได้ ในเวลาที่เป็นฟังก์ชันพหุนามของขนาดข้อมูลป้อนเข้า ด้วย[[เครื่องจักรทัวริง]]เชิงกำหนด (deterministic turing machine) นิยามนี้สอดคล้องกับแนวคิดของปัญหาที่สามารถหาคำตอบได้อย่างมีประสิทธิภาพ

กลุ่มความซับซ้อนของปัญหา [[เอ็นพี (ความซับซ้อน)|เอ็นพี]] (NP) คือเซตของปัญหาการตัดสินใจที่สามารถแก้ปัญหาได้โดยใช้เครื่องจักรทัวริงเชิงไม่กำหนดในเวลาพหุนาม ปัญหาที่อยู่ในกลุ่มนี้หลายปัญหาเป็นปัญหาที่มนุษย์ต้องการเป็นอย่างมากที่จะแก้ให้ได้อย่างมีประสิทธิภาพ ตัวอย่างของปัญหาในกลุ่มนี้ก็คือ [[ปัญหาความสอดคล้องแบบบูล]] ([[:en:Boolean satisfiability problem|Boolean satisfiability problem]]) [[ปัญหาเส้นทางของฮามิลตัน]] ([[:en:Hamiltonian path problem|Hamiltonian path problem]]) และ [[ปัญหาจุดยอดปกคลุม]] ([[:en:Vertex cover problem|Vertex cover problem]]) ปัญหาทุกปัญหาในกลุ่มนี้สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ