ทฤษฎีความซับซ้อนในการคำนวณเป็นสาขาวิชาคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ที่เกี่ยวข้องกับทรัพยากรที่จำเป็นในการแก้ปัญหาในระบบคอมพิวเตอร์ จำนวนเทคนิคที่มีอยู่เพื่อกำหนดความต้องการทรัพยากรของปัญหา ปัญหาบางอย่างอาจไม่สามารถทำได้ในระบบคอมพิวเตอร์ที่มีอยู่เนื่องจากความต้องการทรัพยากรของพวกเขา นักวิจัยจำแนกปัญหาด้วยความยากลำบากและสามารถแบ่งการคำนวณออกเป็นพหุนาม (P) กับปัญหาพหุนามไม่เชิง (NP)
การแก้ไขการคำนวณต้องใช้ทรัพยากรเช่นเวลาพื้นที่เก็บข้อมูลและฮาร์ดแวร์ ระบบคอมพิวเตอร์อาจมีข้อ จำกัด ที่ทำให้ไม่สามารถแก้ไขปัญหาได้เนื่องจากไม่มีทรัพยากรที่มีอยู่ เมื่อเทคโนโลยีคอมพิวเตอร์ดีขึ้นปัญหาที่แก้ไม่ได้ก่อนหน้านี้อาจแก้ไขได้ด้วยความช่วยเหลือของเทคโนโลยีใหม่และการวิจัยในสาขาทฤษฎีความซับซ้อนในการคำนวณ การแก้ปัญหาไม่ได้ขึ้นอยู่กับความซับซ้อน แต่ขึ้นอยู่กับอัลกอริทึมที่ใช้ในการแก้
ในทฤษฎีความซับซ้อนในการคำนวณปัญหา P เป็นสิ่งที่สามารถแก้ไขได้ในเวลาพหุนามด้วยอัลกอริทึมที่ตรงไปตรงมา มันอาจยังต้องใช้ทรัพยากรจำนวนมาก แต่มันสามารถแก้ไขได้และตรวจสอบได้ด้วยคอมพิวเตอร์ ปัญหาดังกล่าวอาจถูกแก้ไขได้อย่างรวดเร็วตราบใดที่คอมพิวเตอร์มีทรัพยากรที่มีอยู่เพื่อจัดการกับการคำนวณที่จำเป็น
ปัญหา NP มีความซับซ้อนมากขึ้น ไม่สามารถใช้อัลกอริทึมเดียวและอาจจำเป็นต้องใช้ตัวเลือกขั้นสูงเพิ่มเติมเช่นเครื่องทัวริงขนานที่สามารถสำรวจตัวเลือกต่าง ๆ ปัญหาอาจแก้ไขได้ด้วยวิธีนี้ แต่จะต้องใช้ทรัพยากรมากขึ้น ปัญหาดังกล่าวอาจง่ายขึ้นสำหรับผู้ปฏิบัติงานมนุษย์ที่มีความสามารถในการคิดเชิงตรรกะขั้นสูงเนื่องจากจุดเปลี่ยนบ่อยครั้งจะเป็นหนึ่งในตรรกะมากกว่าความยากในการคำนวณอย่างแท้จริง ปัญหาพนักงานขายเดินทางซึ่งเป้าหมายคือการหาเส้นทางที่มีประสิทธิภาพมากที่สุดระหว่างเมืองหลายแห่งตามเส้นทางเป็นตัวอย่างคลาสสิกของปัญหา NP ในทฤษฎีความซับซ้อนในการคำนวณ
การจำแนกปัญหา P กับปัญหา NP ผ่านทฤษฎีความซับซ้อนในการคำนวณอาจเป็นงานที่ซับซ้อนและปัญหาอาจเลื่อนไปมาระหว่างการหาร ปัญหาการคำนวณชุดเล็ก ๆ ไม่เหมาะอย่างเป็นระเบียบในบางหมวดหมู่และบางครั้งก็จัดว่าไม่เหมือนกันเพื่อสะท้อนสิ่งนี้ ในที่สุดอาจเป็นไปได้ที่จะพัฒนาอัลกอริทึมเพื่อแก้ปัญหา NP และในบางกรณีอาจใช้กับปัญหาอื่น ๆ ที่มีโครงสร้างคล้ายกัน อย่างไรก็ตามในบางประเทศอาจมีปัญหาเฉพาะ กระบวนการในการสำรวจโปรแกรมดังกล่าวและวิธีการพัฒนาเพื่อแก้ปัญหานั้นเป็นส่วนสำคัญของคณิตศาสตร์และวิทยาการคอมพิวเตอร์ที่มีส่วนช่วยในการพัฒนาระบบคอมพิวเตอร์ขั้นสูงและมีกำลังสูง
