เมนูนำทาง
ทฤษฎีความซับซ้อนในการคำนวณ กลุ่มของความซับซ้อนของปัญหาปัญหาการตัดสินใจสามารถแบ่งออกได้เป็นหลายๆกลุ่ม โดยที่แต่ละกลุ่มจะประกอบไปด้วยปัญหาที่มีความยากเท่าเทียมกัน
กลุ่มความซับซ้อนของปัญหา พี (P) คือเซตของปัญหาการตัดสินใจที่สามารถหาคำตอบได้ ในเวลาที่เป็นฟังก์ชันพหุนามของขนาดข้อมูลป้อนเข้า ด้วยเครื่องจักรทัวริงเชิงกำหนด (deterministic turing machine) นิยามนี้สอดคล้องกับแนวคิดของปัญหาที่สามารถหาคำตอบได้อย่างมีประสิทธิภาพ
กลุ่มความซับซ้อนของปัญหา เอ็นพี (NP) คือเซตของปัญหาการตัดสินใจที่สามารถแก้ปัญหาได้โดยใช้เครื่องจักรทัวริงเชิงไม่กำหนดในเวลาพหุนาม ปัญหาที่อยู่ในกลุ่มนี้หลายปัญหาเป็นปัญหาที่มนุษย์ต้องการเป็นอย่างมากที่จะแก้ให้ได้อย่างมีประสิทธิภาพ ตัวอย่างของปัญหาในกลุ่มนี้ก็คือ ปัญหาความสอดคล้องแบบบูล (Boolean satisfiability problem) ปัญหาเส้นทางของฮามิลตัน (Hamiltonian path problem) และ ปัญหาจุดยอดปกคลุม (Vertex cover problem) ปัญหาทุกปัญหาในกลุ่มนี้สามารถตรวจคำตอบได้อย่างมีประสิทธิภาพ
เมนูนำทาง
ทฤษฎีความซับซ้อนในการคำนวณ กลุ่มของความซับซ้อนของปัญหาใกล้เคียง
ทฤษฎี ทฤษฎี สหวงษ์ ทฤษฎีเกม ทฤษฎีระบบควบคุม ทฤษฎีความผูกพัน ทฤษฎีแม่เหล็กไฟฟ้า ทฤษฎีสีชมพู ทฤษฎีสัมพัทธภาพพิเศษ ทฤษฎีบทพีทาโกรัส ทฤษฎีจีบเธอแหล่งที่มา
WikiPedia: ทฤษฎีความซับซ้อนในการคำนวณ