มาดูเวอร์ชั่นของผมบ้าง และเหมือนเช่นทุกครั้งคือผมไม่ขอรับประกันความถูกต้องใดๆทั้งสิ้นนะครับ
ปัญหากลุ่ม P คือ ปัญหาที่แก้ได้ใน polynomial time (ซึ่งแปลว่า เราสามารถหา polynomial p(n) มาอันนึงที่ทำให้เวลาที่ใช้ในการแก้ปัญหาที่มีขนาด n มีค่าน้อยกว่า p(n) ได้สำหรับทุกจำนวนเต็ม n แต่ปกติมักใช้ big O notation กันครับ) อย่างเช่นการคูณเลข n bits 2 ตัวเข้าด้วยกันโดยใช้การคูณแบบธรรมดาจะใช้เวลา O(n
2) ดังนั้นปัญหาการคูณเลขจึงอยู่ในกลุ่ม P
ปัญหากลุ่ม NP คือ ปัญหาที่เราสามารถเช็คได้ว่าคำตอบที่ให้มาถูกต้องหรือไม่ได้ใน polynomial time ครับ ดังนั้น \(P\subseteq NP\) แต่มีปัญหา NP บางอันที่เราไม่รู้ว่าเป็น P รึเปล่า (นั่นคือเราไม่รู้ว่า P = NP ไหม) ตัวอย่างเช่น ปัญหา integer factoring ปัจจุบันนี้เรายังไม่รู้จัก algorithm ใดที่สามารถแยกตัวประกอบของจำนวนเต็ม N ได้ใน polynomial time แต่เราสามารถเช็คคำตอบว่า N = ab จริงมั้ยได้ใน polynomial time ดังนั้น ปัญหา integer factoring จึงอยู่ใน NP แต่(ยัง?)ไม่อยู่ใน P ซึ่งเราเรียกปัญหาพวกนี้ว่า NP-hard ครับ
NP-complete เป็น subset พิเศษของ NP-hard ปัญหาในกลุ่มนี้ equivalent กันหมดครับ คือถ้าแก้ได้อันนึงก็แก้อันอื่นๆได้หมด จะว่าไปแล้ว NP-complete ก็คือกลุ่มของปัญหาทั้งหมดที่ equivalent กับปัญหาการหา Hamiltonian cycle นั่นเอง ปัญหาที่เป็น NP-hard แต่ไม่เคยมีใครพิสูจน์ว่าเป็น (และจริงๆแล้วก็ไม่น่าจะเป็น) NP-complete ก็เช่น integer factoring ครับ
แม้ปัจจุบันนี้ ปัญหา integer factoring จะเป็น NP-hard สำหรับ conventional computer (ที่เราเรียกกันว่า Turing machine) แต่จะเป็น P สำหรับ (hypothetical) quantum computer เนื่องจากการค้นพบ Shor's algorithm เมื่อไม่นานมานี้ นั่นคือถ้ามีคนสร้าง quantum computer ได้เมื่อไหร่การเข้ารหัสแบบที่เราใช้กับ https:// ในปัจจุบันก็จะหมดประโยชน์ไปเลยครับ