- Anthropic के मॉडल Claude Opus 4.6 ने Donald Knuth द्वारा कई हफ्तों से अध्ययन किए जा रहे directed Hamiltonian cycle decomposition problem को हल कर दिया
- समस्या (m^3) vertices वाले directed graph को तीन Hamiltonian cycles में decomposition करने की है, और Claude ने इसे odd m के लिए पूरी तरह हल किया
- Claude ने "fiber decomposition", 3D serpentine pattern, depth-first search (DFS), simulated annealing जैसी कई exploration strategies को चरणबद्ध तरीके से अपनाया
- अंततः इसने Python program के रूप में एक general solution निकाला, और Filip Stappers ने m=3 से 101 तक के odd m पर इसे verify करके complete decomposition की पुष्टि की
- Knuth ने इस परिणाम को automated reasoning और creative problem solving में एक breakthrough बताया, और स्पष्ट किया कि even m के मामले अब भी unsolved हैं
समस्या की पृष्ठभूमि और परिभाषा
- यह शोध विषय directed Hamiltonian cycles से संबंधित है, और Knuth की पुस्तक The Art of Computer Programming के आगामी खंड में शामिल किया जाना तय है
- graph (m^3) vertices (ijk) से बना है, और हर vertex से तीन edges निकलती हैं: (i+jk), (ij+k), (ijk+)
- लक्ष्य सभी (m>2) के लिए इन edges को तीन directed (m^3)-cycles में decompose करने का एक general solution खोजना है
Claude की exploration process
- Claude Opus 4.6, Anthropic का hybrid reasoning मॉडल है; Filip Stappers ने इसे यह समस्या दी और प्रगति प्रक्रिया को document करने का निर्देश दिया
- शुरुआती चरण में Claude ने समस्या को functional graph और permutation assignment problem के रूप में फिर से परिभाषित किया, और linear तथा quadratic functional approaches आज़माए, लेकिन वे असफल रहे
- इसके बाद इसने DFS search, 2D serpentine pattern analysis, 3D Gray code आधारित patterns आदि को क्रमशः परखा
- फिर fiber decomposition approach अपनाई गई, जिसमें (s = (i+j+k) \mod m) के आधार पर layered structure का analysis किया गया, और simulated annealing (SA) के जरिए partial solutions मिले
समाधान की खोज और verification
- exploration के 31वें चरण में Claude ने fiber-wise single-coordinate dependent rules का उपयोग करने वाला एक Python program तैयार किया
- इस program ने m=3,5,7,9,11 पर पूरी तीन Hamiltonian cycles उत्पन्न कीं
- Filip Stappers ने इसे m=3~101 के सभी odd m पर test किया और complete decomposition की पुष्टि की
- Knuth ने इसे C code में सरल बनाकर प्रस्तुत किया, और गणितीय रूप से सिद्ध किया कि हर cycle की लंबाई वास्तव में (m^3) है
generalization और mathematical analysis
- यह पाया गया कि (m=3) की कुछ Hamiltonian cycles को सभी odd m के लिए generalize किया जा सकता है
- (m=3) पर 11,502 cycles में से 1,012 को (m=5) तक generalize किया जा सकता है, और 996 को (m=7) तक
- ये 996 सभी odd m>1 के लिए generalize की जा सकती हैं
- Claude-like decomposition को ऐसे सरल rules से परिभाषित किया गया है जो केवल i, j, s के boundary values (0 या m−1) पर निर्भर करते हैं
- प्रमेय: यदि Claude-like decomposition सभी odd m>1 पर मान्य हो, तो m=3 की तीनों cycles ऐसी generalizable Hamiltonian cycles होनी चाहिए
- computation के अनुसार, 760 Claude-like decompositions सभी odd m पर valid हैं
even m की अनसुलझी स्थिति और निष्कर्ष
- even m का मामला अब भी open है
- (m=2) असंभव है, यह पहले के शोध में सिद्ध किया जा चुका है
- Claude ने (m=4,6,8) पर partial solutions पाए, लेकिन generalization में असफल रहा
- even m की exploration के दौरान Claude ने errors और abnormal behavior दिखाया, जिसके कारण खोज रोक दी गई
- Knuth ने इसे AI-आधारित automated reasoning की ऐतिहासिक उपलब्धि कहा, और टिप्पणी की कि यह Claude Shannon के नाम के अनुरूप प्रगति है
परिशिष्ट: अन्य दो cycles के rules
- दूसरी cycle (c=1):
- (s=0) हो तो j बढ़ता है, (0<s<m−1) हो तो i बढ़ता है, और (s=m−1) पर i>0 हो तो k बढ़ता है, i=0 हो तो j बढ़ता है
- तीसरी cycle (c=2):
- (s=0) पर j<m−1 हो तो i बढ़ता है, j=m−1 हो तो k बढ़ता है
- (0<s<m−1) पर i<m−1 हो तो k बढ़ता है, i=m−1 हो तो j बढ़ता है
- (s=m−1) हो तो i बढ़ता है
- हर cycle में s=0 पर vertices का क्रम स्पष्ट रूप से दिया गया है, और इसके जरिए पूरे cycle की संरचना सिद्ध की जा सकती है
अभी कोई टिप्पणी नहीं है.