อัลกอริธึมที่กล่าวถึงในบทก่อน ๆ มีอัตราเวลาในการทำงาน (runtimes) ที่แตกต่างกัน ตัวอย่างเช่น การหาสมาชิกที่เล็กที่สุดในลิสต์ที่ยังไม่ได้เรียงต้องใช้เวลาแบบ linear (เชิงเส้น) ในขณะที่ในลิสต์ที่เรียงแล้วอาจใช้เวลาแบบ constant (คงที่) ในทำนองเดียวกัน การค้นหาองค์ประกอบเฉพาะในลิสต์ที่ไม่ได้เรียงใช้เวลาแบบ linear แต่สามารถทำได้ในเวลาแบบ logarithmic เมื่อใช้ sorted array หรือ balanced binary search tree โครงสร้างข้อมูลที่ถูกเรียงล่วงหน้าจึงมีผลต่อประสิทธิภาพของอัลกอริธึม อย่างไรก็ตาม อัลกอริธึมต่างชนิดกันอาจมี runtimes แตกต่างกันแม้กับอินพุตชุดเดียวกัน—เช่น selection sort เป็นอัลกอริธึมแบบ quadratic ในขณะที่ mergesort มี runtime แบบ linearithmic

อัลกอริธึมที่มีเวลาแบบ quadratic อาจช้าจนไม่สามารถใช้งานได้จริง ลองพิจารณางานจัดเรียงชื่อผู้อยู่อาศัยทั้งหมดจำนวนประมาณ 300 ล้านคน ในสหรัฐฯ หากรันบนคอมพิวเตอร์ที่ทำงานได้พันล้านคำสั่งต่อวินาที selection sort จะต้องใช้เวลาประมาณ 90 ล้านวินาที หรือราว 2 ปี 10 เดือน ซึ่งไม่เป็นไปได้ในทางปฏิบัติ ในทางกลับกัน mergesort ที่มีเวลาแบบ linearithmic จะทำงานเดียวกันให้เสร็จภายในไม่ถึง 10 วินาที แต่ถ้าอินพุตมีขนาดปานกลาง เราอาจไม่ต้องกังวลมากนักเกี่ยวกับความซับซ้อนของเวลา โดยเฉพาะเมื่อคอมพิวเตอร์มีความเร็วเพิ่มขึ้นทุกปี

ในเชิงอุปมา ให้พิจารณาวิธีการเดินทางที่แตกต่างกันสำหรับปัญหาการเดินทางต่าง ๆ เช่น ในการไปทำงานคุณอาจปั่นจักรยาน ขึ้นรถเมล์ หรือขับรถยนต์ แต่การข้ามมหาสมุทรแอตแลนติก ไม่มีวิธีเหล่านี้ที่เหมาะสม จะต้องขึ้นเรือสำราญหรือเครื่องบิน ในทางทฤษฎีคุณอาจพายเรือคายัคข้ามได้ แต่เวลาหรือทรัพยากรที่ต้องใช้ทำให้เกือบจะเป็นไปไม่ได้ในทางปฏิบัติ

ทำนองเดียวกัน ปัญหาทางคอมพิวเตอร์บางเรื่องมีวิธีแก้ได้ในทางทฤษฎี แต่การคำนวณนั้นใช้เวลานานเกินกว่าจะทำได้จริง บทนี้นำเสนอกรณีตัวอย่างของปัญหาในลักษณะนี้ โดยผมจะยกตัวอย่างปัญหาบางอย่างที่จนถึงตอนนี้รู้วิธีแก้ได้เพียงโดยอัลกอริธึมที่มี exponential runtime กล่าวคือ เวลาในการรันเพิ่มขึ้นแบบทวีคูณตามขนาดของอินพุต อัลกอริธึมแบบ exponential จึงไม่สามารถใช้งานได้จริงนอกจากอินพุตที่มีขนาดเล็กมาก ซึ่งทำให้คำถามเรื่อง lower bounds และว่ามีอัลกอริธึมที่เร็วกว่าอยู่หรือไม่ มีความสำคัญเป็นพิเศษ คำถามนี้เป็นแกนกลางของปัญหา P = NP ซึ่งเป็นปัญหาสำคัญในวิทยาการคอมพิวเตอร์ที่ยังไม่ถูกแก้ไข

เช่นเดียวกับกรณีของการจัดเรียงผลลัพธ์ ผลลัพธ์ที่ดูเหมือนเป็นความผิดหวังแรกเริ่มเกี่ยวกับขอบเขตของวิทยาการคอมพิวเตอร์ ไม่จำเป็นต้องหมายความว่าเราต้องยอมแพ้ ถ้าไม่สามารถพัฒนาอัลกอริธึมที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งได้ เราไม่จำเป็นต้องละทิ้งปัญหานั้นเสมอไป โดยเฉพาะอย่างยิ่งเราสามารถออกแบบ approximation algorithms ที่คำนวณคำตอบที่ไม่แม่นยำเป๊ะ ๆ แต่เพียงพอสำหรับการใช้งานจริง นอกจากนี้ ข้อเท็จจริงที่ว่าปัญหาใดปัญหาหนึ่งแก้ไม่ได้ในทางปฏิบัติ บางครั้งก็สามารถนำมาใช้เป็นประโยชน์ในการแก้ปัญหาอื่น ๆ ได้

ในขณะที่อินพุตขนาดใหญ่ทำให้เห็นความแตกต่างระหว่างอัลกอริธึมแบบ quadratic กับแบบ linearithmic แต่ในอินพุตขนาดเล็ก อัลกอริธึมแบบ quadratic อาจทำงานได้ดี เช่น การจัดเรียงลิสต์ขนาด 10,000 รายการด้วย selection sort จะใช้เวลาประมาณหนึ่งในสิบวินาทีบนคอมพิวเตอร์ที่ทำงานได้พันล้านคำสั่งต่อวินาที ถึงแม้เวลาในการรันในกรณีนี้จะแทบไม่สังเกตเห็น แต่การเพิ่มขนาดลิสต์ขึ้นสิบเท่าจะเพิ่มเวลาในการรันเป็นร้อยเท่า ดังนั้นการจัดเรียงลิสต์ขนาด 100,000 รายการจะใช้เวลาประมาณ 10 วินาที ซึ่งในสถานการณ์ที่ผู้ใช้คาดหวังการตอบสนองทันทีอาจไม่ยอมรับได้ อย่างไรก็ตาม คอมพิวเตอร์รุ่นถัดไปอาจแก้ปัญหานี้ทำให้อัลกอริธึมกลับมาใช้งานได้อีกครั้ง ความก้าวหน้าทางเทคโนโลยีอาจช่วยยืดขีดจำกัดของอัลกอริธึมแบบ quadratic แต่เราก็ไม่สามารถหวังพึ่งผลนี้เพื่อทำให้อัลกอริธึมที่มี exponential runtime ใช้งานได้จริง

Tipping the Scale (การเอียงของตาชั่ง)

ตอนต้นของเรื่อง Raiders of the Lost Ark นั้น Indiana Jones สำรวจถ้ำเพื่อค้นหาไอดอลทองคำล้ำค่า ไอดอลวางอยู่บนตาชั่งที่ออกแบบมาให้กระตุ้นกับดักอันตรายหากไอดอลถูกย้าย เพื่อหลีกเลี่ยงกลไกป้องกัน Indiana Jones จึงแทนที่ไอดอลด้วยถุงทรายที่หวังว่าจะมีน้ำหนักใกล้เคียง แต่ถุงทรายกลับหนักเกินไปและกระตุ้นกับดัก ทำให้เกิดการหนีออกจากถ้ำอย่างตื่นเต้น

ถ้า Indiana Jones รู้จักน้ำหนักที่แน่นอนของไอดอล เขาอาจเติมทรายให้ถุงมีน้ำหนักเท่ากับไอดอล และการออกจากถ้ำคงจะไม่ตื่นเต้นเท่านี้ แต่เนื่องจากเขาอาจไม่มีตาชั่งพกพา จึงต้องประมาณน้ำหนักด้วยวิธีอื่น โชคดีที่การประดิษฐ์ตาชั่งสมดุลไม่ใช่เรื่องยาก หลัก ๆ คือใช้คันไม้ ขึงถุงทรายไว้ด้านหนึ่งและวางน้ำหนักมาตรฐานไว้ด้านตรงข้าม แล้วเติมทรายจนคันไม้สมดุล ถ้า Indiana Jones ไม่มีวัตถุที่มีน้ำหนักเท่ากับไอดอล เขาต้องประมาณน้ำหนักจากการรวมวัตถุต่าง ๆ ซึ่งดูเหมือนเป็นปัญหาที่ไม่ซับซ้อนนัก สมมติว่าไอดอลคาดว่าน้ำหนักประมาณ 42 ออนซ์ (ประมาณ 2.6 ปอนด์ หรือ 1.2 กก.) และเขามีวัตถุ 6 ชิ้นที่หนัก 5, 8, 9, 11, 13, และ 15 ออนซ์ตามลำดับ หลังลองจับคู่หลายครั้งเขาจะพบว่า 5, 9, 13 และ 15 ออนซ์รวมกันได้พอดี 42 ออนซ์

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

วิธีการตรงไปตรงมาสำหรับแก้ปัญหาการชั่งน้ำหนักคือสร้างชุดผสมของวัตถุทุกชุดอย่างเป็นระบบแล้วตรวจดูแต่ละชุดว่าน้ำหนักรวมเท่ากับน้ำหนักเป้าหมายหรือไม่ กลยุทธ์นี้เรียกว่า generate-and-test เพราะประกอบด้วยสองขั้นตอนซ้ำ ๆ: (1) generate — สร้างคำตอบที่เป็นไปได้ และ (2) test — ตรวจว่าคำตอบนั้นเป็นไปตามเงื่อนไขจริงหรือไม่ ในกรณีนี้ ขั้นตอนการ generate ผลิตชุดของวัตถุ และขั้นตอนการ test รวมค่าน้ำหนักของวัตถุแล้วเปรียบเทียบกับน้ำหนักเป้าหมาย สำคัญว่าขั้นตอนการ generate ต้องทำอย่างเป็นระบบและครอบคลุมทุกกรณี มิฉะนั้นอัลกอริธึมอาจพลาดคำตอบ

เวลาในการรันของวิธี generate-and-test ขึ้นกับจำนวนชุดผสมที่สามารถสร้างได้ เพื่อเข้าใจจำนวนชุดผสม ให้พิจารณาวิธีการสร้างชุดผสมใดชุดหนึ่งจากวัตถุทั้งหมด เช่น พิจารณาชุด 5, 9, และ 11 สำหรับวัตถุแต่ละชิ้น เราสามารถถามได้ว่าชิ้นนั้นถูกเลือกหรือไม่ เช่น 5 ถูกเลือกแต่ 8 ไม่ถูกเลือก 9 และ 11 ถูกเลือก แต่ 13 และ 15 ไม่ถูกเลือก กล่าวคือ ชุดผสมใด ๆ เกิดจากการตัดสินใจของแต่ละชิ้นว่าจะรวมหรือไม่รวม และการตัดสินใจแต่ละชิ้นเป็นอิสระจากกัน

เราสามารถเปรียบกระบวนการสร้างชุดผสมกับการกรอกแบบสอบถามที่มีช่องทำเครื่องหมายข้างรายการวัตถุ แต่ละชุดผสมสอดคล้องกับการกรอกแบบสอบถามโดยติ๊กช่องของวัตถุที่เลือก จำนวนชุดผสมจึงเท่ากับจำนวนวิธีการกรอกแบบสอบถาม และที่นี่เราจะเห็นว่าทุกช่องสามารถติ๊กหรือไม่ติ๊กได้อย่างเป็นอิสระจากช่องอื่น ๆ

ดังนั้น จำนวนชุดผสมที่เป็นไปได้จึงเท่ากับผลคูณของจำนวนทางเลือกที่มี ซึ่งคือ 2 สำหรับการเลือกหรือไม่เลือกวัตถุแต่ละชิ้น เนื่องจาก Indiana Jones มีวัตถุ 6 ชิ้น จำนวนชุดผสมจึงเป็น 2 คูณด้วยตัวมันเองหกครั้ง นั่นคือ 2 × 2 × 2 × 2 × 2 × 2 = 2^6 = 64. เนื่องจากอัลกอริธึม generate-and-test ต้องทดสอบทุกชุด เวลาในการรันจึงเพิ่มขึ้นตามอัตรานี้ ในความเป็นจริง ยังต้องใช้เวลาเพิ่มขึ้นกว่านี้ เนื่องจากการทดสอบแต่ละชุดยังต้องรวมค่าน้ำหนักทั้งหมดแล้วเปรียบเทียบกับน้ำหนักเป้าหมาย

When Runtime Explodes (เมื่อเวลาในการรันพุ่งขึ้นอย่างมาก)

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

ในบางครั้ง ผู้คนใช้ข้ออ้างเรื่องความเร็วของฮาร์ดแวร์มาแก้ปัญหาการเลือกอัลกอริธึมที่มี runtime แย่ ข้อโต้แย้งมักเป็นประมาณว่า “ใช่ ฉันรู้ว่าอัลกอริธึมนี้ใช้เวลาหลายนาที แต่รอจนกว่าเราจะได้คอมพิวเตอร์ที่เร็วขึ้น ปัญหานี้จะหายไป” ข้อโต้แย้งนี้มีเหตุผลบางส่วน เพราะกฎของ Moore บอกว่าความเร็วของคอมพิวเตอร์จะเพิ่มเป็นสองเท่าประมาณทุก 18 เดือน

เมื่อความเร็วของคอมพิวเตอร์เพิ่มเป็นสองเท่า อัลกอริธึมแบบ quadratic จะสามารถจัดการอินพุตที่ใหญ่ขึ้นได้ประมาณ 1.4 เท่า แต่พิจารณาผลกระทบกับอัลกอริธึมแบบ exponential หากต้องการให้เวลาในการรันเพิ่มขึ้นไม่เกินสองเท่า เราจะสามารถเพิ่มขนาดอินพุตได้เพียงหนึ่งหน่วยเท่านั้น เพราะเวลาในการรันเพิ่มเป็นสองเท่าทุกครั้งที่อินพุตเพิ่มขึ้นหนึ่งหน่วย กล่าวคือ เราต้องเพิ่มความเร็วของคอมพิวเตอร์เป็นสองเท่าเพื่อประมวลผลอินพุตที่เพิ่มขึ้นเพียงหนึ่งองค์ประกอบเท่านั้น

Table 7.1 Approximate runtimes for different sizes of input on a computer that can perform a billion steps per second.

Input Size	Linear	Linearithmic	Quadratic	Exponential
20				0.001 second
50				13 days
100
1,000
10,000			0.1 second
1 million	0.001 second	0.002 second	16 minutes
1 billion	1 second	30 seconds	32 years

Note: ช่องว่างหมายถึง runtimes ที่น้อยกว่า 1 มิลลิวินาที เล็กจนไม่มีความหมายต่อการรับรู้ของมนุษย์ และจึงไม่มีความสำคัญทางปฏิบัติ ช่องที่ทำเครื่องหมายสีเทาบ่งชี้ runtimes ที่ใหญ่เกินกว่าจะจินตนาการได้

เนื่องจากเวลาในการรันเพิ่มขึ้นอย่างรวดเร็ว การปรับปรุงทางเทคโนโลยีที่เพิ่มความสามารถการประมวลผลขึ้นเป็นปัจจัยคงที่จึงไม่เพียงพอที่จะปรับขนาดอัลกอริธึมแบบ exponential ให้รองรับอินพุตที่ใหญ่ขึ้นอย่างมีนัยสำคัญ ให้สังเกตว่าแม้จะเพิ่มความเร็วขึ้นเป็นตัวคูณใหญ่ เช่น 10 ก็ไม่ได้เปลี่ยนแปลงมากนัก—แม้จะทำให้อัลกอริธึมแบบ quadratic จัดการอินพุตที่ใหญ่ขึ้นได้ประมาณ 3 เท่า แต่สำหรับอัลกอริธึมแบบ exponential การเพิ่มความเร็วเป็น 10 เท่าให้สามารถจัดการอินพุตที่เพิ่มขึ้นได้เพียง 3 เท่า เพราะเวลาในการรันจะเพิ่มขึ้นเป็น 2 × 2 × 2 = 2^3 = 8 เท่า

Table 7.1 แสดงช่องว่างมหาศาลระหว่างอัลกอริธึมที่มี runtime แบบ nonexponential และ exponential ในการจัดการขนาดอินพุตต่าง ๆ: runtimes สำหรับอัลกอริธึม nonexponential เริ่มมีความสังเกตได้เมื่ออินพุตมากกว่า 1,000 ขณะที่อัลกอริธึมแบบ exponential ทำได้ดีสำหรับอินพุตขนาด 20 หรือต่ำกว่า แต่สำหรับอินพุตขนาด 100 อัลกอริธึมแบบ exponential จะใช้เวลามากกว่า 400 พันล้านศตวรรษ ซึ่งมากกว่าอายุของจักรวาลถึง 2,900 เท่า

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

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

ช่องว่างอันมากระหว่างขนาดอินพุตที่อัลกอริธึมแบบ exponential และ nonexponential จัดการได้นั้นชี้ให้เห็นความแตกต่างระหว่างอัลกอริธึมที่ใช้ได้จริง (practical algorithms) ซึ่งมี runtime น้อยกว่า exponential กับอัลกอริธึมที่ไม่ใช่แบบปฏิบัติได้ (impractical algorithms) ซึ่งมี runtime เป็น exponential หรือแย่กว่า อัลกอริธึมที่มี exponential runtime จึงไม่ถือว่าเป็นวิธีแก้ปัญหาในทางปฏิบัติสำหรับอินพุตที่ไม่เล็กมากนัก เพราะใช้เวลานานเกินไป

Shared Destiny (โชคชะตาร่วมกัน)

อัลกอริธึม generate-and-test สำหรับปัญหาการชั่งน้ำหนักใช้ได้เฉพาะกับอินพุตขนาดเล็ก (น้อยกว่า 30 ประมาณนั้น) ซึ่งพอเพียงสำหรับสถานการณ์ที่ Indiana Jones เผชิญ แต่เนื่องจากการเติบโตแบบทวีคูณของเวลาในการรัน อัลกอริธึมนี้จะไม่สามารถจัดการอินพุตขนาด 100 หรือมากกว่าได้ เวลาในการรันแบบทวีคูณของอัลกอริธึมนี้ไม่ได้หมายความว่าจะไม่มีอัลกอริธึมที่มีประสิทธิภาพกว่าและมี runtime แบบ nonexponential แต่อย่างไรก็ตาม ปัจจุบันยังไม่มีอัลกอริธึมดังกล่าวที่เป็นที่รู้จัก

ปัญหาที่แก้ได้โดยอัลกอริธึมที่มี exponential (หรือแย่กว่า) runtime เท่านั้น เรียกว่า intractable เนื่องจากปัจจุบันเรารู้เพียงอัลกอริธึมแบบ exponential สำหรับปัญหาการชั่งน้ำหนัก จึงดูเหมือนว่าปัญหานี้อาจเป็น intractable แต่เราไม่สามารถแน่ใจเสมอไป บางทีอาจมีอัลกอริธึมแบบ nonexponential ที่ยังไม่ได้ค้นพบ หากเราสามารถพิสูจน์ได้ว่าไม่มีอัลกอริธึม nonexponential ใด ๆ สำหรับปัญหานั้น ก็จะทำให้เรารู้แน่นอนว่าปัญหานั้นเป็น intractable ขอบเขตล่าง (lower bound) อาจให้ความแน่นอนในแง่นี้

แต่ทำไมเราต้องสนใจเรื่องนี้? บางทีนักวิทยาการคอมพิวเตอร์อาจปล่อยมันไปแล้วไปศึกษาเรื่องอื่น แต่ปัญหาการชั่งน้ำหนักมีความคล้ายคลึงกับปัญหาอีกจำนวนหนึ่งที่มีคุณสมบัติสองประการที่น่าสนใจ: ประการแรก อัลกอริธึมที่เป็นที่รู้จักสำหรับแก้ปัญหาเหล่านี้มี runtime แบบ exponential เท่านั้น และประการที่สอง หากมีการค้นพบอัลกอริธึม nonexponential สำหรับปัญหาใดปัญหาหนึ่ง มันจะนำไปสู่การมีอัลกอริธึม nonexponential สำหรับปัญหาอื่น ๆ ทั้งหมด ปัญหาใดที่เป็นสมาชิกของกลุ่มพิเศษนี้ เรียกว่า NP-complete. ความสำคัญของปัญหา NP-complete มาจากข้อเท็จจริงที่ว่าปัญหาเชิงปฏิบัติจำนวนมากเป็น NP-complete และทั้งหมดมีความเสี่ยงว่าจะเป็น intractable

ในช่วงท้ายของการผจญภัย The Kingdom of the Crystal Skull เพื่อนร่วมทางของ Indiana Jones ชื่อ Mac เก็บของมีค่าหลายชิ้นในวิหารของหัวกะโหลกคริสตัล เขาพยายามหิ้วของให้ได้มากที่สุดเท่าที่จะทำได้ พร้อมกับเพิ่มมูลค่ารวมให้สูงสุด ปัญหานี้ ปัญหาการชั่งน้ำหนัก และปัญหาเรื่องการทานข้าวเป็นกลุ่ม ล้วนเป็นตัวอย่างของปัญหา knapsack ซึ่งตั้งชื่อตามงานที่ต้องเติมไอเท็มลงในกระเป๋าที่มีความจุจำกัดให้มากที่สุด โดยมีเป้าหมายคือเพิ่มมูลค่าหรือประโยชน์รวมของไอเท็มที่บรรจุ ในปัญหาการชั่งน้ำหนัก กระเป๋าเป้เปรียบเสมือตาชั่ง ขีดจำกัดคือค่าน้ำหนักที่ต้องวัด การบรรจุคือการวางวัตถุบนตาชั่ง และเป้าหมายเชิงปรับแต่งคือให้ใกล้เคียงน้ำหนักเป้าหมายที่สุด สำหรับปัญหาของ Mac ขีดจำกัดคือสิ่งที่เขาหิ้วได้ การบรรจุหมายถึงการเลือกไอเท็ม และการปรับแต่งคือการเพิ่มมูลค่ารวมของไอเท็มให้มากที่สุด ในปัญหาการทานข้าว ขีดจำกัดคือจำนวนเงินที่มีสำหรับซื้อ รายการที่บรรจุคือการเลือกรายการอาหาร และเป้าหมายคือการเพิ่มมูลค่าของการเลือกเมนูให้มากที่สุด

บังเอิญว่า ทั้ง Mac และ Indiana Jones ต่างล้มเหลว: Mac ใช้เวลามากเกินไปในการเลือกของและเสียชีวิตในวิหารที่พังทลาย ส่วนถุงทรายของ Indiana Jones กระตุ้นกับดัก แม้กระนั้นเขาก็สามารถหนีรอดได้ ยังไม่ชัดเจนว่าความล้มเหลวของพวกเขาเกิดจาก NP-completeness ของปัญหาที่พยายามแก้หรือไม่ แต่เหตุการณ์นี้ก็เตือนให้เห็นถึงความไม่สามารถแก้ได้ในทางปฏิบัติ

ปัญหา knapsack และแอปพลิเคชันของมันเป็นเพียงหนึ่งในปัญหา NP-complete มากมาย ตัวอย่างที่รู้จักกันดีอีกประการคือปัญหา traveling salesman ซึ่งขอเส้นทางรอบที่เชื่อมเมืองหลายเมืองโดยให้ความยาวรวมสั้นที่สุด วิธีง่าย ๆ คือสร้างเส้นทางรอบทั้งหมดแล้วหาอันที่สั้นที่สุด ความซับซ้อนของวิธีนี้เป็นแบบ exponential แต่แย่กว่าปัญหาการชั่งน้ำหนักมาก—for example, ขณะที่อัลกอริธึมการชั่งน้ำหนักอาจแก้ปัญหาขนาด 20 ได้ใน 1 มิลลิวินาที การคำนวณเส้นทางรอบสำหรับ 20 เมืองจะต้องใช้เวลาประมาณ 77 ปี การหาเส้นทางรอบไม่เพียงเป็นประโยชน์สำหรับพ่อค้าขายตามเมืองแต่ยังมีการใช้งานอื่น ๆ เช่น การวางแผนเส้นทางรถโรงเรียนหรือการจัดตารางทัวร์เรือสำราญ ปัญหาเชิงปรับแต่งอื่น ๆ จำนวนมากก็เป็น NP-complete

คุณสมบัติที่น่าสนใจของปัญหา NP-complete คือ พวกมันทั้งหมดยังอยู่ในสองทางเลือกคือเป็น intractable หรือมีอัลกอริธึมที่มี runtime แบบ nonexponential เป็นวิธีหนึ่งในการแสดงว่าปัญหาหนึ่งเป็น NP-complete คือแสดงว่าวิธีแก้ปัญหานั้นสามารถแปลง (ในเวลา nonexponential) เป็นวิธีแก้ของปัญหาอื่นที่รู้ว่าเป็น NP-complete อยู่แล้ว การแปลงดังกล่าวเรียกว่า reduction Reduction เป็นวิธีแก้ปัญหาแบบชาญฉลาดโดยแปลงคำตอบของปัญหาหนึ่งเป็นคำตอบของอีกปัญหาหนึ่ง การลดรูปดังกล่าวเกิดขึ้นบ่อยครั้ง และบางครั้งเกิดขึ้นโดยนัย เช่น Indiana Jones ที่ลดปัญหาการหากระเบื้องปลอดภัยให้เป็นการสะกดชื่อ Iehova หรือเมื่อ Sherlock Holmes ลดงานการเก็บข้อมูลผู้ต้องสงสัยเป็นการดำเนินการบนพจนานุกรม

Reductions เองก็เป็นการคำนวณ และเป็นเทคนิคที่มีประโยชน์ในการผสมผสานกับการคำนวณอื่น ๆ ตัวอย่างเช่น ปัญหาการหาค่าสมาชิกที่เล็กที่สุดในลิสต์สามารถลดรูปเป็นการ sort ลิสต์แล้วเอาสมาชิกตัวแรกของลิสต์ที่เรียงแล้ว โดยการแปลงอินพุต (เช่น ลิสต์ที่ไม่เรียง) เป็นรูปเฉพาะ (เช่น ลิสต์ที่เรียงแล้ว) เพื่อให้สามารถใช้ algorithm อื่น (เช่น การเอาสมาชิกตัวแรก) ได้ร่วมกัน การรวมทั้งสองการคำนวณ—การ sort ตามด้วยการเอาสมาชิกตัวแรก—จะได้การคำนวณที่เป็นวิธีแก้ปัญหาเดิมของการหาค่าน้อยสุดในลิสต์แบบสุ่ม อย่างไรก็ตาม ควรพิจารณาเวลาในการรันของการลดรูปด้วย ยกตัวอย่าง การ sort ต้องใช้เวลาแบบ linearithmic วิธีที่ได้จากการลดรูปจึงไม่ได้มีเวลาเท่ากับการสแกนหาค่าน้อยสุดแบบง่าย ๆ ซึ่งใช้เวลาแบบ linear ดังนั้นการลดรูปนี้จึงไม่ค่อยมีประโยชน์เพราะทำให้ประสิทธิภาพแย่ลง ดังนั้น การลดรูประหว่างปัญหา NP-complete ต้องทำได้ในเวลา nonexponential มิฉะนั้นวิธีแก้ที่เป็น nonexponential ของปัญหาหนึ่งจะกลายเป็น exponential เพราะเวลาในการลดรูปเป็น exponential

การลดรูปแบบ nonexponential ระหว่างปัญหา NP-complete ให้ leverage อย่างมาก เช่นเดียวกับที่สิ่งประดิษฐ์หนึ่งอย่าง เช่น ล้อ ถูกประดิษฐ์เพียงครั้งเดียวและถูกใช้โดยมนุษย์ทั้งมวล การแก้ปัญหา NP-complete หนึ่งปัญหาสามารถแก้ปัญหาอื่น ๆ ได้ทั้งหมด และข้อเท็จจริงนี้นำไปสู่คำถามที่สรุปโดยสมการที่โด่งดัง:

P = NP ?

สมการนี้ถูกยกขึ้นเป็นครั้งแรกโดยนักตรรกศาสตร์ชาวออสเตรีย-อเมริกัน Kurt Gödel และถูกทำให้ชัดเจนในปี 1971 โดยนักวิทยาการคอมพิวเตอร์ชาวแคนาดา-อเมริกัน Stephen Cook คำถามคือว่าชั้นปัญหา P ซึ่งสามารถ แก้ได้ ในเวลาแบบ nonexponential (หรือ polynomial) เท่ากับชั้น NP ซึ่งสามารถ ตรวจสอบได้ ในเวลา polynomial หรือไม่ การหาขอบเขตล่างแบบ exponential สำหรับปัญหา NP-complete จะให้คำตอบว่า "ไม่" แต่อีกด้านหนึ่งการค้นพบอัลกอริธึม nonexponential สำหรับปัญหาใดปัญหาหนึ่งจะทำให้คำตอบเป็น "ใช่" ความสามารถในการแก้ปัญหาจำนวนมากขึ้นอยู่กับคำตอบของปัญหา P = NP ซึ่งเน้นความสำคัญของมัน ปัญหานี้สับสนวิทยาการคอมพิวเตอร์มากว่าสี่ทศวรรษและน่าจะเป็นปัญหาเปิดที่สำคัญที่สุดในสาขานี้ นักวิทยาการคอมพิวเตอร์ส่วนใหญ่มักเชื่อว่าปัญหา NP-complete เป็นจริง ๆ แล้ว intractable และไม่มีอัลกอริธึม nonexponential สำหรับปัญหาเหล่านี้ แต่ก็ยังไม่มีผู้ออกมายืนยันอย่างแน่นอน

The Nirvana Fallacy (กับดักนิรวาณ)

การที่เวลาในการทำงานของอัลกอริธึมสูงเกินไปอาจสร้างความหงุดหงิดแน่นอน มีวิธีแก้ปัญหาหนึ่งแต่ก็มีค่าใช้จ่ายสูงเกินกว่าจะทำได้จริง—คล้ายผลไม้ที่อยู่ตรงหน้าต้นไม้ของ Tantalus แต่เข้าใกล้ไม่ได้ อย่างไรก็ตาม ข้อเท็จจริงที่น่าหดหู่เกี่ยวกับปัญหา NP-complete ไม่ใช่เหตุผลให้สิ้นหวัง นอกจากวิธีการรับมือกับความไม่มีประสิทธิภาพของอัลกอริธึม ยังมีข้อดีที่น่าประหลาดใจ

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

อัลกอริธึมแบบ exponential ที่คำนวณคำตอบที่แม่นยำจึงไม่ใช่ทางเลือกที่ใช้งานได้จริงสำหรับอินพุตขนาดใหญ่ เช่นเดียวกับแผนการถูกล็อตเตอรี่ที่ไม่ใช่วิธีการปฏิบัติ สำหรับทางเลือก เราสามารถมองหาอัลกอริธึม nonexponential ที่อาจไม่ให้คำตอบที่สมบูรณ์แต่ให้คำตอบแบบ approximation ที่เพียงพอสำหรับการใช้งานจริง—approximation algorithm การทำงานและการประเมินผลแบบ approximation สามารถเปรียบได้กับการทำงานและการเก็บออมเป็นแผนสำรองในการเกษียณ ซึ่งเป็น approximation ของการถูกล็อตเตอรี่ แม้จะไม่ดีเท่าการถูกล็อตเตอรี่ แต่มักเป็นทางเลือกที่ใช้ได้จริง

บาง approximation algorithms ให้คำตอบที่รับประกันว่าจะอยู่ในปัจจัยหนึ่งของคำตอบที่แม่นยำ เช่น Indiana Jones สามารถหาคำตอบประมาณสำหรับปัญหาการชั่งน้ำหนักได้ในเวลาแบบ linearithmic โดยการเพิ่มวัตถุตามลำดับจากน้ำหนักมากไปน้อย ด้วยวิธีนี้ ผลลัพธ์รับประกันว่าจะไม่แย่กว่าคำตอบที่ดีที่สุดไม่เกิน 50% แม้อาจไม่ดูดีนักเพราะความแม่นยำต่ำ แต่ในหลายกรณีผลลัพธ์ใกล้เคียงคำตอบที่ดีที่สุดจริง ๆ และมีต้นทุนถูก—คุณมักได้สิ่งที่จ่ายไป (ในแง่ runtime)

ในปัญหาการชั่งน้ำหนัก อัลกอริธึมที่ง่ายที่สุดต้องเริ่มด้วยการ sort วัตถุตามน้ำหนัก แล้วหาองค์ประกอบแรกที่น้ำหนักน้อยกว่าน้ำหนักเป้าหมายและค่อย ๆ เพิ่มวัตถุต่อไปจนถึงเป้าหมาย เริ่มด้วยการใส่ 15, 13, และ 11 รวมเป็น 39 การเพิ่มถัดไปคือ 9 จะทำให้น้ำหนักเกินเป้าหมาย จึงข้ามไปยังตัวถัดไป แต่ทั้ง 8 และ 5 ก็หนักเกินไปเช่นกัน ดังนั้นผลลัพธ์ประมาณคือ 15, 13, และ 11 ซึ่งห่างจากคำตอบที่ดีที่สุดเพียง 3 หน่วย หรือประมาณ 7% ของคำตอบที่ดีที่สุด

กลยุทธ์ที่เลือกค่าที่ใหญ่ที่สุดเป็นประจำนี้เรียกว่า greedy algorithm เพราะมันมักจะตัดสินใจฉับพลันตามโอกาสแรกที่พบ Greedy algorithms ง่ายและทำงานได้ดีสำหรับปัญหาหลายประเภท แต่มันอาจพลาดคำตอบที่แม่นยำในบางกรณี เช่น ในตัวอย่างนี้การเลือก 11 แทนที่จะรอ 9 ทำให้ไม่สามารถได้คำตอบที่ดีที่สุด Greedy algorithm นี้มีเวลาในการทำงานแบบ linearithmic (เกิดจากการ sort เบื้องต้น) จึงค่อนข้างมีประสิทธิภาพ

คำถามสำคัญสำหรับ approximation algorithm คือมันสามารถให้การประมาณที่แย่ที่สุด (worst-case) ได้ดีแค่ไหน สำหรับ greedy weighing algorithm สามารถพิสูจน์ได้ว่ามันอยู่ภายใต้ 50% ของคำตอบที่ดีที่สุดเสมอ.

การประมาณคือคำตอบที่เพียงพอ — อาจไม่ดีเท่าคำตอบที่ดีที่สุด แต่ดีกว่าไม่มีคำตอบเลย ใน Indiana Jones and the Temple of Doom Indiana Jones และเพื่อนสองคนต้องเผชิญกับสถานการณ์ที่เครื่องบินกำลังจะชนภูเขา ทั้งสองนักบินหนีออกจากเครื่องบิน เหลือเชื้อเพลิงน้อย และไม่มีร่มชูชีพ Indiana Jones แก้ปัญหานั้นด้วยการใช้เรือเป่าลมเพื่อพาผู้โดยสารลงสู่พื้น เปรียบได้กับการประมาณผลของร่มชูชีพ การมี approximation algorithm แม้จะหยาบก็ยังดีกว่าไม่มีอัลกอริธึมที่ใช้งานได้

Make Lemonade (พลิกวิกฤตให้เป็นโอกาส)

Approximation algorithms สามารถบรรเทาปัญหาความไม่มีประสิทธิภาพจากอัลกอริธึมแบบ exponential ได้ นั่นถือเป็นข่าวดี แต่ยังมีข้อดีอีกประการ หนึ่งคือความจริงที่ว่าเมื่อคำตอบของปัญหาหนึ่งไม่สามารถคำนวณได้อย่างมีประสิทธิภาพ อาจเป็นประโยชน์ในทางอื่น ๆ ตัวอย่างเช่น วิธี generate-and-test สำหรับปัญหาการชั่งน้ำหนักคล้ายกับสิ่งที่เราต้องทำเมื่อลืมรหัสล็อกของกล่องตัวเลข: เราต้องลองทุกการผสมของตัวเลข ซึ่งสำหรับสามแป้นตัวเลข (แต่ละแป้น 0–9) มี 10 × 10 × 10 = 1,000 วิธี การใช้เวลานานในการลองทุกชุดนี่เองที่ทำให้ล็อกตัวเลขมีประสิทธิภาพในการป้องกันการเข้าถึง

การตรวจชุด 1,000 วิธีด้วยคอมพิวเตอร์อิเล็กทรอนิกส์นั้น trivial แต่สำหรับมนุษย์ที่ช้าอาจใช้เวลานานพอสมควร ซึ่งแสดงให้เห็นว่าเรื่องประสิทธิภาพเป็นแนวคิดสัมพัทธ์และขึ้นกับความสามารถของเครื่องมือคำนวณ อย่างไรก็ตาม เวลาในการรันเกี่ยวกับอัตราการเติบโตของอัลกอริธึม ดังนั้นคอมพิวเตอร์ที่เร็วขึ้นไม่สามารถชดเชยการเพิ่มขึ้นอย่างมหาศาลของเวลาในการรันของอัลกอริธึมแบบ exponential ที่เกิดจากการเพิ่มขนาดอินพุตเล็กน้อย ข้อเท็จจริงนี้ถูกนำมาใช้ใน cryptography เพื่ออำนวยความสะดวกในการแลกเปลี่ยนข้อความอย่างปลอดภัย เมื่อใดก็ตามที่คุณเข้าเว็บไซต์ที่ขึ้นต้นด้วย https:// ไอคอนกุญแจในแถบที่อยู่จะล็อกเพื่อบอกว่าการสื่อสารที่ปลอดภัยกับเว็บไซต์นั้นถูกตั้งขึ้นแล้ว

หนึ่งในวิธีการส่งและรับข้อความแบบเข้ารหัสคือการเข้ารหัสและถอดรหัสข้อความด้วย คีย์ สองชนิดที่เกี่ยวข้องกัน หนึ่งคือ public key และอีกหนึ่งคือ private key ผู้เข้าร่วมการสื่อสารแต่ละคนมีคู่คีย์เช่นนี้ คีย์สาธารณะ (public key) เป็นที่รู้จักของทุกคน แต่ private key ของแต่ละคนจะรู้เฉพาะเจ้าของเท่านั้น ทั้งสองคีย์เชื่อมโยงกันในลักษณะที่ข้อความที่ถูกเข้ารหัสด้วย public key จะถอดรหัสได้เฉพาะโดยใช้ private key ที่สอดคล้องกัน จึงสามารถส่งข้อความแบบปลอดภัยถึงใครบางคนโดยเข้ารหัสด้วย public key ของคนนั้น ซึ่งเป็นที่เปิดเผย และเพราะมีเพียงผู้รับที่รู้ private key เท่านั้น ผู้รับจึงเป็นคนเดียวที่ถอดรหัสข้อความได้ ตัวอย่างเช่น หากคุณต้องการตรวจสอบยอดเงินในบัญชีธนาคารผ่านอินเทอร์เน็ต เบราว์เซอร์ของคุณจะส่ง public key ไปยังคอมพิวเตอร์ของธนาคาร ธนาคารจะใช้เพื่อเข้ารหัสยอดเงินแล้วส่งกลับมายังเบราว์เซอร์ของคุณ ข้อความนี้แม้ใครเห็นก็ไม่อาจถอดได้ เพราะมันถูกเข้ารหัส เท่านั้นคุณเท่านั้นที่สามารถถอดรหัสได้ในเบราว์เซอร์ของคุณโดยใช้ private key ของคุณ

ถ้าเราไม่มีอินเทอร์เน็ตและต้องทำผ่านไปรษณีย์ ก็เปรียบได้กับการส่งกล่องที่มีกุญแจ (กุญแจอยู่กับคุณคนเดียว) ไปให้ธนาคาร ธนาคารจะเขียนยอดเงินใส่กระดาษ ใส่ลงในกล่อง ล็อกกล่องด้วยกุญแจ แล้วส่งกล่องที่ล็อกกลับมาให้คุณ เมื่อคุณได้รับกล่อง คุณก็เปิดกล่องด้วยกุญแจของคุณและเห็นยอดเงินได้ เพราะไม่มีใครคนอื่นที่เปิดกล่องได้ ข้อมูลจึงปลอดภัยระหว่างการส่ง ในตัวอย่างนี้ กล่องที่มีกุญแจเปิดเปรียบได้กับ public key และการที่ธนาคารใส่กระดาษแล้วล็อกกล่องเปรียบเสมือนการเข้ารหัสข้อความ

ข้อความที่เข้ารหัสจะปลอดภัยจากการเข้าถึงโดยไม่ได้รับอนุญาต เนื่องจากการถอดรหัสโดยไม่รู้ private key ต้องคำนวณการหา prime factors ของจำนวนขนาดใหญ่ ขณะที่ยังไม่ทราบว่าการหารตัวประกอบเฉพาะทำให้เป็นปัญหา NP-complete หรือไม่ ปัจจุบันยังไม่มีอัลกอริธึม nonexponential ที่รู้จักสำหรับปัญหานี้ ดังนั้นการถอดรหัสโดยไม่ได้รับอนุญาตในทางปฏิบัติจะใช้เวลามากเกินไป ดังนั้นความยากของการแก้ปัญหาบางอย่างจึงถูกนำมาใช้เพื่อปกป้องการส่งข้อมูลให้ปลอดภัย

แนวคิดนี้ไม่ใช่เรื่องใหม่ ป้อมค่าย รั้ว กำแพง และกลไกป้องกันอื่น ๆ ทั้งหมดตั้งอยู่บนหลักการเดียวกัน แต่หลาย ๆ การป้องกันเหล่านี้ก็สามารถถูกทำลายได้ ในปัจจุบัน การส่งและรับข้อความแบบเข้ารหัสถือว่าปลอดภัยเนื่องจากยังไม่มีอัลกอริธึม nonexponential สำหรับการหา prime factors อย่างไรก็ตาม เมื่อใดก็ตามที่มีผู้ค้นพบอัลกอริธึม nonexponential ได้ ความปลอดภัยนี้จะหายไปทันที ในทางกลับกัน หากมีการพิสูจน์ขอบเขตล่างแบบ exponential สำหรับปัญหานี้ เราจะมั่นใจได้ว่าข้อความที่เข้ารหัสปลอดภัย ในระหว่างนี้ ความไม่รู้ของเราต่อคำถามนี้ทำให้วิธีการนี้ยังใช้งานได้