นักคณิตศาสตร์แก้ปัญหาอายุ 30 ปีที่ขอบเขตระหว่างคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ เขาใช้นวัตกรรมล้ำสมัยที่พิสูจน์ได้ว่าเพื่อนร่วมงานของเขาประหลาดใจกับความเรียบง่าย
Hao Huang ผู้ช่วยศาสตราจารย์คณิตศาสตร์ที่มหาวิทยาลัย Emory ในแอตแลนตาพิสูจน์ความคิดทางคณิตศาสตร์ที่เรียกว่าการคาดการณ์ความอ่อนไหว (Sensitivity conjecture) ซึ่งในแง่หยาบอย่างไม่น่าเชื่อทำให้คุณสามารถเปลี่ยนอินพุตเป็นฟังก์ชันได้โดยไม่ต้องเปลี่ยนผลลัพธ์ คือความไวของมัน)
ในทศวรรษที่ผ่านมาตั้งแต่นักคณิตศาสตร์เสนอการคาดเดาความอ่อนไหวเป็นครั้งแรก (โดยไม่ต้องพิสูจน์) นักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีได้ตระหนักว่ามันมีผลกระทบอย่างมากสำหรับการพิจารณาวิธีที่มีประสิทธิภาพที่สุดในการประมวลผลข้อมูล
สิ่งที่น่าทึ่งเกี่ยวกับข้อพิสูจน์ของหวางตามผู้เชี่ยวชาญคนอื่น ๆ ในสนามไม่ใช่แค่ว่าหวางดึงออก แต่ยังเป็นวิธีที่สง่างามและตรงไปตรงมาที่เขาทำ หลักฐานของเขายังไม่ได้รับการตรวจสอบอย่างเป็นทางการหรือเผยแพร่ในวารสารคณิตศาสตร์ใด ๆ แต่ไม่นานหลังจาก Huang วางไว้ออนไลน์วันที่ 1 กรกฎาคมเพื่อนร่วมงานของเขายอมรับอย่างรวดเร็วว่าเป็นความจริง
"เมื่อใดก็ตามที่มีการประกาศเช่นนี้" นักวิทยาศาสตร์คอมพิวเตอร์ทฤษฎีมหาวิทยาลัยออสติน Scott Aaronson เขียนไว้ในบล็อกของเขา "~ 99% ของเวลาพิสูจน์ผิดหรือในอัตราใด ๆ มันก็ซับซ้อนเกินไปที่คนนอกจะประเมินได้ อย่างรวดเร็วนี่เป็นหนึ่งใน 1% ที่เหลือของคดีฉันค่อนข้างมั่นใจว่าการพิสูจน์นั้นถูกต้องเพราะอะไรเพราะฉันอ่านและเข้าใจมันใช้เวลาประมาณครึ่งชั่วโมง "
Ryan O'Donnell ศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์ที่ศึกษาทฤษฎีจำนวนที่ Carnegie Mellon University ใน Pittsburgh ชี้ให้เห็นว่าหลักฐานของ Huang สามารถสรุปได้ใน tweet เดียว:
หวางพิสูจน์อะไรจริง ๆ ?
เพื่อความเรียบง่ายลองนึกภาพลูกบาศก์สามมิติที่มีด้านยาว 1 หน่วย หากคุณใส่ลูกบาศก์นี้ลงในระบบพิกัด 3 มิติ (หมายถึงมันมีการวัดในสามทิศทาง) มุมหนึ่งจะมีพิกัด (0,0,0) หนึ่งมุมถัดจากนั้นอาจเป็น (1,0,0) ด้านบนอาจเป็น (0,1,0) เป็นต้น คุณสามารถใช้ครึ่งมุม (สี่มุม) โดยไม่ต้องมีคู่เพื่อนบ้าน: (0,0,0), (1,1,0), (1,0,1) และ (0,1,1) aren ' ทีเพื่อนบ้าน คุณสามารถแสดงสิ่งนี้ได้โดยดูที่คิวบ์ แต่เราก็รู้เพราะมันทั้งหมดต่างจากพิกัดมากกว่าหนึ่งพิกัด
การคาดเดาความไวเป็นเรื่องเกี่ยวกับการค้นหาจำนวนเพื่อนบ้านที่คุณมีเมื่อคุณใช้เวลามากกว่าครึ่งมุมของลูกบาศก์มิติที่สูงขึ้นหรือไฮเปอร์คิวบ์ Gil Gilai นักคณิตศาสตร์จากมหาวิทยาลัยฮิบรูกล่าว คุณสามารถเขียนพิกัดของไฮเปอร์คิวบ์เป็นสตริง 1s และ 0s โดยที่จำนวนมิติคือความยาวของสตริงคาไลบอกวิทยาศาสตร์สด สำหรับไฮเปอร์คิวบ์ 4D เช่นมี 16 จุดที่แตกต่างกันซึ่งหมายถึง 16 สตริงที่แตกต่างกันของ 1s และ 0s ที่มีความยาวสี่หลัก
ตอนนี้เลือกครึ่งบวก 1 คะแนนแต่ละจุดบนไฮเปอร์คิวบ์ (สำหรับไฮเปอร์คิวบ์ 4D นั่นหมายถึงเลือกเก้า - หรือ 8 + 1 - คะแนนที่แตกต่างจากทั้งหมด 16)
จากเซตที่เล็กกว่านี้ให้หาจุดที่มีเพื่อนบ้านมากที่สุด - อะไรคือสิ่งที่ ขั้นต่ำ จำนวนเพื่อนบ้านสามารถมีได้? (เพื่อนบ้านต่างกันเพียงหนึ่งหมายเลขตัวอย่างเช่น 1111 และ 1110 เป็นเพื่อนบ้านเพราะคุณต้องสลับหนึ่งหลักเพื่อเปลี่ยนตัวเลขแรกเป็นวินาที)
หวางพิสูจน์ว่ามุมนี้ต้องมีเพื่อนบ้านอย่างน้อยเท่ากับรากที่สองของจำนวนหลัก - ในกรณีนี้สแควร์รูทของ 4 - ซึ่งก็คือ 2
สำหรับขนาดที่ต่ำคุณสามารถบอกได้ว่านี่เป็นความจริงเพียงแค่ตรวจสอบ มันไม่ยากเลยที่จะตรวจสอบพิกัด 16 ตำแหน่งบนลูกบาศก์ (หรือ "สตริง") สำหรับเพื่อนบ้านตัวอย่างเช่น แต่ทุกครั้งที่คุณเพิ่มมิติลงในคิวบ์จำนวนของสตริงจะเพิ่มเป็นสองเท่า ดังนั้นปัญหาจึงยากที่จะตรวจสอบอย่างรวดเร็ว
ชุดของสตริงที่มีความยาว 30 หลัก - พิกัดไปที่มุมของคิวบ์ 30 มิติ - มีสตริงที่แตกต่างกันมากกว่า 1 พันล้านชุดซึ่งหมายความว่าคิวบ์นั้นมีมากกว่า 1 พันล้านมุม ด้วยสตริงที่มีความยาว 200 หลักจึงมีมากกว่าหนึ่งล้านล้าน นั่นคือล้านล้านพันล้านล้านล้านล้านหรือ 1 ตามด้วย 60 ศูนย์
นี่คือเหตุผลที่นักคณิตศาสตร์ชอบพิสูจน์: พวกเขาแสดงให้เห็นว่ามีบางสิ่งบางอย่างที่เป็นจริงในทุกกรณีไม่ใช่แค่เรื่องง่าย ๆ
"ถ้า n เท่ากับหนึ่งล้าน - นี่หมายความว่าเรามีสายยาว 1 ล้าน - การคาดเดาคือถ้าคุณเอา 2 ^ 1,000,000-1 และบวก 1 แล้วก็มีสตริงที่มี 1,000 เพื่อนบ้าน - รากที่สองของล้าน Kalai พูด
ความก้าวหน้าที่สำคัญครั้งสุดท้ายในการคาดเดาความอ่อนไหวมาในปี 1988 คาไลกล่าวว่าเมื่อนักวิจัยพิสูจน์ว่าสตริงหนึ่งต้องมีอย่างน้อยลอการิทึมของ n เพื่อนบ้าน นั่นเป็นจำนวนที่ต่ำกว่ามาก ลอการิทึม 1,000,000 เป็นเพียง 6 ดังนั้นหลักฐานของหวางเพิ่งค้นพบว่ามีเพื่อนบ้านอย่างน้อย 994 คนออกไปที่นั่น
หลักฐานอันงดงามและ "ลึกลับ"
“ มันลึกลับมาก” คาไลพูดถึงบทพิสูจน์ของหวาง “ มันใช้ 'วิธีการทางสเปกตรัม' ซึ่งเป็นวิธีการที่สำคัญมากในหลาย ๆ ด้านของคณิตศาสตร์ แต่มันใช้วิธีการทางสเปกตรัมในลักษณะที่แปลกใหม่มันยังคงเป็นปริศนา แต่ฉันคิดว่าเราสามารถคาดหวังได้ว่าวิธีการแบบใหม่นี้ แอปพลิเคชันเพิ่มเติม "
ในสาระสำคัญ Huang วางแนวคิดไฮเปอร์คิวบ์โดยใช้อาร์เรย์ของตัวเลขในแถวและคอลัมน์ (เรียกว่าเมทริกซ์) หวางคิดวิธีที่ไม่คาดคิดอย่างสมบูรณ์ในการจัดการเมทริกซ์ด้วยการจัดเรียงที่ผิดปกติของ -1s และ 1s ซึ่ง "ทำให้มันทำงานได้อย่างน่าอัศจรรย์" Aaronson เขียนไว้ในบล็อกของเขา
หวาง "รับเมทริกซ์นี้และเขาดัดแปลงมันด้วยวิธีที่แยบยลและลึกลับ" Kalai กล่าว "มันเหมือนกับว่าคุณมีวงออเคสตราและพวกเขาเล่นดนตรีแล้วคุณก็ปล่อยให้ผู้เล่นบางคนฉันไม่รู้ยืนบนหัวของพวกเขาและเพลงก็เปลี่ยนไปอย่างสิ้นเชิง - อะไรทำนองนั้น"
เพลงต่าง ๆ นั้นกลายเป็นกุญแจสำคัญในการพิสูจน์การคาดเดา Kalai กล่าว มันเป็นเรื่องลึกลับเขากล่าวเพราะแม้ว่านักคณิตศาสตร์จะเข้าใจว่าทำไมวิธีการทำงานในกรณีนี้พวกเขาไม่เข้าใจ "เพลง" ใหม่นี้อย่างสมบูรณ์หรือในกรณีอื่น ๆ ที่อาจมีประโยชน์หรือน่าสนใจ
"เป็นเวลา 30 ปีไม่มีความคืบหน้าและจากนั้นหวางหวงตัดสินปัญหานี้และเขาพบหลักฐานที่ง่ายมากที่คำตอบคือรากที่สองของ n"Kalai พูด" แต่ในช่วง 30 ปีที่ผ่านมา ... ผู้คนตระหนักว่าคำถามนี้สำคัญมากในทฤษฎีการคำนวณ "
การพิสูจน์ของหวางนั้นน่าตื่นเต้นเพราะมันก้าวหน้าไปในสาขาวิทยาศาสตร์คอมพิวเตอร์ Kalai กล่าว แต่ก็น่าสังเกตเพราะมันแนะนำวิธีการใหม่และนักคณิตศาสตร์ยังไม่แน่ใจว่าวิธีการใหม่ของหวางอาจทำให้พวกเขาสำเร็จ
