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

ตัวอย่างง่ายๆ ของปัญหา NP-hard คือปัญหาผลรวมของเซตย่อย

โดยทั่วไป หากHเป็น NP-hard แสดงว่าการแก้ปัญหานั้นยากอย่างน้อยก็เท่ากับปัญหาในNPอย่างไรก็ตาม ทิศทางตรงกันข้ามนั้นไม่เป็นจริง: บางปัญหาไม่สามารถตัดสินได้และด้วยเหตุนี้จึงยากต่อการแก้ปัญหามากกว่าปัญหาทั้งหมดใน NP แต่ปัญหาเหล่านั้นอาจไม่ใช่ NP-hard (เว้นแต่ P=NP) ^{[ 5 ]}

ปัญหาการตัดสินใจHเป็นปัญหา NP-hard เมื่อสำหรับทุกปัญหาLใน NP จะมีการลดแบบหลายหนึ่งในเวลาพหุนามจากLไปยังH ^{[ 1 ] : 80}

นิยามอีกประการหนึ่งคือ กำหนดให้ต้องมีการลดรูปในเวลาพหุนามจากปัญหาNP-complete GไปยังH [ ^{1 ] : 91เนื่องจาก}ปัญหาL ใดๆ ใน NP สามารถลดรูปในเวลาพหุนามไปยังG ได้ดังนั้นLจึงสามารถลดรูปไปยังHในเวลาพหุนามได้เช่นกัน ดังนั้นนิยามใหม่นี้จึงหมายถึงนิยามก่อนหน้านี้ มันไม่ได้จำกัดคลาส NP-hard ไว้เฉพาะปัญหาการตัดสินใจเท่านั้น แต่ยังรวมถึงปัญหาการค้นหาหรือปัญหาการเพิ่มประสิทธิภาพด้วย

ถ้า P ≠ NP แสดงว่าปัญหา NP-hard ไม่สามารถแก้ไขได้ในเวลาพหุนาม

ปัญหาการหาค่าเหมาะสมที่สุดแบบ NP-hard บางปัญหาสามารถประมาณค่าได้ ในเวลาพหุนาม จนถึงอัตราส่วนการประมาณค่าคงที่บางค่า (โดยเฉพาะปัญหาในAPX ) หรือแม้กระทั่งจนถึงอัตราส่วนการประมาณค่าใดๆ ก็ได้ (ปัญหาในPTASหรือFPTAS ) มีคลาสของความสามารถในการประมาณค่าหลายประเภท แต่ละประเภทช่วยให้สามารถประมาณค่าได้ถึงระดับที่แตกต่างกัน^{[ 6 ]}

ปัญหาNP-completeทั้งหมด ก็เป็นปัญหา NP-hard ด้วยเช่นกัน (ดู รายชื่อปัญหา NP-complete ) ตัวอย่างเช่น ปัญหาการหาเส้นทางวนรอบที่มีต้นทุนต่ำที่สุดผ่านโหนดทั้งหมดของกราฟที่มีน้ำหนัก—ซึ่งโดยทั่วไปเรียกว่าปัญหาพนักงานขายเดินทาง—เป็นปัญหา NP-hard ^{[ 7 ]}ปัญหาผลรวมของเซตย่อยเป็นอีกตัวอย่างหนึ่ง: เมื่อกำหนดเซตของจำนวนเต็มแล้ว มีเซตย่อยที่ไม่ว่างเปล่าใดบ้างที่รวมกันแล้วได้ศูนย์? นั่นเป็นปัญหาการตัดสินใจและเป็นปัญหา NP-complete

มีปัญหาการตัดสินใจบางอย่างที่เป็นNP-hardแต่ไม่ใช่NP-completeเช่นปัญหาการหยุดทำงาน (halting problem ) ซึ่งเป็นปัญหาที่ถามว่า "เมื่อกำหนดโปรแกรมและอินพุตแล้ว โปรแกรมจะทำงานไปเรื่อยๆ หรือไม่" นี่เป็น คำถาม ใช่ / ไม่ใช่ดังนั้นจึงเป็นปัญหาการตัดสินใจเช่นกัน การพิสูจน์ว่าปัญหาการหยุดทำงานเป็น NP-hard แต่ไม่ใช่ NP-complete นั้นทำได้ง่าย ตัวอย่างเช่นปัญหาความสามารถในการทำให้เป็นจริงของบูลีน (Boolean satisfiability problem)สามารถลดรูปไปเป็นปัญหาการหยุดทำงานได้โดยการแปลงให้เป็นการอธิบายเครื่องจักรทัวริง (Turing machine) ที่ลองกำหนด ค่าความจริงทั้งหมดและเมื่อพบค่าที่ตรงกับสูตรก็จะหยุดทำงาน มิฉะนั้นก็จะวนลูปไม่รู้จบ นอกจากนี้ยังเห็นได้ง่ายว่าปัญหาการหยุดทำงานไม่ได้อยู่ในNPเนื่องจากปัญหาทั้งหมดใน NP สามารถตัดสินได้ด้วยจำนวนการดำเนินการที่จำกัด แต่ปัญหาการหยุดทำงานโดยทั่วไปนั้นไม่สามารถตัดสินได้นอกจากนี้ยังมีปัญหา NP-hard บางอย่างที่ไม่ใช่ทั้งNP-completeและไม่สามารถตัดสินได้ ตัวอย่างเช่น ภาษาของสูตรบูลีนเชิงปริมาณที่แท้จริงสามารถตัดสินได้ในพื้นที่พหุนามแต่ไม่ใช่ในเวลาพหุนามที่ไม่กำหนด (เว้นแต่ NP = PSPACE ) ^{[ 8 ]}

ปัญหา NP-hard ไม่จำเป็นต้องเป็นส่วนหนึ่งของกลุ่มความซับซ้อน NP เสมอไป เนื่องจาก NP มีบทบาทสำคัญในความซับซ้อนของการคำนวณจึงถูกนำมาใช้เป็นพื้นฐานของกลุ่มความซับซ้อนหลายกลุ่ม:

NP

กลุ่มของปัญหาการตัดสินใจเชิงคำนวณ ซึ่ง คำตอบ "ใช่" ใดๆ ก็ตาม สามารถตรวจสอบได้ว่าเป็นคำตอบในเวลาพหุนามโดยเครื่องจักรทัวริงแบบกำหนดได้ (หรือสามารถแก้ไขได้โดย เครื่องจักรทัวริง แบบไม่กำหนดได้ในเวลาพหุนาม)

NP-hard

กลุ่มของปัญหาที่ยากอย่างน้อยก็เท่ากับปัญหาที่ยากที่สุดใน NP ปัญหาที่จัดว่าเป็น NP-hard ไม่จำเป็นต้องเป็นสมาชิกของ NP เสมอไป อันที่จริงแล้ว ปัญหาเหล่านั้นอาจไม่สามารถตัดสินได้ด้วยซ้ำ

NP-complete

กลุ่มของปัญหาการตัดสินใจซึ่งประกอบด้วยปัญหาที่ยากที่สุดใน NP โดยที่ปัญหา NP-complete ทุกปัญหาจะต้องอยู่ใน NP

NP-easy

อย่างมากที่สุดก็ยากพอๆ กับ NP แต่ไม่จำเป็นต้องอยู่ใน NP เสมอไป

เทียบเท่า NP

ปัญหาการตัดสินใจที่เป็นทั้งปัญหา NP-hard และ NP-easy แต่ไม่จำเป็นต้องอยู่ในกลุ่ม NP

NP-ระดับกลาง

ถ้า P และ NP แตกต่างกัน จะมีปัญหาการตัดสินใจอยู่ในขอบเขตของ NP ซึ่งอยู่ระหว่าง P และปัญหา NP-complete (ถ้า P และ NP เป็นกลุ่มเดียวกัน ปัญหา NP-intermediate จะไม่มีอยู่จริง เพราะในกรณีนี้ ปัญหา NP-complete ทุกปัญหาจะอยู่ใน P และตามนิยามแล้ว ทุกปัญหาใน NP สามารถลดรูปให้เป็นปัญหา NP-complete ได้)

ปัญหา NP-hard มักได้รับการแก้ไขด้วยภาษาโปรแกรมแบบใช้กฎเกณฑ์ในด้านต่างๆ เช่น:

• การคำนวณโดยประมาณ
• การกำหนดค่า
• การเข้ารหัสลับ
• การขุดข้อมูล
• การสนับสนุนการตัดสินใจ
• วิวัฒนาการทางสายพันธุ์
• การวางแผน
• การตรวจสอบและควบคุมกระบวนการ
• รายชื่อหรือตารางการแข่งขัน
• การกำหนดเส้นทาง/การจัดเส้นทางยานพาหนะ
• การจัดตารางเวลา

ปัญหาที่สามารถตัดสินได้แต่ไม่ใช่ปัญหาNP-completeมักจะเป็นปัญหาเกี่ยวกับการหาค่าเหมาะสมที่สุด:

• ปัญหาการเพิ่มประสิทธิภาพกระเป๋าเป้สะพายหลัง
• การเขียนโปรแกรมจำนวนเต็ม
• ปัญหาการหาค่าเหมาะสมที่สุดของพนักงานขายเดินทาง
• กลุ่มใหญ่ที่สุด
• เส้นทางที่เรียบง่ายที่สุดที่ยาวที่สุด
• การระบายสีกราฟ : การประยุกต์ใช้: การจัดสรรรีจิสเตอร์ในคอมไพเลอร์

• รายการปัญหา
• รายการปัญหาที่ยังแก้ไม่ตก
• การลดลง (ความซับซ้อน)
• ความไม่สามารถรู้ได้