ปัญหาที่ใหญ่ที่สุดในวิทยาการคอมพิวเตอร์: ปัญหา P กับ NP
มีปัญหาคณิตศาสตร์เจ็ดข้อที่ถือว่ายากและน่าสนใจมาก จนสถาบันคณิตศาสตร์เคลย์ (Clay Mathematics Institute) ประกาศให้เป็น ปัญหารางวัลแห่งสหัสวรรษ (Millennium Prize Problems) ผู้ที่แก้ได้แต่ละข้อจะได้รับรางวัลหนึ่งล้านดอลลาร์สหรัฐ ปัญหาข้อหนึ่งเกี่ยวกับวิทยาการคอมพิวเตอร์ด้วย เรียกว่าปัญหา P กับ NP (P versus NP) มาดูกันว่าปัญหานี้ว่าด้วยเรื่องอะไร
ขอบอกตรง ๆ ว่าการอธิบายเรื่องนี้ไม่ง่าย เพราะอย่างไรก็เป็นปัญหาระดับสหัสวรรษ ไปชงชาเขียวดี ๆ สักแก้ว 🍵 แล้วเริ่มกันเลย ขั้นแรกจะดูปัญหาสี่ข้อจากโลกของวิทยาการคอมพิวเตอร์และอัลกอริทึม วิเคราะห์ปัญหาเหล่านี้ และดูว่าเกี่ยวข้องกับตัวอักษร P และ NP อย่างไร
ปัญหาที่ 1: การหาจำนวนที่น้อยที่สุด
ปัญหา P กับ NP เกี่ยวกับอัลกอริทึมและความซับซ้อนของอัลกอริทึม ลองนึกว่ามีกระดาษหนึ่งร้อยแผ่นเทกองอยู่ตรงหน้า แต่ละแผ่นเขียนจำนวนไว้หนึ่งจำนวน และต้องหาแผ่นที่เขียนจำนวนที่น้อยที่สุด จะใช้เวลานานเท่าใด
ครึ่งนาที สองนาที
หน่วยเวลาแบบนี้ไม่ใช่สิ่งที่วิทยาการคอมพิวเตอร์เชิงทฤษฎีสนใจนัก สิ่งที่สนใจคือ จำนวนการดำเนินการ มากกว่า จึงถามอีกแบบได้ว่า ต้องตรวจกระดาษกี่แผ่นจึงจะมั่นใจว่าพบจำนวนที่น้อยที่สุดแล้ว คำตอบคือต้องตรวจกระดาษทุกแผ่น เพราะจำนวนที่น้อยที่สุดอาจอยู่ในแผ่นสุดท้ายก็ได้ ถ้ามีกระดาษหนึ่งร้อยแผ่น ก็ต้องตรวจหนึ่งร้อยแผ่น ถ้ามีหนึ่งพันแผ่น ก็ต้องตรวจหนึ่งพันแผ่น โดยทั่วไป ถ้ามีกระดาษ n แผ่น ก็ต้องตรวจ n แผ่น
แนวคิดนี้เรียกว่า ความซับซ้อนของอัลกอริทึม ถ้ามีกระดาษ n แผ่น และต้องดำเนินการ n ครั้งเพื่อหาจำนวนที่น้อยที่สุด แสดงว่าอัลกอริทึมการหาจำนวนที่น้อยที่สุดนี้มีความซับซ้อน n ซึ่งเรียกอีกอย่างว่าความซับซ้อนเชิงเส้น เพราะความซับซ้อนอธิบายได้ด้วยฟังก์ชันเชิงเส้น
สมมติว่าดูกระดาษครบหนึ่งร้อยแผ่นแล้ว และบอกว่าจำนวนที่น้อยที่สุดคือ 17 จะตรวจได้อย่างไรว่าคำตอบนี้ถูกต้อง ไม่มีวิธีอื่นนอกจากดูกระดาษทุกแผ่นอีกครั้ง และตรวจว่าไม่มีแผ่นใดเขียนจำนวนที่น้อยกว่านั้น นั่นคือ ผู้หาต้องดูกระดาษ n แผ่นเพื่อหาจำนวนที่น้อยที่สุด และผู้ตรวจก็ต้องทำแบบเดียวกัน ความซับซ้อนของการ ตรวจสอบ ผลลัพธ์จึงเป็น n เช่นกัน คือความซับซ้อนเชิงเส้น
มีอัลกอริทึมใดบ้างหรือไม่ที่ตรวจสอบผลลัพธ์ได้ง่ายกว่าการหาผลลัพธ์
ปัญหาที่ 2: ผลคูณของคู่จำนวน
ลองนึกว่ามีกระดาษสองกองที่มีขนาดเท่ากัน แต่ละแผ่นเขียนจำนวนไว้หนึ่งจำนวนเช่นเดิม คราวนี้ต้องหาจำนวนจากกอง A หนึ่งจำนวน และจากกอง B หนึ่งจำนวน ที่ผลคูณเท่ากับ 918 ตัวอย่างเช่น ให้กองของจำนวนเป็นดังนี้:
จะหาคู่จำนวนที่ผลคูณเท่ากับ 918 ได้อย่างไร วิธีง่าย ๆ คือลองทุกกรณี มีกี่กรณี ค่อนข้างมาก คือ 25 กรณี เริ่มจากนำจำนวนแรกในกอง A คือ 49 คูณกับจำนวนทุกจำนวนในกอง B:
ไม่มีคู่ใดได้ 918 จึงทำแบบเดียวกันกับจำนวนที่เหลือในกอง A คืออีกห้าคู่สำหรับ 11 อีกห้าคู่สำหรับ 32 อีกห้าคู่สำหรับ 54 และห้าคู่สุดท้ายสำหรับ 15 รวมแล้วลองได้ 25 คู่ ในที่สุดจะพบว่า 54 × 17 = 918
อัลกอริทึมนี้มี ความซับซ้อน เท่าใด สิ่งที่สนใจคือต้องคูณจำนวนกี่คู่ ทั้งสองกองมีกระดาษกองละห้าแผ่น และต้องลองจำนวนแต่ละจำนวนจากห้าจำนวนในกองแรกกับจำนวนแต่ละจำนวนจากห้าจำนวนในกองที่สอง รวมแล้วลอง 5 × 5 = 25 แบบ ถ้ามีกระดาษสองกอง กองละ 10 แผ่น ก็ต้องลอง 10 × 10 = 100 แบบ เมื่อขยายเป็นกรณีทั่วไป ถ้ามีกระดาษสองกอง กองละ n แผ่น ก็ต้องลอง n · n = n2 แบบ
กล่าวว่าอัลกอริทึมนี้มีความซับซ้อน n2 คือความซับซ้อนกำลังสอง เพราะอธิบายได้ด้วยฟังก์ชันกำลังสอง
แล้วการตรวจผลลัพธ์จะยากเพียงใด ถ้าคำตอบคือ 54 และ 17 เป็นจำนวนที่ผลคูณเท่ากับ 918 ผู้ตรวจไม่ต้องไล่ดูทุกคู่จากทั้งสองกองเหมือนผู้หา เพียงคูณคู่นี้คู่เดียว 54 × 17 ก็รู้แล้วว่าคำตอบถูกหรือผิด ดังนั้นแม้การ แก้ ปัญหานี้อาจต้องคำนวณผลคูณถึง n2 ครั้ง แต่การ ตรวจสอบ ต้องคำนวณผลคูณเพียงครั้งเดียว การตรวจสอบจึงมีความซับซ้อนคงตัวเท่ากับ 1
ปัญหานี้จึงต่างจากปัญหาก่อนหน้ามาก เพราะปัญหาก่อนหน้าต้องใช้จำนวนขั้นตอนเท่ากันทั้งในการคำนวณและการตรวจสอบ
ปัญหานี้ยังซับซ้อนกว่าปัญหาก่อนหน้า มาก ด้วย ถ้ามีกระดาษหนึ่งหมื่นแผ่นและต้องหาจำนวนที่น้อยที่สุด ก็น่าจะหาได้ภายในหนึ่งวัน แต่ถ้ามีกระดาษสองกอง กองละหนึ่งหมื่นแผ่น และต้องหาผลคูณ ก็ต้องตรวจผลคูณหนึ่งหมื่นคูณหนึ่งหมื่นครั้ง คือหนึ่งร้อยล้านครั้ง แม้จะคำนวณได้วินาทีละหนึ่งผลคูณ ก็ต้องใช้เวลาประมาณสามปี
ปัญหาที่ 3: ผลบวกของสับเซต
มาดูปัญหาที่สาม คราวนี้มีกระดาษสิบสองแผ่นที่เขียนจำนวนไว้ และต้องหากระดาษกี่แผ่นก็ได้ที่ผลบวกเท่ากับศูนย์ ตัวอย่างเช่น:
จงเลือกจำนวนกลุ่มหนึ่งจากจำนวนเหล่านี้ที่ผลบวกเท่ากับ 0 ตัวอย่างเช่น จำนวน
มีผลบวกเท่ากับ 4 จึงไม่ใช่คำตอบที่ถูกต้อง คำตอบที่ถูกต้องคือกลุ่มของจำนวน… เอาเป็นว่า ลองหาเองเป็นการบ้าน 😉 มีจำนวนเพียงกลุ่มเดียวที่ผลบวกเท่ากับ 0 อย่างน้อยก็จะได้รู้ว่าปัญหานี้ยากเพียงใด
ต่อไปต้องหาความซับซ้อนของปัญหานี้ การคำนวณไม่ง่ายนัก เหมาะกับผู้ที่สนใจเป็นพิเศษ ถ้าสนใจว่าคำนวณความซับซ้อนของปัญหานี้อย่างไร ให้อ่านต่อ ถ้าไม่สนใจก็ข้ามไปหัวข้อถัดไปได้ ⏩
จะหากลุ่มของจำนวนที่ผลบวกเท่ากับ 0 ได้อย่างไร ต้องลองทุกการจัดหมู่ที่เป็นไปได้ คือต้องลองทุกคู่ ทุกกลุ่มสามจำนวน สี่จำนวน ห้าจำนวน ไปเรื่อย ๆ และตรวจว่าผลบวกของแต่ละกลุ่มเท่ากับศูนย์หรือไม่ การจัดหมู่แบบนี้มีกี่แบบ
ลองดูจากเซตที่เล็กกว่า จากจำนวนสามจำนวน B = {5, 7, 9} สร้างกลุ่มของจำนวน หรือสับเซต ที่ต่างกันได้กี่กลุ่ม มีทั้งหมดแปดกลุ่ม:
สังเกตว่านับเซตว่าง B1 รวมไปด้วย ตอนนี้ยังไม่มีประโยชน์นัก แต่ใส่ไว้เพื่อความครบถ้วน เพื่อให้คำนวณง่ายขึ้น จะกำหนดลำดับเลขฐานสอง (binary vector) ให้แต่ละสับเซต ลำดับเลขฐานสองก็คือลำดับของศูนย์และหนึ่ง เช่น 00101010 ในที่นี้จะใช้ลำดับเลขฐานสองที่ยาวสามหลัก โดยกำหนด 101 ให้สับเซตที่มี “จำนวนที่หนึ่งและที่สามจากเซตเดิม แต่ไม่มีจำนวนที่สอง” คือเซต {5, 9} กำหนด 110 ให้สับเซตที่มี “จำนวนที่หนึ่งและที่สองจากเซตเดิม แต่ไม่มีจำนวนที่สาม” คือเซต {5, 7} เป็นต้น
จะเห็นว่าสับเซตแต่ละสับเซตมีลำดับเลขฐานสองยาวสามหลักเพียงลำดับเดียว และลำดับเลขฐานสองยาวสามหลักแต่ละลำดับก็ตรงกับสับเซตเพียงสับเซตเดียว ดังนั้นถ้าคำนวณได้ว่ามีลำดับเลขฐานสองยาว n หลักที่ต่างกันกี่ลำดับ ก็จะได้จำนวนการจัดหมู่ที่ต่างกันทั้งหมดที่สร้างได้จากจำนวนที่ต่างกัน n จำนวน มาคำนวณกัน
ลำดับเลขฐานสองยาวหนึ่งหลักมีสองลำดับ คือ 0 และ 1
ลำดับเลขฐานสองยาวสองหลักได้จากการนำลำดับยาวหนึ่งหลักทั้งหมดมาเติม 0 ต่อท้าย จะได้ 00 และ 10 แล้วนำลำดับยาว 1 หลักทั้งหมดมาเติม 1 ต่อท้ายอีกครั้ง จะได้ 01 และ 11 จึงได้ลำดับยาว 2 หลักครบทุกลำดับ คือ 00, 01, 10 และ 11
ลำดับเลขฐานสองยาวสามหลักได้จากการนำลำดับยาวสองหลักทั้งหมดมาเติมศูนย์ต่อท้าย: 000, 010, 100 และ 110 และเติมหนึ่งต่อท้าย: 001, 011, 101 และ 111
ความยาวต่อ ๆ ไปก็ทำเช่นเดียวกัน จะเห็นว่าเมื่อความยาวของลำดับเลขฐานสองเพิ่มขึ้นหนึ่ง จำนวนลำดับที่ต่างกันจะเพิ่มขึ้นเป็นสองเท่า ลำดับที่ยาวสี่หลักจึงมีการจัดหมู่ที่ต่างกันทั้งหมด 2 × 2 × 2 × 2 คือ 16 แบบ
โดยทั่วไปสรุปได้ว่า ถ้าเซต M มีสมาชิก n ตัว จำนวนสับเซตทั้งหมดของเซต M จะเท่ากับจำนวนลำดับเลขฐานสองยาว n หลักที่ต่างกันทั้งหมด ซึ่งเท่ากับ
2n หรือ n2 ต่างกันตรงไหน 🤷♂
ดังนั้นจากเซตที่มีจำนวน n จำนวน สร้างสับเซตที่ต่างกันได้ 2n สับเซต ในกรณีนี้มี n = 12 จำนวน จึงต้องตรวจการจัดหมู่ที่ต่างกัน 212 แบบ คือ 4096 แบบ กล่าวว่าปัญหานี้มีความซับซ้อน 2n คือความซับซ้อนแบบเอกซ์โพเนนเชียล เพราะอธิบายได้ด้วยฟังก์ชันเอกซ์โพเนนเชียล
สังเกตว่าปัญหาก่อนหน้ามีความซับซ้อน n2 ส่วนปัญหานี้มีความซับซ้อน 2n ดูคล้ายกันมาก ใช่ไหม แต่การที่เลขชี้กำลังเป็นค่าคงตัว กับการที่เลขชี้กำลังเป็นตัวแปร n ต่างกันมาก สังเกตว่าเมื่อ n = 4 จะได้
ถึงตอนนี้ยังได้ค่าเท่ากัน แล้วถ้า n = 10 ล่ะ
อ้าว ฟังก์ชันเอกซ์โพเนนเชียลพุ่งขึ้นไปจนมากกว่าฟังก์ชันกำลังสองประมาณสิบเท่าในทันที แล้วถ้า n = 20 จะได้เท่าใด
เมื่อ n = 20 ความซับซ้อนแบบเอกซ์โพเนนเชียลมีค่ามากกว่าความซับซ้อนกำลังสองประมาณ 2,600 เท่า จะเห็นว่าฟังก์ชันเอกซ์โพเนนเชียลเพิ่มขึ้นเร็วกว่าฟังก์ชันกำลังสอง มาก ลองนึกถึงเรื่องนี้เมื่อเกิดโรคระบาดครั้งต่อไปที่แพร่ในประชากรด้วยอัตราแบบเอกซ์โพเนนเชียล
ดังนั้นถ้ามีกระดาษยี่สิบแผ่น ก็ต้องตรวจการจัดหมู่ 1,048,576 แบบ ซึ่งมากทีเดียว
การตรวจสอบความถูกต้องของผลลัพธ์
การ ตรวจสอบ ว่ากลุ่มของจำนวนที่ได้มีผลบวกเท่ากับ 0 จริงหรือไม่ จะใช้เวลานานเท่าใด ค่อนข้างเร็ว เพียงบวกจำนวนกลุ่มนี้กลุ่มเดียว ถ้าผลบวกเท่ากับ 0 ก็แสดงว่าพบกลุ่มกระดาษที่ถูกต้อง ถ้าผลบวกเป็นค่าอื่น ก็แสดงว่าพบกลุ่มกระดาษที่ผิด
จะเห็นอีกครั้งว่าการตรวจผลลัพธ์ง่ายกว่าการหาผลลัพธ์มาก
ปัญหาที่ 4: ปัญหาการเดินทางของพนักงานขาย
ปัญหาการเดินทางของพนักงานขาย (travelling salesman problem) เป็นปัญหาเชิงอัลกอริทึมที่มีชื่อเสียงที่สุดปัญหาหนึ่ง กล่าวโดยย่อ มีพนักงานขายคนหนึ่งที่ขายฝน พนักงานขายคนนี้ต้องเดินทางมากเพื่อหาเลี้ยงชีพ จึงตัดสินใจไปเยือนทุกจังหวัดในภาคใต้ของประเทศไทย และเพราะไม่อยากสิ้นเปลือง จึงตั้งใจจะหาเส้นทางที่สั้นที่สุดที่ผ่านตัวเมืองของทุกจังหวัดในภาคใต้ หน้าที่ของเราคือหาเส้นทางที่สั้นที่สุดนั้น
จะหาเส้นทางที่สั้นที่สุดนี้ได้อย่างไร ลองทุกกรณี
ทำให้ง่ายขึ้นได้ สมมติว่าระหว่างตัวเมืองของจังหวัดสองจังหวัดใด ๆ มีเส้นทางที่สั้นที่สุดเพียงเส้นทางเดียว จะหาเส้นทางที่สั้นที่สุดที่ผ่านทุกเมืองได้อย่างไร ภาคใต้มี 14 จังหวัด จึงเลือกจุดเริ่มต้นได้ 14 แบบ สมมติว่าเริ่มที่ภูเก็ต!!! จากภูเก็ตไปที่ใดได้บ้าง ในทางทฤษฎีไปตัวเมืองของจังหวัดใดก็ได้ จึงเลือกได้จาก 13 เมืองที่เหลือ
ตอนนี้ก็คำนวณได้แล้วว่ามีวิธีไปเยือนสองเมืองแรกทั้งหมด 14 × 13 วิธี คือเลือกจุดเริ่มต้นได้ 14 แบบ แล้วเลือกเมืองถัดไปจาก 13 เมืองที่เหลือ
เมื่อถึงเมืองที่สองแล้วต้องเดินทางต่อ ไปมาแล้วสองเมือง จึงเดินทางไปได้หนึ่งใน 12 เมืองที่เหลือ จึงมีวิธีไปเยือนสามเมืองแรกทั้งหมด 14 × 13 × 12 วิธี
เมื่อไปเยือนเมืองที่สามแล้ว ต้องเลือกหนึ่งใน 11 เมืองที่เหลือ แล้วเลือกหนึ่งใน 10 เมืองที่เหลือ ไปเรื่อย ๆ
เมื่อไปเยือนครบทุกเมือง จะพบว่ามีทางเลือกทั้งหมด
แบบ ซึ่งอาจทำให้นึกถึงแฟกทอเรียลที่เขียนด้วยเครื่องหมายอัศเจรีย์ จึงกล่าวได้ว่าผลคูณนี้เท่ากับ 14!:
ดังนั้นมีเส้นทางที่ผ่านตัวเมืองของทุกจังหวัดในภาคใต้ทั้งหมด 14! เส้นทาง มากหรือไม่ ค่อนข้างมาก เพราะ
โดยทั่วไป ถ้าหาเส้นทางที่สั้นที่สุดผ่าน n เมือง ต้องลองเส้นทางที่ต่างกัน n! เส้นทาง วิธีแก้ปัญหานี้จึงมีความซับซ้อน n!
จะ ตรวจสอบ ได้อย่างไรว่าพบผลลัพธ์ที่ถูกต้อง ถ้ามีคนบอกว่าเส้นทางที่สั้นที่สุดคือจากกระบี่ไปภูเก็ต แล้วไปสงขลา และต่อไปเรื่อย ๆ จะตรวจได้อย่างไรว่าเขาพูดจริง ยากมาก 🤷♂ เพราะเมื่อดูเส้นทางนั้น ก็ไม่มีวิธีง่าย ๆ ที่จะตรวจว่าเส้นทางนี้สั้นที่สุดจริงหรือไม่ ที่จริงต้องคำนวณใหม่ทั้งหมด การตรวจสอบผลลัพธ์จึงมีความซับซ้อน n! เช่นกัน
คลาส P และ NP
เราได้ดูปัญหาสี่ข้อและอัลกอริทึมที่ใช้แก้ปัญหาเหล่านั้น และวิเคราะห์แล้วว่าการหาคำตอบยากเพียงใด และการตรวจคำตอบยากเพียงใด สรุปได้ในตารางนี้:
| ปัญหา | ความซับซ้อนของการแก้ปัญหา | ความซับซ้อนของการตรวจสอบ |
|---|---|---|
| จำนวนที่น้อยที่สุด | n | n |
| ผลคูณของคู่จำนวน | n2 | 1 |
| ผลบวกของสับเซต | 2n | n |
| พนักงานขาย | n! | n! |
ตอนนี้จะแบ่งปัญหาออกเป็นสองกลุ่ม กลุ่มแรกคือปัญหาที่แก้ได้ ง่าย ได้แก่ปัญหาที่แก้ได้ด้วยความซับซ้อน n หรือ n2 หรือ n3 หรือ n4 ฯลฯ เนื่องจากนิพจน์อย่าง n2 เรียกว่า พหุนาม (polynomial) จึงเรียกคลาสของปัญหานี้ด้วยตัวอักษร P กล่าวคือ คลาส P ประกอบด้วยปัญหาที่แก้ได้ในเวลาพหุนาม (นั่นคือมีความซับซ้อน เช่น n2 หรือ n7) โดยทั่วไปเป็นปัญหาที่แก้ได้ค่อนข้าง ง่าย
ปัญหาที่ 1 การหาจำนวนที่น้อยที่สุด จึงอยู่ในคลาส P เพราะมีความซับซ้อนของการแก้ปัญหาเป็น n และปัญหาที่ 2 ผลคูณของคู่จำนวน ก็อยู่ในคลาสนี้ด้วย เพราะมีความซับซ้อนของการแก้ปัญหาเป็น n2 ซึ่งทั้งสองเป็นพหุนาม
คลาสที่สองคือคลาส NP ซึ่งประกอบด้วยปัญหาที่ ตรวจสอบ ได้ในเวลาพหุนาม ปัญหาทุกข้อจึงอยู่ในคลาส NP ยกเว้นข้อสุดท้าย เราไม่สามารถตรวจสอบปัญหาการเดินทางของพนักงานขายได้ในเวลาพหุนาม ส่วนสามปัญหาแรกตรวจสอบได้ในเวลาพหุนาม
ปัญหาการเดินทางของพนักงานขายนั้น เราไม่สามารถทั้งแก้และตรวจสอบได้ในเวลาพหุนาม จึงต้องมีอีกคลาสหนึ่งที่ประกอบด้วยปัญหาที่ยากยิ่งขึ้นไปอีก คลาสนี้มีอยู่จริง แต่ตอนนี้ยังไม่ใช่เรื่องที่น่าสนใจสำหรับเรา
เห็นได้ชัดว่าคลาส P เป็นสับเซตของคลาส NP นั่นคือปัญหาทุกข้อที่อยู่ในคลาส P ก็อยู่ในคลาส NP ด้วย ซึ่งสมเหตุสมผล ถ้า แก้ ปัญหาได้ในเวลาพหุนาม ก็ ตรวจสอบ ผลลัพธ์ได้ในเวลาพหุนามเช่นกัน
ปัญหา P กับ NP
แล้วในทางกลับกันเป็นจริงด้วยหรือไม่ ปัญหาทุกข้อในคลาส NP อยู่ในคลาส P ด้วยหรือไม่ กล่าวคือ ถ้ามีวิธี ตรวจสอบ ผลลัพธ์ของปัญหาในเวลาพหุนาม จะมีอัลกอริทึมที่ แก้ ปัญหานั้นในเวลาพหุนามด้วยหรือไม่
ตัวอย่างเช่น เรารู้ว่า ตรวจสอบ ผลลัพธ์ของปัญหาที่ 3 ผลบวกของสับเซต ได้ในเวลาพหุนาม แต่อัลกอริทึมที่ใช้แก้ปัญหานี้ไม่ใช่อัลกอริทึมเวลาพหุนาม อัลกอริทึมที่ใช้มีความซับซ้อนแบบเอกซ์โพเนนเชียล 2n แต่เรารู้แน่หรือว่าไม่มีอัลกอริทึมที่มีความซับซ้อนแบบพหุนามสำหรับปัญหานี้
เราไม่รู้
อาจเป็นไปได้ว่าปัญหาทุกข้อที่ ตรวจสอบ ได้ในเวลาพหุนาม มีอัลกอริทึมที่ แก้ ปัญหานั้นได้ในเวลาพหุนาม เราไม่รู้ เราพิสูจน์ไม่ได้ว่ามีอัลกอริทึมแบบนั้น และก็พิสูจน์ไม่ได้ว่าไม่มี
ถ้าปัญหาทุกข้อในคลาส NP มีอัลกอริทึมที่แก้ได้ในเวลาพหุนาม ก็หมายความว่าคลาส NP เท่ากับคลาส P ปัญหาทุกข้อในคลาส P อยู่ในคลาส NP และปัญหาทุกข้อในคลาส NP อยู่ในคลาส P สองคลาสนี้จึงเท่ากัน เป็นคลาสเดียวกัน
ปัญหา P กับ NP จึงเป็นคำถามว่า คลาส P เป็นคลาสเดียวกับคลาส NP หรือเป็นคลาสของปัญหาสองคลาสที่ต่างกัน
ดังนั้น P = NP หรือ P ≠ NP อย่างใดอย่างหนึ่ง ยังไม่มีใครรู้ ถ้าใครหาคำตอบได้ จะได้รับรางวัลหนึ่งล้านดอลลาร์สหรัฐ ชื่อเสียงที่ไม่มีวันเลือนหาย และอาจได้รางวัลทัวริง (Turing Award) ซึ่งเปรียบได้กับรางวัลโนเบลของวงการวิทยาการคอมพิวเตอร์ด้วย
จะเกิดอะไรขึ้นถ้า P = NP
จะเกิดอะไรขึ้นถ้า P = NP บอกได้ไม่ง่ายนัก เราจะรู้ว่าปัญหาทุกข้อในคลาส NP มีอัลกอริทึมที่แก้ได้ในเวลาพหุนาม เช่น ปัญหาที่ 3 ผลบวกของสับเซต มีอัลกอริทึมที่แก้ได้ในเวลาพหุนาม แต่เรื่องนี้มีข้อแม้สามข้อ:
- การรู้ว่ามีอัลกอริทึมแบบนั้นอยู่ ไม่ได้หมายความว่าจะหาอัลกอริทึมนั้นได้ เราจะรู้เพียงว่ามีอัลกอริทึมที่แก้ปัญหาได้ในเวลาพหุนามอยู่จริง แต่อาจสร้างอัลกอริทึมนั้นไม่ได้ไปอีกร้อยปี คล้ายกับที่ทฤษฎีสัมพัทธภาพทั่วไปทำนายว่ามีหลุมดำ แต่ก็ยังต้องใช้เวลาอีกหลายสิบปีกว่าจะถ่าย “ภาพ” หลุมดำภาพแรกได้
- น่าเสียดายที่การมีอัลกอริทึมเวลาพหุนามไม่ได้หมายความว่าอัลกอริทึมนั้นจะ เร็ว เราอาจพบอัลกอริทึมที่มีความซับซ้อน n100 เพราะนิพจน์ n100 ก็เป็นพหุนาม ถ้าเปรียบเทียบความซับซ้อน 2n กับ n100 จะพบว่าเมื่อ n ยังค่อนข้างเล็ก อัลกอริทึมที่มีความซับซ้อน 2n ยังใช้จำนวนการดำเนินการน้อยกว่า เช่น เมื่อ n = 20 จะได้ 220 = 1,048,576 ขณะที่ 20100 เป็นจำนวนที่มีประมาณ 130 หลัก ซึ่งมากกว่า 1,048,576 ราว 10 ยกกำลัง 120 เท่า ในความเป็นจริงอัลกอริทึมเวลาพหุนามนี้จึงช้ากว่าอัลกอริทึมแบบเอกซ์โพเนนเชียล อย่างน้อยก็ตราบที่ n ยังค่อนข้างเล็ก
- ถ้าหาอัลกอริทึมเวลาพหุนามที่เร็วได้จริง ก็จะแก้ปัญหาได้มากมายเร็วขึ้นและแม่นยำขึ้น ซึ่งแน่นอนว่าเป็นข่าวดี แต่ก็มีข้อเสียด้วย มีศาสตร์หนึ่งที่อาศัยความจริงที่ว่าปัญหาบางข้อแก้ได้ยาก คือวิทยาการรหัสลับ (cryptography) หรือการเข้ารหัส จึงอาจเป็นไปได้ว่าการเจาะรหัสที่ใช้กันในปัจจุบันจะง่ายขึ้นมาก
คั่นรายการ: เป็นรางวัลสำหรับผู้ที่อ่านมาถึงตรงนี้ ขอเฉลยว่าคำตอบของปัญหาที่ 3 คือ 24 + 1 − 60 + 16 − 83 + 48 + 54
จะเกิดอะไรขึ้นถ้า P ≠ NP
ถ้าคลาสของปัญหา P และ NP เป็นคลาสที่ต่างกัน ก็จะไม่มีอะไรเปลี่ยนไปมากนัก เพราะนั่นคือสภาพที่เป็นอยู่ในปัจจุบัน ตอนนี้เรายังไม่มีอัลกอริทึมที่แก้ปัญหายากใด ๆ ใน NP ได้ในเวลาพหุนาม และถ้ามีใครพิสูจน์ได้ว่า P ≠ NP ก็จะเป็นเช่นนี้ตลอดไป การพิสูจน์ว่า P = NP จะเป็นข่าวใหญ่กว่ามาก
การอ้างถึงในวัฒนธรรมสมัยนิยม
- ในการ์ตูนเรื่อง The Simpsons ตอนหนึ่ง โฮเมอร์ไปอยู่ในโลกคู่ขนานที่มีข้อความปรากฏขึ้นว่า P = NP ดูได้ที่ youtube.com
- ส่วนในการ์ตูนเรื่อง Futurama มีฉากที่ในโกดังมีแฟ้มสองแฟ้ม แฟ้มหนึ่งชื่อ P และอีกแฟ้มหนึ่งชื่อ NP ดูได้ที่ youtube.com
- ตอนที่สองของซีซันที่สอง ของซีรีส์ Elementary ชื่อตอน “Solve for X” เล่าถึงการฆาตกรรมนักคณิตศาสตร์ซึ่งน่าจะแก้ปัญหา P กับ NP ได้