ในด้านความซับซ้อนของการคำนวณปัญหาNP-completeness ที่เข้มงวดเป็นคุณสมบัติของปัญหาการคำนวณที่เป็นกรณีพิเศษของNP-completenessโดยทั่วไปแล้ว ปัญหาการคำนวณอาจมีพารามิเตอร์เชิงตัวเลข ตัวอย่างเช่น ข้อมูลนำเข้าของ ปัญหา การบรรจุลงถังคือรายการของวัตถุที่มีขนาดเฉพาะ และขนาดของถังที่ต้องบรรจุวัตถุเหล่านั้น ซึ่งขนาดของวัตถุและขนาดของถังเหล่านี้เป็นพารามิเตอร์เชิงตัวเลข

ปัญหาหนึ่งเรียกว่าเป็นปัญหาNP-complete ที่แข็งแกร่ง (NP-complete ในความหมายที่แข็งแกร่ง) หากยังคงเป็น NP-complete แม้ว่าพารามิเตอร์เชิงตัวเลขทั้งหมดจะถูกจำกัดด้วยพหุนามในความยาวของอินพุตก็ตาม^{[ 1 ]}ปัญหาหนึ่งเรียกว่าเป็นปัญหาNP-hard ที่แข็งแกร่ง หากปัญหา NP-complete ที่แข็งแกร่งมีการลดรูปพหุนามเทียม การลดรูปพหุนามเทียมนี้มีความเข้มงวดมากกว่าการลดรูปพหุนามเวลาปกติที่ใช้ในการพิสูจน์ความยากของ NP โดยเฉพาะอย่างยิ่ง การลดรูปพหุนามเทียมไม่สามารถส่งออกพารามิเตอร์เชิงตัวเลขที่ไม่ถูกจำกัดด้วยพหุนามโดยขนาดและค่าของตัวเลขในอินพุตได้^{[ 2 ]}

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

ตัวอย่างเช่น ปัญหาการจัดเรียงสิ่งของ ลงถัง (bin packing)เป็นปัญหา NP-complete อย่างมาก ในขณะที่ปัญหาเป้สะพายหลังแบบ 0-1 (0-1 Knapsack problem) เป็นปัญหา NP-complete อย่างอ่อนเท่านั้นดังนั้น ปัญหาการจัดเรียงสิ่งของลงถังในรูปแบบที่ขนาดของวัตถุและถังเป็นจำนวนเต็มที่มีขอบเขตจำกัดด้วยพหุนาม จึงยังคงเป็นปัญหา NP-complete ในขณะที่ปัญหาเป้สะพายหลังในรูปแบบที่สอดคล้องกันสามารถแก้ไขได้ในเวลาแบบพсевдоพหุนามโดยใช้ การเขียนโปรแกรมเชิงพลวัต ( dynamic programming )

จากมุมมองทางทฤษฎี ปัญหาการหาค่าเหมาะสมที่สุดที่ยากแบบ NP-hard อย่างมากซึ่งมีฟังก์ชันเป้าหมายที่มีขอบเขตพหุนาม จะไม่สามารถมีแผนการประมาณค่าแบบพหุนามเต็มรูปแบบ (หรือFPTAS ) ได้ เว้นแต่ว่า P  =  NP ^{[ 3 ] [ 4 ]}อย่างไรก็ตาม ในทางกลับกันนั้นไม่เป็นจริง เช่น ถ้า P ไม่เท่ากับ NP ปัญหา knapsack ที่มีข้อจำกัดสองข้อจะไม่ยากแบบ NP-hard อย่างมาก แต่ก็ไม่มี FPTAS แม้ว่าฟังก์ชันเป้าหมายที่เหมาะสมที่สุดจะมีขอบเขตพหุนามก็ตาม^{[ 5 ]}

ปัญหาที่ซับซ้อนระดับ NP-complete บางปัญหาอาจยังแก้ได้ง่ายโดยเฉลี่ยแต่ในทางปฏิบัติแล้วมีโอกาสมากกว่าที่จะเจอปัญหาที่แก้ได้ยากกว่า

สมมติว่า P ≠ NP ข้อต่อไปนี้เป็นจริงสำหรับปัญหาการคำนวณบนจำนวนเต็ม: ^{[ 6 ]}

• หากปัญหาใดเป็นปัญหาNP-hard แบบอ่อนนั่นหมายความว่าปัญหานั้นจะไม่มีอัลกอริทึมแบบเวลาพหุนามแบบอ่อน (พหุนามตามจำนวนจำนวนเต็มและจำนวนบิตในจำนวนเต็มที่ใหญ่ที่สุด) แต่ปัญหานั้นอาจมีอัลกอริทึมแบบเวลาพหุนามเทียม (พหุนามตามจำนวนจำนวนเต็มและขนาดของจำนวนเต็มที่ใหญ่ที่สุด) ตัวอย่างเช่นปัญหาการแบ่งพาร์ติชันทั้งความยากแบบ NP-hard แบบอ่อนและเวลาพหุนามแบบอ่อนนั้นสอดคล้องกับการเข้ารหัสจำนวนเต็มอินพุตในรูปแบบไบนารี

• หากปัญหาใดเป็นปัญหาNP-hard ที่รุนแรงปัญหานั้นจะไม่มี อัลกอริทึมที่ใช้เวลาประมวล ผลแบบพсевдоพหุนาม (pseudo-polynomial time ) และไม่มีวิธีการประมาณค่าที่ใช้เวลาประมวลผลแบบพหุนามอย่างสมบูรณ์ (fully-polynomial time approximation scheme ) ตัวอย่างเช่นปัญหาการแบ่ง 3 ส่วน (3-partition problem ) ทั้งความยากแบบ NP-hard ที่รุนแรงและเวลาประมวลผลแบบพсевдоพหุนามนั้นสอดคล้องกับการเข้ารหัสจำนวนเต็มอินพุตด้วยการเข้ารหัสแบบเอกภาค (unary coding )