บทนำสู่ทฤษฎีการคำนวณและความซับซ้อน

คุณเคยสงสัยหรือไม่ว่าอุปกรณ์ที่คุณกำลังอ่านบทความนี้คืออะไร? คอมพิวเตอร์คืออะไร?

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

แต่คอมพิวเตอร์เหล่านี้ ซึ่งดูเหมือนจะมีศักยภาพไม่รู้จบ—พวกเขามีข้อจำกัดหรือไม่? มีปัญหาที่คอมพิวเตอร์ใช้แก้ไม่ได้หรือไม่?

ในบทความนี้ เราจะตอบคำถามเหล่านี้โดยหลีกเลี่ยงเฉพาะภาษาโปรแกรมและสถาปัตยกรรมคอมพิวเตอร์ เมื่อเข้าใจถึงพลังและข้อจำกัดของคอมพิวเตอร์และอัลกอริธึม เราสามารถปรับปรุงวิธีที่เราคิดและให้เหตุผลที่ดีขึ้นเกี่ยวกับกลยุทธ์ต่างๆ

มุมมองนามธรรมของการคำนวณสร้างผลลัพธ์ที่ยืนหยัดเหนือกาลเวลา และมีค่าสำหรับเราในทุกวันนี้เหมือนกับที่เกิดขึ้นเมื่อเริ่มพัฒนาในปี 1970

ความสามารถในการคำนวณ

คอมพิวเตอร์คืออะไร? ปัญหาคืออะไร?

ในโรงเรียน เรามักจะได้รับการสอนเกี่ยวกับแบบจำลองทางจิตของปัญหาและการทำงานในลักษณะนี้:

ฟังก์ชันคือขั้นตอนที่คุณใช้กับอินพุต x เพื่อค้นหาเอาต์พุต f(x)

ปรากฎว่าคำจำกัดความทางคณิตศาสตร์แตกต่างกัน:

ฟังก์ชันคือชุดของคู่ที่มีคำสั่ง โดยที่องค์ประกอบแรกของแต่ละคู่มาจากชุด X (เรียกว่าโดเมน) องค์ประกอบที่สองของแต่ละคู่มาจากชุด Y (เรียกว่าโคโดเมนหรือช่วง) และแต่ละองค์ประกอบของ โดเมนจับคู่กับองค์ประกอบเดียวของช่วง

นั่นเป็นคำที่ค่อนข้างถูก แต่นั่นหมายความว่าอย่างไร?

คำจำกัดความนี้บอกเราว่าคอมพิวเตอร์เป็นเครื่องจักรสำหรับฟังก์ชันการคำนวณ

ทำไม?

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

อย่างไรก็ตาม คำจำกัดความทางคณิตศาสตร์ทำให้เราได้ข้อสรุปที่น่าสนใจ เช่น การมีอยู่ของฟังก์ชันที่คำนวณไม่ได้ (เช่น ปัญหาที่แก้ไม่ได้):

เพราะไม่ใช่ทุกฟังก์ชันที่สามารถอธิบายเป็นอัลกอริธึมได้

กฎของเกม

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

เราจะเรียกอินพุตตัวอักษรของเครื่อง นั่นคือชุดของสตริงอักขระจากชุดจำกัดบางชุด ตัวอย่างเช่น ตัวอักษรของเครื่องอาจเป็นเลขฐานสอง (0 และ 1s) หรืออาจเป็นชุดอักขระ ASCII ลำดับอักขระใดๆ ที่จำกัดเป็นสตริง ตัวอย่างเช่น “0110”

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

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

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

ตัวดำเนินการที่สำคัญอย่างหนึ่งคือตัวดำเนินการ Kleene star ที่ใช้กับนิพจน์ทั่วไปด้วย นี่ถือได้ว่าเป็นการรวมพลังที่เป็นไปได้ทั้งหมดของภาษา ตัวอย่างเช่น หากภาษา A ของเราคือชุดของสตริง { '01', '1' } ดังนั้นสมาชิกหนึ่งตัวของ A* ก็คือสตริง '0101111'

นับได้

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

แม่นยำยิ่งขึ้น หลักฐานของเราอ้างว่าชุดของโปรแกรมที่เป็นไปได้นั้นนับไม่ถ้วนในขณะที่ชุดของภาษาบนตัวอักษรนั้นไม่มีที่สิ้นสุด

ณ จุดนี้ คุณอาจจะคิดว่า “อินฟินิตี้เป็นความคิดที่แปลกพอสำหรับตัวมันเอง ตอนนี้ฉันต้องจัดการกับพวกเขาสองคน!”

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

สำหรับบางเซต เช่น ตัวเลขจริง ไม่สำคัญว่าคุณฉลาดแค่ไหน ไม่มีการแจงนับ เซตเหล่านี้นับไม่ถ้วนหรือนับไม่ได้

นับได้หลายโปรแกรม

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

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

ย้ำ:

ชุดของสตริงทั้งหมดบนตัวอักษรใดๆ (เช่น ชุดของโปรแกรมคอมพิวเตอร์ทั้งหมด) สามารถนับได้

หลายภาษานับไม่ถ้วน

จากข้อสรุปนี้ แล้วชุดย่อยของสตริงเหล่านี้ล่ะ ถามอีกทางหนึ่ง แล้วชุดของภาษาทั้งหมดล่ะ? ปรากฎว่าชุดนี้นับไม่ได้

ชุดของภาษาทั้งหมดบนตัวอักษรใด ๆ นั้นนับไม่ได้

เป็นอีกครั้งที่เราไม่ปิดบังหลักฐานที่นี่

ผลที่ตามมา

แม้ว่าอาจไม่ปรากฏชัดในทันที แต่ผลที่ตามมาของการนับไม่ได้ของภาษาและการนับได้ของชุดโปรแกรมคอมพิวเตอร์ทั้งหมดนั้นลึกซึ้ง

ทำไม?

สมมติว่า A คือชุดของอักขระ ASCII อักขระ ASCII เป็นเพียงอักขระที่จำเป็นในการเขียนโปรแกรมคอมพิวเตอร์ เราจะเห็นได้ว่าชุดของสตริงที่เป็นตัวแทนของโปรแกรม JavaScript เป็นสับเซตของ A* (ในที่นี้ * คือตัวดำเนินการ Kleene star) การเลือก JavaScript เป็นไปตามอำเภอใจ เนื่องจากชุดโปรแกรมนี้เป็นชุดย่อยของชุดที่นับได้ เราจึงมีชุดโปรแกรม JavaScript ที่สามารถนับได้

นอกจากนี้ ให้เราพิจารณาว่าสำหรับภาษาใดๆ L เราสามารถกำหนดบางฟังก์ชัน f ที่ประเมินเป็น 1 ถ้าบางสตริง x อยู่ใน L และ 0 มิฉะนั้น หน้าที่ดังกล่าวทั้งหมดมีความแตกต่างกัน เนื่องจากมีการโต้ตอบแบบ 1:1 กับชุดของทุกภาษา และเนื่องจากชุดของทุกภาษานั้นนับไม่ได้ เราจึงมีชุดของฟังก์ชันดังกล่าวทั้งหมดนับไม่ได้

นี่คือจุดที่ลึกซึ้ง:

เนื่องจากชุดของโปรแกรมที่ใช้ได้ทั้งหมดสามารถนับได้ แต่ชุดของฟังก์ชันไม่สามารถนับได้ ดังนั้นต้องมีฟังก์ชันบางอย่างที่เราไม่สามารถเขียนโปรแกรมได้

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

ตอนนี้คำถามกลายเป็นว่า "ปัญหาเหล่านี้มีลักษณะอย่างไร" ก่อนที่เราจะอธิบายปัญหาดังกล่าวต่อไป เราต้องสร้างแบบจำลองการคำนวณในลักษณะทั่วไปก่อน

เครื่องจักรทัวริง

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

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

• สัญลักษณ์ปัจจุบันใต้หัวและ

• สถานะภายในของเครื่องซึ่งได้รับการอัปเดตตามสัญลักษณ์ที่เขียนด้วย

แค่นั้นแหละ.

ความเป็นสากล

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

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

วิทยานิพนธ์คริสตจักรทัวริง

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

ทุกสิ่งที่คำนวณได้นั้นสามารถคำนวณได้ด้วยเครื่องทัวริง

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

การรับรู้และการตัดสินใจ

เราต้องครอบคลุมพื้นหลังอีกเล็กน้อยก่อนที่เราจะอธิบายปัญหาที่แก้ไม่ได้อย่างเป็นรูปธรรม นั่นคือ แนวคิดของตัวจำแนกภาษาและตัวกำหนดภาษา

ภาษาเป็นที่รู้จักหากมีเครื่องทัวริงที่รู้จัก

และ

ภาษาตัดสินได้หากมีเครื่องทัวริงที่ตัดสิน

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

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

ตัดสินใจไม่ถูก

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

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

เราสามารถพิสูจน์ได้โดยใช้เครื่องทัวริง เครื่องทัวริงสามารถอธิบายได้ว่าเป็นสตริง ดังนั้นจึงมีจำนวนนับได้ สมมติว่า M ₁ , M ₂ เป็นต้น ประกอบเป็นชุดของเครื่องจักรทัวริงทั้งหมด ให้เรากำหนดฟังก์ชันต่อไปนี้:

ที่นี่ <M> คือไวยากรณ์สำหรับ "การเข้ารหัสสตริงของ M" และฟังก์ชันนี้แสดงถึงปัญหาของการส่งออก 1 หาก M _i หยุดโดยการยอมรับ M _j เป็นอินพุตและเอาต์พุตเป็น 0 มิฉะนั้น โปรดทราบว่า _ฉัน จะต้องหยุด (เช่น เป็นผู้ตัดสินใจ) สิ่งนี้จำเป็นเนื่องจากเราต้องการอธิบายฟังก์ชันที่ตัดสินใจไม่ได้ (เช่น ปัญหาที่แก้ไม่ได้)

ตอนนี้ ให้เรากำหนดภาษา L ที่ประกอบด้วยการเข้ารหัสสตริงของเครื่องทัวริงที่ไม่ยอมรับคำอธิบายของตนเอง:

ตัวอย่างเช่น เครื่อง M ₁ บางเครื่องอาจส่งออก 0 บนอินพุต <M ₁ > ในขณะที่เครื่องอื่น M ₂ อาจส่งออก 1 บนอินพุต <M ₂ > เพื่อพิสูจน์ว่าภาษานี้ไม่สามารถตัดสินใจได้ เราถามว่า ML ซึ่งเป็นเครื่องที่ตัดสินภาษา _L ทำอะไรเมื่อได้รับคำอธิบายของตัวเอง < _ML > เป็นอินพุต มีความเป็นไปได้สองอย่าง:

_ML ยอมรับ < _ML >

หรือ

_ML ปฏิเสธ < _ML >

หาก ML ยอมรับการเข้ารหัสของตัวเอง แสดงว่า < _ML > ไม่ได้อยู่ในภาษา _L อย่างไรก็ตาม หากเป็นกรณีนี้ _ML ไม่ควรยอมรับการเข้ารหัสตั้งแต่แรก ในทางกลับกัน หาก ML ไม่ยอมรับการเข้ารหัสของตัวเอง < _ML > จะอยู่ในภาษา _L ดังนั้น _ML ควรยอมรับการเข้ารหัสสตริง

ในทั้งสองกรณี เรามีความขัดแย้ง หรือในทางคณิตศาสตร์ ความขัดแย้ง พิสูจน์ให้เห็นว่าภาษา L ไม่สามารถตัดสินใจได้ ดังนั้นเราจึงได้อธิบายปัญหาแรกที่แก้ไม่ได้ของเรา

ปัญหาการหยุดชะงัก

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

ภาษาของการเข้ารหัสของเครื่องทัวริงที่หยุดบนสตริงว่าง

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

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

สรุป

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

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

ทิ้งฟังก์ชันที่คำนวณได้และภาษาไว้เบื้องหลัง ตอนนี้เราพูดถึงความซับซ้อนในการคำนวณ สำรวจการคำนวณที่มีประสิทธิภาพ และปัญหา P vs. NP ที่มีชื่อเสียง

ความซับซ้อน

ช้ากับเร็ว

นักวิทยาศาสตร์คอมพิวเตอร์รู้จักปัญหาประเภทต่างๆ มากมาย และสองชั้นเรียนที่เราสนใจ ได้แก่ ปัญหาที่คอมพิวเตอร์สามารถแก้ไขได้อย่างรวดเร็วหรือมีประสิทธิภาพที่เรียกว่า P และปัญหาที่วิธีแก้ปัญหาสามารถตรวจสอบได้อย่างรวดเร็ว แต่ไม่สามารถรับได้อย่างรวดเร็วที่เรียกว่า NP

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

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

คำนิยามที่เป็นทางการ

P คือเซตของปัญหาที่แก้ได้ในเวลาพหุนาม นั่นคือจำนวนขั้นตอนการคำนวณถูกล้อมรอบด้วยฟังก์ชันพหุนามเทียบกับขนาดของปัญหา เรารู้ว่า "ทุกคนสามารถหาคู่ได้หรือไม่" คำถามหรือที่เรียกว่าปัญหาการจับคู่แบบสองฝ่ายอยู่ใน P

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

สุดท้าย NP-complete คือชุดของปัญหาที่เป็นปัญหาที่ยากที่สุดใน NP พวกเขาถูกเรียกว่ายากที่สุดเพราะปัญหาใด ๆ ใน NP สามารถเปลี่ยนเป็น NPC ได้อย่างมีประสิทธิภาพ ผลที่ได้คือ หากมีคนระบุวิธีแก้ปัญหาที่มีประสิทธิภาพใน NPC แล้ว NP ทั้งหมดจะถูกดูดซับโดย P ปัญหากลุ่มก็อยู่ใน NPC ด้วย

ดังนั้นเราจึงมาถึงปัญหาของ P vs. NP . นักวิทยาศาสตร์คอมพิวเตอร์และนักคณิตศาสตร์หลายคนเชื่อมั่นว่า P และ NP ไม่เท่ากัน หากเป็นเช่นนั้น ความหมายก็จะยิ่งลึกซึ้ง โครงสร้างพื้นฐานดิจิทัลในปัจจุบันส่วนใหญ่อาศัยความจริงที่ว่ามีปัญหาใน NP ที่ไม่ได้อยู่ใน P หากไม่เป็นเช่นนั้น วิธีเข้ารหัส เช่น จะล่มในชั่วข้ามคืน ทำให้บุคคลที่มีวิธีแก้ไขปัญหา NPC มีประสิทธิภาพสามารถล้มล้างโปรโตคอลความปลอดภัยที่เข้มงวดที่สุดได้

รายละเอียดปลีกย่อย

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

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

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

ที่จริงแล้วเราสามารถมีความละเอียดอ่อนยิ่งขึ้นได้ แทนที่จะขอเส้นทางที่สั้นที่สุด (P) เราสามารถขอเส้นทางที่ยาวที่สุดโดยไม่มีวงรอบได้ ปรากฎว่าปัญหาเส้นทางที่ยาวที่สุดนั้นสมบูรณ์ด้วย NP

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

สรุป

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

ไม่มีใครสามารถพิสูจน์ได้ว่า P ไม่เท่ากับ NP ไม่ว่าปัญหาสองประเภทนี้จะเท่ากันหรือไม่นั้นเรียกว่าปัญหา P กับ NP และเป็นปัญหาเปิดที่สำคัญที่สุดในวิทยาการคอมพิวเตอร์เชิงทฤษฎีในปัจจุบันหากไม่ใช่ในวิชาคณิตศาสตร์ทั้งหมด ในความเป็นจริง ในปี 2000 สถาบัน Clay Math ได้ตั้งชื่อปัญหา P vs. NP ให้เป็นหนึ่งในเจ็ดคำถามที่สำคัญที่สุดในวิชาคณิตศาสตร์ และได้เสนอเงินรางวัลล้านเหรียญเพื่อเป็นข้อพิสูจน์ที่กำหนดวิธีแก้ปัญหานี้

บทสรุป

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

• มีบางสิ่งที่ไม่สามารถคำนวณได้ เช่น ปัญหาการหยุดชะงัก

• มีบางอย่างที่ไม่สามารถคำนวณได้อย่างมีประสิทธิภาพ เช่น ปัญหาใน NPC

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

อ่านเพิ่มเติมในบล็อก Toptal Engineering:

• วิธีการเขียนล่ามตั้งแต่เริ่มต้น