✖

ปัญหาที่ใหญ่ที่สุดในวิทยาการคอมพิวเตอร์: ปัญหา 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 ตัวอย่างเช่น ให้กองของจำนวนเป็นดังนี้:

A={49,11,32,54,15}B={17,64,74,61,21}

จะหาคู่จำนวนที่ผลคูณเท่ากับ 918 ได้อย่างไร วิธีง่าย ๆ คือลองทุกกรณี มีกี่กรณี ค่อนข้างมาก คือ 25 กรณี เริ่มจากนำจำนวนแรกในกอง A คือ 49 คูณกับจำนวนทุกจำนวนในกอง B:

49×17=83349×64=313649×74=362649×61=298949×21=1029

ไม่มีคู่ใดได้ 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: ผลบวกของสับเซต

มาดูปัญหาที่สาม คราวนี้มีกระดาษสิบสองแผ่นที่เขียนจำนวนไว้ และต้องหากระดาษกี่แผ่นก็ได้ที่ผลบวกเท่ากับศูนย์ ตัวอย่างเช่น:

A={24,−69,1,−15,−76,−60,16,−83,48,−22,54,−47}

จงเลือกจำนวนกลุ่มหนึ่งจากจำนวนเหล่านี้ที่ผลบวกเท่ากับ 0 ตัวอย่างเช่น จำนวน

24+48−69+1

มีผลบวกเท่ากับ 4 จึงไม่ใช่คำตอบที่ถูกต้อง คำตอบที่ถูกต้องคือกลุ่มของจำนวน… เอาเป็นว่า ลองหาเองเป็นการบ้าน 😉 มีจำนวนเพียงกลุ่มเดียวที่ผลบวกเท่ากับ 0 อย่างน้อยก็จะได้รู้ว่าปัญหานี้ยากเพียงใด

ต่อไปต้องหาความซับซ้อนของปัญหานี้ การคำนวณไม่ง่ายนัก เหมาะกับผู้ที่สนใจเป็นพิเศษ ถ้าสนใจว่าคำนวณความซับซ้อนของปัญหานี้อย่างไร ให้อ่านต่อ ถ้าไม่สนใจก็ข้ามไปหัวข้อถัดไปได้ ⏩

จะหากลุ่มของจำนวนที่ผลบวกเท่ากับ 0 ได้อย่างไร ต้องลองทุกการจัดหมู่ที่เป็นไปได้ คือต้องลองทุกคู่ ทุกกลุ่มสามจำนวน สี่จำนวน ห้าจำนวน ไปเรื่อย ๆ และตรวจว่าผลบวกของแต่ละกลุ่มเท่ากับศูนย์หรือไม่ การจัดหมู่แบบนี้มีกี่แบบ

ลองดูจากเซตที่เล็กกว่า จากจำนวนสามจำนวน B = {5, 7, 9} สร้างกลุ่มของจำนวน หรือสับเซต ที่ต่างกันได้กี่กลุ่ม มีทั้งหมดแปดกลุ่ม:

B1={}B2={5}B3={7}B4={9}B5={5,9}B6={5,7}B7={7,9}B8={5,7,9}

สังเกตว่านับเซตว่าง B1 รวมไปด้วย ตอนนี้ยังไม่มีประโยชน์นัก แต่ใส่ไว้เพื่อความครบถ้วน เพื่อให้คำนวณง่ายขึ้น จะกำหนดลำดับเลขฐานสอง (binary vector) ให้แต่ละสับเซต ลำดับเลขฐานสองก็คือลำดับของศูนย์และหนึ่ง เช่น 00101010 ในที่นี้จะใช้ลำดับเลขฐานสองที่ยาวสามหลัก โดยกำหนด 101 ให้สับเซตที่มี “จำนวนที่หนึ่งและที่สามจากเซตเดิม แต่ไม่มีจำนวนที่สอง” คือเซต {5, 9} กำหนด 110 ให้สับเซตที่มี “จำนวนที่หนึ่งและที่สองจากเซตเดิม แต่ไม่มีจำนวนที่สาม” คือเซต {5, 7} เป็นต้น

B1={}→000B2={5}→100B3={7}→010B4={9}→001B5={5,9}→101B6={5,7}→110B7={7,9}→011B8={5,7,9}→111

จะเห็นว่าสับเซตแต่ละสับเซตมีลำดับเลขฐานสองยาวสามหลักเพียงลำดับเดียว และลำดับเลขฐานสองยาวสามหลักแต่ละลำดับก็ตรงกับสับเซตเพียงสับเซตเดียว ดังนั้นถ้าคำนวณได้ว่ามีลำดับเลขฐานสองยาว 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 หลักที่ต่างกันทั้งหมด ซึ่งเท่ากับ

2×2×…×2⏟n ตัว=2n

2n หรือ n2 ต่างกันตรงไหน 🤷‍♂

ดังนั้นจากเซตที่มีจำนวน n จำนวน สร้างสับเซตที่ต่างกันได้ 2n สับเซต ในกรณีนี้มี n = 12 จำนวน จึงต้องตรวจการจัดหมู่ที่ต่างกัน 212 แบบ คือ 4096 แบบ กล่าวว่าปัญหานี้มีความซับซ้อน 2n คือความซับซ้อนแบบเอกซ์โพเนนเชียล เพราะอธิบายได้ด้วยฟังก์ชันเอกซ์โพเนนเชียล

สังเกตว่าปัญหาก่อนหน้ามีความซับซ้อน n2 ส่วนปัญหานี้มีความซับซ้อน 2n ดูคล้ายกันมาก ใช่ไหม แต่การที่เลขชี้กำลังเป็นค่าคงตัว กับการที่เลขชี้กำลังเป็นตัวแปร n ต่างกันมาก สังเกตว่าเมื่อ n = 4 จะได้

n2=42=162n=24=16

ถึงตอนนี้ยังได้ค่าเท่ากัน แล้วถ้า n = 10 ล่ะ

n2=102=1002n=210=1024

อ้าว ฟังก์ชันเอกซ์โพเนนเชียลพุ่งขึ้นไปจนมากกว่าฟังก์ชันกำลังสองประมาณสิบเท่าในทันที แล้วถ้า n = 20 จะได้เท่าใด

n2=202=4002n=220=1 048 576

เมื่อ 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×13×12×11×10×9×8×7×6×5×4×3×2×1

แบบ ซึ่งอาจทำให้นึกถึงแฟกทอเรียลที่เขียนด้วยเครื่องหมายอัศเจรีย์ จึงกล่าวได้ว่าผลคูณนี้เท่ากับ 14!:

14!=14×13×12×11×10×9×8×7×6×5×4×3×2×1

ดังนั้นมีเส้นทางที่ผ่านตัวเมืองของทุกจังหวัดในภาคใต้ทั้งหมด 14! เส้นทาง มากหรือไม่ ค่อนข้างมาก เพราะ

14!=87 178 291 200

โดยทั่วไป ถ้าหาเส้นทางที่สั้นที่สุดผ่าน 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 ได้