เคล็ดลับทางคณิตศาสตร์สำหรับการควบคุมระยะกลาง | นิตยสารควอนตั้ม

จนถึงปีนี้ ควอนตั้ม ได้บันทึกความก้าวหน้าที่สำคัญสามประการในทฤษฎีแรมซีย์ การศึกษาวิธีหลีกเลี่ยงการสร้างรูปแบบทางคณิตศาสตร์ เดอะ ผลลัพธ์แรก กำหนดขีดจำกัดใหม่ว่าชุดของจำนวนเต็มจะมีขนาดใหญ่เพียงใดโดยไม่ต้องมีตัวเลขที่เว้นระยะเท่าๆ กันสามตัว เช่น {2, 4, 6} หรือ {21, 31, 41} เดอะ ที่สอง และ ที่สาม ในทำนองเดียวกันให้ขอบเขตใหม่กับขนาดของเครือข่ายโดยไม่มีกลุ่มของจุดที่เชื่อมต่อทั้งหมดหรือแยกออกจากกัน

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

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

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

Gasarch ได้ศึกษาคำถามในทฤษฎีแรมซีย์เกี่ยวกับจำนวนจำกัดที่ใหญ่เกินกว่าปัญหาจะแก้ไขได้ด้วยการดุร้าย ในโครงการหนึ่ง เขาได้นำเสนอความก้าวหน้าครั้งแรกของปีนี้ในเวอร์ชันจำกัด ซึ่งเป็นบทความฉบับเดือนกุมภาพันธ์โดย แซนเดอร์ เคลลีย์นักศึกษาระดับบัณฑิตศึกษาจาก University of Illinois, Urbana-Champaign และ ราหู เมกา แห่งมหาวิทยาลัยแคลิฟอร์เนีย ลอสแอนเจลิส Kelley และ Meka พบขอบเขตบนใหม่เกี่ยวกับจำนวนเต็มระหว่าง 1 ถึง N คุณสามารถใส่ลงในชุดในขณะที่หลีกเลี่ยงการก้าวหน้าสามระยะหรือรูปแบบของตัวเลขที่เว้นระยะเท่า ๆ กัน

แม้ว่าผลลัพธ์ของ Kelley และ Meka จะมีผลก็ตาม N มีขนาดค่อนข้างเล็ก มันไม่ได้ให้ขอบเขตที่เป็นประโยชน์อย่างยิ่งในกรณีนั้น สำหรับค่าที่น้อยมากของ Nคุณควรใช้วิธีง่ายๆ ดีกว่า ถ้า N คือพูด 5 แค่ดูชุดตัวเลขที่เป็นไปได้ทั้งหมดระหว่าง 1 ถึง Nแล้วเลือกรายการที่ไม่มีความก้าวหน้าที่ใหญ่ที่สุด: {1, 2, 4, 5}

แต่จำนวนคำตอบที่เป็นไปได้ที่แตกต่างกันนั้นเพิ่มขึ้นอย่างรวดเร็วและทำให้ยากเกินไปที่จะใช้กลยุทธ์ง่ายๆ เช่นนี้ มีมากกว่า 1 ล้านชุดประกอบด้วยตัวเลขระหว่าง 1 ถึง 20 มีมากกว่า 10⁶⁰ โดยใช้ตัวเลขระหว่าง 1 ถึง 200 การค้นหาชุดที่ไม่มีความก้าวหน้าที่ดีที่สุดสำหรับกรณีเหล่านี้ต้องใช้พลังการประมวลผลจำนวนมาก แม้จะมีกลยุทธ์การปรับปรุงประสิทธิภาพก็ตาม “คุณต้องสามารถบีบประสิทธิภาพออกจากสิ่งต่าง ๆ ได้มากมาย” กล่าว เจมส์ เกล็นนักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัยเยล ในปี 2008 Gasarch, Glenn และ ไคลด์ ครูสคาล ของมหาวิทยาลัยแมรี่แลนด์ เขียนโปรแกรม เพื่อค้นหาฉากที่ปราศจากความก้าวหน้าที่ใหญ่ที่สุดจนถึง N Glenn กล่าว

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

Gasarch, Glenn และ Kruskal ยังได้ลองใช้กลยุทธ์อื่นๆ อีกหลายอย่าง แนวคิดที่มีแนวโน้มประการหนึ่งขึ้นอยู่กับความบังเอิญ วิธีง่ายๆ ในการสร้างชุดที่ไม่มีความก้าวหน้าคือการใส่ 1 ในชุดของคุณ จากนั้นให้เพิ่มจำนวนถัดไปที่ไม่ได้สร้างความก้าวหน้าทางเลขคณิตเสมอ ทำตามขั้นตอนนี้จนกว่าจะถึงเลข 10 และคุณจะได้ชุด {1, 2, 4, 5, 10} แต่ปรากฎว่านี่ไม่ใช่กลยุทธ์ที่ดีที่สุดโดยทั่วไป “ถ้าเราไม่เริ่มที่ 1 ล่ะ?” Gasarch กล่าวว่า “ถ้าคุณเริ่มต้นจากที่สุ่ม คุณทำได้ดีกว่านี้จริงๆ” นักวิจัยไม่รู้ว่าเหตุใดการสุ่มจึงมีประโยชน์ เขากล่าวเสริม

การคำนวณเวอร์ชันที่จำกัดของผลลัพธ์ทฤษฎีแรมซีย์ใหม่อีกสองตัวนั้นสร้างความสับสนมากกว่าการกำหนดขนาดของเซตที่ไม่มีความก้าวหน้า ผลลัพธ์เหล่านี้เกี่ยวข้องกับเครือข่ายทางคณิตศาสตร์ (เรียกว่ากราฟ) ซึ่งประกอบด้วยโหนดที่เชื่อมต่อกันด้วยเส้นที่เรียกว่าเอดจ์ หมายเลขแรมซีย์ r(s, t) คือจำนวนโหนดที่น้อยที่สุดที่กราฟต้องมีก่อนที่จะหลีกเลี่ยงไม่ให้รวมกลุ่มของ s โหนดที่เชื่อมต่อหรือ t พวกที่ไม่ได้เชื่อมต่อ ตัวเลขแรมซีย์เป็นเรื่องน่าปวดหัวในการคำนวณเลขคู่นั้น r(5, 5) ไม่เป็นที่รู้จัก - อยู่ระหว่าง 43 ถึง 48

ใน 1981, เบรนแดน แมคเคย์ซึ่งปัจจุบันเป็นนักวิทยาศาสตร์คอมพิวเตอร์ที่ Australian National University ได้เขียนโปรแกรมซอฟต์แวร์ชื่อ nauty ซึ่งมีจุดประสงค์เพื่อทำให้การคำนวณตัวเลขของ Ramsey ง่ายขึ้น Nauty ช่วยให้นักวิจัยไม่ต้องเสียเวลาตรวจสอบกราฟสองกราฟที่เพิ่งพลิกกลับหรือหมุนเวอร์ชันของกราฟกัน “ถ้าใครอยู่ในพื้นที่นั้นและไม่ได้เล่นทะลึ่ง เกมก็จบลงแล้ว คุณต้องใช้มัน” กล่าว สตานิสลาฟ รัดซิสซอฟสกี้นักคณิตศาสตร์แห่งสถาบันเทคโนโลยีโรเชสเตอร์ ถึงกระนั้น จำนวนของการคำนวณที่เกี่ยวข้องก็แทบจะไม่สามารถเข้าใจได้ ในปี 2013 Radziszowski และ ยาน โกเอดจ์เบอร์ พิสูจน์แล้วว่า r(3, 10) มากที่สุดคือ 42. “ฉันคิดว่ามันต้องใช้เวลาเกือบ 50 ปี CPU” Goedgebeur นักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัย KU Leuven ในเบลเยียมกล่าว

หากคุณไม่สามารถคำนวณจำนวนแรมซีย์ที่แน่นอนได้ คุณสามารถลองจำกัดค่าให้แคบลงด้วยตัวอย่าง หากคุณพบกราฟ 45 โหนดที่ไม่มี XNUMX โหนดที่เชื่อมต่อทั้งหมด และไม่มี XNUMX โหนดที่ถูกตัดการเชื่อมต่อทั้งหมด นั่นจะเป็นการพิสูจน์ว่า r(5, 5) มีค่ามากกว่า 45 นักคณิตศาสตร์ที่ศึกษาตัวเลขแรมซีย์เคยคิดว่าการหาตัวอย่างเหล่านั้นที่เรียกว่ากราฟแรมซีย์นั้นเป็นเรื่องง่าย Radziszowski กล่าว แต่มันไม่เป็นเช่นนั้น “มีความคาดหวังว่าสิ่งก่อสร้างทางคณิตศาสตร์ที่ดีและเจ๋งจะให้สิ่งก่อสร้างที่ดีที่สุดเท่าที่จะเป็นไปได้ และเราแค่ต้องการคนจำนวนมากขึ้นเพื่อทำงานนี้” เขากล่าว “ความรู้สึกของฉันมากขึ้นเรื่อย ๆ ว่ามันวุ่นวาย”

ความบังเอิญเป็นทั้งอุปสรรคในการทำความเข้าใจและเป็นเครื่องมือที่มีประโยชน์ เจฟฟรีย์ เอ็กโซนักวิทยาศาสตร์คอมพิวเตอร์แห่ง Indiana State University ได้ใช้เวลาหลายปีในการปรับแต่งวิธีการสุ่มเพื่อสร้างกราฟของแรมซีย์ ใน กระดาษ 2015 ประกาศกราฟแรมซีย์ใหม่จำนวนมากที่ทำลายสถิติ Exoo และ Milos Tatarevic สร้างกราฟแบบสุ่ม จากนั้นค่อยๆ ปรับแต่งโดยการลบหรือเพิ่มขอบที่ลดจำนวนคลัสเตอร์ที่ไม่ต้องการจนกว่าจะพบกราฟแรมซีย์ Radziszowski กล่าวว่าเทคนิคของ Exoo นั้นเป็นศิลปะมากพอๆ กับทุกสิ่ง บางครั้งพวกเขาต้องการให้เขารวมหลายวิธีเข้าด้วยกันหรือใช้วิจารณญาณว่าจะเริ่มต้นด้วยกราฟประเภทใด Radziszowski กล่าวว่า "หลายคนพยายามทำ แต่พวกเขาทำไม่ได้"

เทคนิคที่พัฒนาขึ้นเพื่อสร้างกราฟแรมซีย์อาจมีประโยชน์ในวงกว้างมากขึ้นในสักวันหนึ่ง Goedgebeur กล่าว ทำงาน การสร้างกราฟประเภทอื่นๆ เช่น กราฟที่แสดงสารประกอบทางเคมี “ไม่น่าเป็นไปได้ที่เทคนิคเหล่านี้สามารถถ่ายโอนและปรับเปลี่ยนเพื่อช่วยให้สร้างกราฟประเภทอื่นๆ ได้อย่างมีประสิทธิภาพมากขึ้น (และในทางกลับกัน)” เขาเขียนในอีเมล

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