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