Claude के cycles [PDF]

 (www-cs-faculty.stanford.edu)
4 पॉइंट द्वारा GN⁺ 2026-03-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 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 की संरचना सिद्ध की जा सकती है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2026-03-04
Hacker News की राय

  • यह सोचना दिलचस्प है कि RL scalability किन-किन समस्या क्षेत्रों पर लागू हो सकती है
    पहले जिन चीज़ों के लिए मानव cognition पर निर्भर रहना पड़ता था, अब वे पैटर्न probability distribution के भीतर समा गए हैं, इसलिए अब कोई भी उन तक पहुँच सकता है
    लेकिन जब विज्ञान की सीमाएँ लगातार फैलती रहती हैं, तब क्या मॉडल उसके साथ कदम मिला पाएँगे, यह सवाल बना रहता है
    2030 में Anthropic को Claude को up-to-date रखना है तो या तो (a) fixed model में continuous learning चाहिए होगा या (b) continuous training, और दोनों ही आसान नहीं हैं

    • open-weight models किसी तरह के time capsule जैसे हैं
      knowledge cutoff के बाद वे हमेशा उसी समय पर अटके रह जाते हैं
    • अगर data sharing की अनुमति हो, तो आज के inference results कल का training data बन सकते हैं
      यह भी सोचा जा सकता है कि researchers को free inference दिया जाए और बदले में उनके thought traces को training data की तरह इस्तेमाल किया जाए
    • हाल के researchers की बातें सुनकर लगता है कि आगे model architecture का विकास context window को बहुत बड़ा करने की दिशा में जाएगा
      Qwen3-next, Qwen3.5, Nemotron 3 Nano जैसे models hybrid attention के ज़रिए memory cost घटाते हुए million-token window को support करते हैं
    • ज़्यादातर research और learning पहले से ही LLMs और coding agents के ज़रिए हो रही है
      human verification, code execution, और search के माध्यम से मिलने वाला real-time feedback loop model training signal की तरह काम करता है
    • 2030 तक शायद उल्टा Claude ही Anthropic को up-to-date रखे
      आधा मज़ाक है, लेकिन पूरी तरह नामुमकिन भी नहीं

  • इससे पहले हुई Wolfram और Knuth की GPT-4 बातचीत याद आ गई
    Knuth उस समय skeptical थे, लेकिन हाल के Opus 4.6 जैसे models को देखकर लगता है कि उनका रुख कुछ नरम हुआ है
    नए सबूत के आधार पर अपना विचार बदलना वाकई काबिले-तारीफ़ है
    संबंधित बातचीत यहाँ देखी जा सकती है

    • नए evidence के आधार पर prior probability को update करना ही Bayesian statistics की खूबसूरती है
      यही वैज्ञानिक सोच का मूल भी है

  • मुझे लगा कि Knuth की लिखावट की शुरुआत कुछ हद तक misleading है
    ऐसा लगता है जैसे Claude ने समस्या सीधे हल कर दी, जबकि वास्तव में Claude ने उदाहरण बनाए और Knuth ने उन्हें generalize करके proof में बदला

    • मैंने भी Claude के साथ ऐसा ही experiment किया है, और human व LLM की synergy सच में बहुत बड़ी होती है
      LLM दिशा तय करने में कमज़ोर होता है, लेकिन एक बार दिशा मिल जाए तो deep exploration बहुत अच्छी तरह करता है
      उसे अकेला छोड़ दें तो वह भटक सकता है, लेकिन इंसान lead करे तो वह शानदार partner बन जाता है
    • मुझे नहीं लगता कि Knuth ने इसे बढ़ा-चढ़ाकर बताया
      Claude ने समस्या के core में सीधे प्रवेश करने वाली भूमिका निभाई, और इंसान ने बस उसे तराशा
    • यह भी कहा जा सकता है कि Knuth के अर्थ में Claude ने ही ‘solution’ दिया
      proof को व्यवस्थित करना तो secondary work भर है
    • पहले के प्रयासों पर वापस जाकर reflect और revise करने की क्षमता साफ़ तौर पर intelligence का संकेत लगती है

  • Claude के even case पर रुक जाने वाली बात दिलचस्प लगी
    शायद उन्होंने claude.ai या claude code में से कुछ इस्तेमाल किया होगा, और वह context overflow (dumb zone) में चला गया होगा

    • अच्छा होता अगर इस dumb zone को visualize किया जा सकता
      जैसे Copilot में context usage graph दिखता है, वैसा कुछ users को दिखाई दे तो काफ़ी उपयोगी होगा
    • आख़िरकार context compacting किए बिना नतीजे बुरी तरह बिगड़ जाते हैं
    • ‘plan document’ का ज़िक्र देखकर लगता है कि session management document इस्तेमाल किया गया था
    • कुछ लोग यह भी पूछ रहे थे कि dumb zone आख़िर है क्या

  • Arthur C. Clarke द्वारा प्रसिद्ध किया गया pentomino puzzle मैंने Claude से हल करवाने की कोशिश की
    उसने board और pieces को 64-bit integers के रूप में व्यक्त करके एक C# program बनाया और जल्दी हल भी कर लिया, लेकिन 20x3 case में गलत mapping के कारण गलत जवाब दे दिया
    यह दिलचस्प है, क्योंकि यह वैसी गलती है जैसी इंसान भी कर सकता है

  • संक्षेप में, Knuth ने समस्या दी और उनके एक दोस्त ने Claude के साथ लगभग 30 बार exploration किया
    Claude ने odd case को हल करने वाला Python program बनाया, और Knuth ने उस approach का proof दिया
    even case अब भी unsolved problem बना हुआ है

    • लेकिन Knuth का “careful human guidance” कहना कुछ बढ़ा-चढ़ाकर कहा गया लगता है
      असल में Claude अक्सर रुक जाता था या गलती करता था, और इंसान का काम बस कभी-कभी उसे remind करना भर था
    • शायद Knuth जिस बात पर ज़ोर दे रहे थे, वह यह है कि formal proof अब भी इंसान का काम है
      मूल idea किससे आया, यह अब भी साफ़ नहीं है

  • आजकल unsolved problems पर काम करना सचमुच बड़ा रोमांचक समय लगता है
    मन करता है कि 10 साल पहले की research को फिर से Claude के साथ explore करूँ

  • LLM की ताकत मुझे तीन चीज़ों में दिखती है: विशाल knowledge, connections बनाने की क्षमता, और बिना थके trial and error
    ये तीनों मिल जाएँ तो कभी-कभी चौंकाने वाले नतीजे निकलते हैं
    शायद P≠NP का proof भी किसी ऐसे धुंधले connection में छिपा हो जिसे इंसान ने अभी तक नहीं देखा

    • आख़िरी बिंदु शायद LLM की अपनी विशेषता कम और agent loop की विशेषता ज़्यादा हो
      LLM तो बस उस loop का एक घटक है
    • फिर भी बिना थके दोहराव वाला exploration इंसानों की तुलना में बड़ा फ़ायदा है
      बाकी सब समान हो तो यही निर्णायक अंतर बन सकता है
    • इन तीनों के मिलने से शानदार नतीजे आते हैं, इस बात से मैं पूरी तरह सहमत हूँ
    • लेकिन यह संभावना डरावनी भी लगती है कि ऐसी क्षमताएँ surveillance systems में इस्तेमाल हो सकती हैं
    • ‘connections बनाने की क्षमता’ शायद दरअसल training data में पहले से मौजूद connections तक ही सीमित है
      पूरी तरह नए connections बनाना अभी भी मुश्किल लगता है

  • यह बात सही है या नहीं, इस पर संदेह है कि “LLM तो बस अगला शब्द predict करने वाली मशीन है”
    अगर ऐसा है, तो इस तरह की problem solving को कैसे समझाया जाए? क्या यह ‘सोचना’ है?

    • अगर आप Einstein के अगले बोले जाने वाले शब्द को पूरी तरह predict कर सकते हों, तो आप पहले ही intelligence को implement कर चुके होंगे
      “सबसे अधिक probable word” कहना हद से ज़्यादा simplified explanation है
    • यह explanation base model पर तो लागू होती है, लेकिन Opus 4.6 जैसे models में उसके ऊपर RLHF और अतिरिक्त training जुड़ी हुई है
      आखिरकार “आगे क्या होगा, इसका अच्छा अनुमान लगाने की क्षमता” ही शायद intelligence की परिभाषा हो सकती है
    • base model वेब पर “Answer:” जैसे patterns सीखते-सीखते स्वाभाविक रूप से problem-solving patterns भी सीख लेता है
      RLHF की वजह से उसे सिर्फ़ prediction नहीं, बल्कि useful answers देने पर reward मिलता है
      इसी कारण “delve” जैसे expressions ज़रूरत से ज़्यादा बार दिखाई देते हैं
      संबंधित जानकारी के लिए AI SIGNS दस्तावेज़ देखें
    • अंततः यह अब भी probability distribution से शब्द चुनने की प्रक्रिया है, लेकिन वही distribution खुद intelligence का core है
      LLM उसी distribution को सीख रहा है
    • “सबसे अधिक probable word” जैसा साधारण mechanism जब पूरी मानवता के ज्ञान के साथ जुड़ता है, तो वह बेहद शक्तिशाली बन जाता है
      इसे बस सरलीकृत करके खारिज करना तकनीक के असली स्वरूप को नज़रअंदाज़ करना है

  • यह दिलचस्प है कि यह खुद Knuth की रिपोर्ट है
    अब समय है कि इसे बिना LLM की मदद के खुद पढ़ा और समझा जाए

    • समय नहीं था, इसलिए मैंने उसकी जगह किसी और का बनाया हुआ summary link देख लिया