โครงการแก้ไขข้อผิดพลาด 'Magical' ได้รับการพิสูจน์แล้วว่าไม่มีประสิทธิภาพโดยธรรมชาติ นิตยสารควอนต้า

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

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

“มันเป็นปรากฏการณ์ที่มหัศจรรย์ทีเดียว” กล่าว ทอม กูร์นักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัยเคมบริดจ์ “โดยพื้นฐานแล้ว มันไม่ชัดเจนว่าวัตถุทางคณิตศาสตร์ดังกล่าวอาจมีอยู่จริงเลย”

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

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

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

“ผลลัพธ์นี้น่าทึ่งมาก” กล่าว ชูบังกี ซาราฟนักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยโตรอนโต “มันเป็นความก้าวหน้าครั้งใหญ่”

ความแข็งแกร่งของตัวเลข

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

สมมติว่าคุณต้องการส่งข้อความถึงเพื่อน แต่คุณกังวลว่าข้อผิดพลาดอาจเปลี่ยนความหมาย กลยุทธ์ง่ายๆ อย่างหนึ่งคือการแทนที่ 0 แต่ละตัวในข้อความของคุณด้วย 000 และแทนที่ 1 แต่ละตัวด้วย 111 หากเพื่อนของคุณเห็นส่วนหนึ่งของข้อความที่ไม่มีบิตที่เหมือนกันสามบิตติดกัน พวกเขาจะรู้ว่ามีข้อผิดพลาดเกิดขึ้น และหากข้อผิดพลาดเกิดขึ้นแบบสุ่มและค่อนข้างหายาก ดังนั้นสตริงใดๆ ของ 110 ก็มีแนวโน้มที่จะเป็น 111 ที่เสียหายมากกว่า 000 ที่เสียหาย การลงคะแนนเสียงข้างมากอย่างง่ายภายในแฝดแต่ละตัวก็เพียงพอที่จะแก้ไขข้อผิดพลาดส่วนใหญ่ได้

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

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

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

คิดว่าทั่วโลก, พระราชบัญญัติเฉพาะ

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

พิจารณาบริษัทที่เก็บอีเมลของผู้ใช้ไว้ในระบบคลาวด์ ซึ่งก็คือบนเซิร์ฟเวอร์ที่หลากหลาย คุณสามารถมองอีเมลทั้งคอลเลกชั่นเป็นข้อความยาวๆ เดียวได้ ตอนนี้สมมติว่าเซิร์ฟเวอร์ตัวหนึ่งล่ม ด้วยรหัส Reed-Solomon คุณจะต้องดำเนินการคำนวณจำนวนมากที่เกี่ยวข้องกับข้อมูลที่เข้ารหัสทั้งหมดเพื่อกู้คืนอีเมลของคุณจากเซิร์ฟเวอร์ที่สูญหายไป “คุณจะต้องดูทุกอย่าง” กล่าว ซีฟ ดวีร์นักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยพรินซ์ตัน “นั่นอาจเป็นอีเมลหลายพันล้านฉบับ – อาจใช้เวลานานมาก”

นักวิจัยใช้คำว่า "ท้องถิ่น" เพื่ออธิบายรหัสที่ใช้เพียงเศษเสี้ยวของข้อความที่เข้ารหัส จุดผิดพลาด หรือแก้ไขให้ถูกต้อง รหัสการทำซ้ำอย่างง่ายมีลักษณะเฉพาะในท้องถิ่นนี้ แต่นั่นคือสิ่งที่ทำให้เสี่ยงต่อการถูกแก้ไข ในทางตรงกันข้าม โค้ดที่แก้ไขได้เฉพาะที่นั้นจะได้รับสิ่งที่ดีที่สุดจากทั้งสองกรณี โดยสามารถแก้ไขข้อผิดพลาดได้ทุกบิตด้วยการสืบค้นเพียงไม่กี่ครั้ง โดยไม่สูญเสียการเชื่อมโยงกันซึ่งทำให้โค้ด Reed-Solomon มีความยืดหยุ่นมาก

“นี่เป็นแนวคิดที่เข้มงวดจริงๆ” โคธารีกล่าว

ตัวอย่างที่มีชื่อเสียงที่สุดของรหัสที่แก้ไขได้เฉพาะที่คือเวอร์ชันของรหัสแก้ไขข้อผิดพลาดที่น่านับถือซึ่งคิดค้นขึ้นในปี 1954 โดยนักคณิตศาสตร์ เดวิด มุลเลอร์ และ เออร์วิง รีด (ซึ่งช่วยพัฒนารหัสรีด-โซโลมอนด้วย) เช่นเดียวกับรหัส Reed-Solomon รหัส Reed-Muller ใช้พหุนามที่มีคำศัพท์หลายคำรวมกันเพื่อเข้ารหัสข้อความขนาดยาว

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

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

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

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

“การเอ็กซ์โพเนนเชียลในกรณีนี้แย่มาก” Dvir กล่าว แต่มันหลีกเลี่ยงไม่ได้เหรอ?

แก้ไขหรือถอดรหัสได้?

ขณะที่นักวิทยาศาสตร์คอมพิวเตอร์พยายามและล้มเหลวในการค้นหารหัสที่มีประสิทธิภาพมากขึ้นในท้องถิ่น พวกเขาเริ่มสงสัยว่ารหัสดังกล่าวไม่สามารถทำได้เลย ในปี พ.ศ. 2003 นักวิจัยสองคน พิสูจน์แล้วว่า ว่าไม่มีทางเอาชนะโค้ด Reed-Muller ได้โดยใช้เพียงสองคำสั่งเท่านั้น แต่นั่นก็เท่าที่ใครๆ ก็ทำได้

“เมื่อคุณไปถึงสาม ความรู้ของเราจะไม่สมบูรณ์มาก” Kothari กล่าว

ความก้าวหน้าครั้งต่อไปเป็นเรื่องที่ซับซ้อนยิ่งขึ้น ในเอกสารสองฉบับที่ตีพิมพ์ใน 2008 และ 2009นักวิทยาศาสตร์คอมพิวเตอร์ Sergey Yekhanin และ Klim Efremenko สาธิตวิธีสร้างโค้ดการสืบค้นสามโค้ดที่มีประสิทธิภาพมากกว่าโค้ด Reed-Muller แต่โค้ดเหล่านี้ไม่ค่อยสามารถแก้ไขได้ในเครื่อง แต่กลับมีคุณสมบัติที่แตกต่างออกไปเล็กน้อยที่เรียกว่าความสามารถในการถอดรหัสเฉพาะที่

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

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

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

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

ตรรกะการยืม

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

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

ในปี 2021 Kothari และ Manohar ร่วมกับ Venkatesan Guruswami จาก University of California, Berkeley ได้สร้าง การพัฒนาที่สำคัญ ในการศึกษาปัญหาความพึงพอใจที่มีข้อจำกัดโดยใช้เทคนิคทางทฤษฎีใหม่ในการระบุกรณีที่ไม่น่าพึงพอใจที่ยุ่งยากเหล่านั้น พวกเขาสงสัยว่าวิธีการใหม่นี้จะเป็นเครื่องมือที่มีประสิทธิภาพในการแก้ปัญหาอื่นๆ ด้วยเช่นกัน และ Omar Alrabiah นักศึกษาระดับบัณฑิตศึกษาของ Guruswami แนะนำให้พวกเขาดูโค้ดที่สามารถถอดรหัสได้ในเครื่อง 3 คิวรี

“พูดได้เลยว่านี่คือตะปูที่มีค้อนอยู่ในมือ” Kothari กล่าว

ผลลัพธ์ที่น่าประหลาดใจของ Yekhanin และ Efremenko แสดงให้เห็นว่ารหัสที่สามารถถอดรหัสได้ภายในเครื่องแบบสามแบบสอบถามอาจมีประสิทธิภาพมากกว่ารหัส Reed-Muller แต่รหัสของพวกเขาเป็นรหัสที่ดีที่สุดเท่าที่จะเป็นไปได้หรือรหัสที่ถอดรหัสได้ภายในเครื่องสามแบบสอบถามจะมีประสิทธิภาพมากกว่าเดิมหรือไม่? Kothari, Manohar, Guruswami และ Alrabiah คิดว่าเทคนิคใหม่ของพวกเขาอาจพิสูจน์ขีดจำกัดว่าโค้ดดังกล่าวจะมีประสิทธิภาพเพียงใด แผนของพวกเขาคือการสร้างสูตรเชิงตรรกะที่ครอบคลุมโครงสร้างของโค้ดที่สามารถถอดรหัสได้ภายในเครื่อง 3 คิวรีที่เป็นไปได้ทั้งหมดในขนาดที่กำหนด และพิสูจน์ว่ามันไม่เป็นที่พอใจ ดังนั้นจึงแสดงให้เห็นว่าไม่มีโค้ดดังกล่าวมีอยู่จริง

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

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

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

ขณะนี้ Kothari และ Manohar หวังที่จะขยายเทคนิคของตนเพื่อศึกษาโค้ดที่ได้รับอนุญาตให้ทำการสืบค้นมากกว่า 3 ข้อ เนื่องจากขณะนี้ยังไม่มีใครทราบข้อมูลเหล่านี้มากนัก และความก้าวหน้าในทฤษฎีการแก้ไขข้อผิดพลาดมักมีผลกระทบในสาขาอื่นๆ ที่ดูเหมือนจะไม่เกี่ยวข้องกัน โดยเฉพาะอย่างยิ่งรหัสที่แก้ไขได้ในท้องถิ่นทำให้เกิดความประหลาดใจในทุกที่จากปัญหา ค้นหาฐานข้อมูลส่วนตัว ในการเข้ารหัสเพื่อพิสูจน์ ทฤษฎีบทในเชิงผสม. ยังเร็วเกินไปที่จะบอกว่าเทคนิคของ Kothari และ Manohar จะส่งผลต่อสาขาต่างๆ เหล่านี้อย่างไร แต่นักวิจัยยังมีความรู้สึกในแง่ดี

“มีแนวคิดใหม่ที่สวยงามจริงๆ ที่นี่” Dvir กล่าว “ผมคิดว่ามีศักยภาพมาก”