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

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

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

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

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

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

Tipping the Scale (การถ่วงดุล)

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

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

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

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

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

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

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

When Runtime Explodes (เมื่อระยะเวลาทำงานระเบิด)

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

ประเด็นหลังนี้บางครั้งถูกใช้เป็นข้ออ้างในการใช้อัลกอริทึมที่มีระยะเวลาทำงานไม่ดี ข้อโต้แย้งเป็นดังนี้ "ใช่ ผมรู้ว่าอัลกอริทึมใช้เวลาหลายนาทีกว่าจะเสร็จ แต่รอให้เราได้คอมพิวเตอร์ที่เร็วกว่านี้ก่อนสิ มันจะแก้ปัญหานี้เอง" ข้อโต้แย้งนี้มีความถูกต้องอยู่บ้าง กฎของมัวร์ (Moore's law) กล่าวว่าความเร็วของคอมพิวเตอร์เพิ่มขึ้นเป็นสองเท่าทุกๆ ประมาณ 18 เดือน 2

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

ตาราง 7.1 ระยะเวลาทำงานโดยประมาณสำหรับ input ขนาดต่างๆ บนคอมพิวเตอร์ที่ประมวลผลได้หนึ่งพันล้านขั้นตอนต่อวินาที

ขนาด Input	ระยะเวลาทำงาน
	Linear	Linearithmic	Quadratic	Exponential
20				0.001 วินาที
50				13 วัน
100
1,000
10,000			0.1 วินาที
1 ล้าน	0.001 วินาที	0.002 วินาที	16 นาที
1 พันล้าน	1 วินาที	30 วินาที	32 ปี

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

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

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

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

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

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

Shared Destiny (ชะตากรรมร่วม)

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

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

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

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

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

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

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

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

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

P = NP ?

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

The Nirvana Fallacy (ความเข้าใจผิดแบบนิพพาน)

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

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

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

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

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

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

คำถามสำคัญสำหรับ approximation algorithm คือ มันสามารถให้ค่าประมาณที่ดีเพียงใดในกรณีที่แย่ที่สุด สำหรับ greedy algorithm การชั่งน้ำหนัก สามารถแสดงให้เห็นว่ามันอยู่ภายใน 50% ของคำตอบที่ดีที่สุดเสมอ 7

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

Make Lemonade (เปลี่ยนวิกฤตเป็นโอกาส)

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

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

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

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

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

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