นักวิจัยผู้สำรวจการคำนวณด้วยการเสกสรรโลกใหม่ | นิตยสารควอนต้า

ลองจินตนาการว่าคุณกำลังแสวงหาความเข้าใจธรรมชาติของการคำนวณ คุณอยู่ลึกเข้าไปในถิ่นทุรกันดาร ห่างไกลจากเส้นทางใดๆ และ ไม่แน่ใจ ข้อความ ถูกแกะสลักไว้บนลำต้นของต้นไม้รอบตัวคุณ – BPP, AC⁰[ม.], Σ₂P, YACC และอื่นๆ อีกหลายร้อยรายการ ร่ายมนตร์กำลังพยายามบอกคุณบางอย่าง แต่จะเริ่มต้นจากตรงไหนดี? คุณไม่สามารถรักษามันให้ตรงทั้งหมดได้

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

ในช่วงทศวรรษปี 1980 และ 1990 Impagliazzo มีบทบาทสำคัญในการรวมกลุ่มของ รากฐานทางทฤษฎีของการเข้ารหัส- ในปีพ.ศ. 1995 เขาได้กล่าวถึงความสำคัญของการพัฒนาใหม่ ๆ เหล่านี้ในเอกสารที่เป็นสัญลักษณ์ซึ่งมีการกำหนดแนวทางแก้ไขที่เป็นไปได้สำหรับ P และ NP และปัญหาที่เกี่ยวข้องจำนวนหนึ่งในภาษาของ โลกสมมุติทั้งห้า เราอาจอาศัยอยู่ซึ่งมีชื่อเรียกอย่างแปลกๆ ว่า Algorithmica, Heuristica, Pessiland, Minicrypt และ Cryptomania โลกทั้งห้าของ Impagliazzo เป็นแรงบันดาลใจให้กับนักวิจัยรุ่นหนึ่ง และพวกเขายังคงชี้แนะการวิจัยในสาขาย่อยที่เจริญรุ่งเรืองของ ความซับซ้อนของเมตาดาต้า.

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

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

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

คุณเริ่มสนใจคณิตศาสตร์ครั้งแรกเมื่อไหร่?

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

แล้ววิทยาการคอมพิวเตอร์ล่ะ? บางส่วนของสาขานี้เป็นนามธรรมมาก แต่ก็ไม่ใช่สิ่งที่คนส่วนใหญ่พบเห็นเป็นครั้งแรก

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

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

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

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

ปัญหากับปริศนาต่างกันอย่างไร?

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

ความแตกต่างระหว่างโลกทั้งห้าคือการตอบคำถามที่ว่า “มีปัญหายากๆ ไหม?” และ “มีปริศนาที่ยากไหม?”

คำตอบที่แตกต่างกันเหล่านั้นมีผลอย่างไร?

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

ใน Minicrypt ฉันสามารถสร้างปริศนาที่ฉันรู้วิธีแก้ซึ่งยังคงท้าทายสำหรับคุณอยู่ และท้ายที่สุดแล้ว Cryptomania คือโลกที่คนสองคนสามารถยืนอยู่ในที่สาธารณะซึ่งผู้ดักฟังสามารถได้ยิน และร่วมกันสร้างปริศนาที่ยังคงยากสำหรับผู้ดักฟัง

อะไรเป็นแรงบันดาลใจให้คุณเขียนรายงานเรื่องห้าโลก

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

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

เหตุใดจึงต้องวางกรอบเป็นโลกที่แตกต่างด้วยชื่อแปลกๆ

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

นักวิจัยได้ตัดโลกที่เป็นไปได้ทั้งห้าออกไปหรือไม่?

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

โลกสมมุติยังมีบทบาทอีกประการหนึ่งในทฤษฎีความซับซ้อน ในการพิสูจน์ที่สันนิษฐานว่ามี "พยากรณ์" อยู่จริง ก่อนอื่นเลย ออราเคิลคืออะไรกันแน่?

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

นักวิจัยคิดว่ากล่องวิเศษเหล่านี้มีอยู่จริงหรือไม่?

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

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

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

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

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

เมื่อพูดถึง Monty Python ฉันรู้ว่าคุณแสดงตลกด้นสดมาเป็นเวลานานแล้ว คุณเริ่มต้นได้อย่างไร

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

เธอคิดอะไรอยู่?

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

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

การทำอิมโพรฟได้เปลี่ยนวิธีการวิจัยของคุณหรือไม่?

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

เช่นอะไร?

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

แล้วความรักในเกมเล่นตามบทบาทของคุณล่ะ นั่นมีอิทธิพลต่องานของคุณหรือไม่?

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

เหตุใดเกมเล่นตามบทบาทจึงเป็นวิธีที่น่าสนใจในการสำรวจโลกสมมุติ?

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