การพิจารณาว่าปัญหาการตัดสินใจหนึ่งๆ เป็นปัญหาที่มีความซับซ้อนอย่างไรเมื่อเทียบกับปัญหาการตัดสินใจอื่นๆ เป็นประเด็นที่สำคัญในทฤษฎีความซับซ้อนในการคำนวณ ทฤษฎีความซับซ้อนในการคำนวณ จึงได้นิยามศัพท์คำว่าความบริบูรณ์ของปัญหา โดยนิยามว่า

ปัญหาการตัดสินใจ P ใดๆ เป็นปัญหาที่บริบูรณ์ (complete) บนเซตของปัญหาการตัดสินใจ S และการลดรูปแบบ R {\displaystyle {\mathcal {R}}} ก็ต่อเมื่อ

1. P เป็นสมาชิกของ S
2. ทุกๆ ปัญหาที่เป็นสมาชิกของ S สามารถลดรูป แบบ R {\displaystyle {\mathcal {R}}} ไปยังปัญหา P ได้

ยกตัวอย่างเช่น ปัญหาความสอดคล้องแบบบูล เป็นปัญหาที่บริบูรณ์บนกลุ่มปัญหาเอ็นพี และการลดรูปด้วยเวลาเชิงพหุนาม เพราะ ปัญหาความสอดคล้องแบบบูล เป็นสมาชิกของปัญหาเอ็นพี และทุกๆ ปัญหาเอ็นพี สามารถลดรูป ด้วยเวลาเชิงพหุนาม ไปยังปัญหาความสอดคล้องแบบบูลได้