కలిపితే లక్ష్యం వచ్చే సంఖ్యలను ఎంచుకోవడం, దాదాపు వాటిని చదివినంత వేగంగా

ఎవరైనా చెప్పగల ఒక పజిల్ ఇది. మీ దగ్గర పూర్ణ సంఖ్యల జాబితా ఉంది — ఉదాహరణకు 3, 9, 14, 20 — ఒక లక్ష్యం, ఉదాహరణకు 23. వాటిలో కొన్నింటిని కలిపితే సరిగ్గా లక్ష్యం వచ్చేలా ఎంచుకోగలరా? (ఇక్కడ, అవును: 3 + 20 లేదా 9 + 14.) ఇదే ఉపసమితి మొత్తం (Subset Sum) సమస్య, కంప్యూటర్ శాస్త్రంలో అత్యంత ప్రాథమిక సమస్యల్లో ఒకటి. పత్రం దీన్ని ఒక ప్రాథమిక NP-సంపూర్ణ (NP-complete) సమస్యగా వర్ణిస్తుంది, ఖచ్చితంగా పరిష్కరించడం కష్టమని పేరున్న సమస్యల కుటుంబం.

అయినా ఒక లొసుగు ఉంది. సంఖ్యలు మరీ పెద్దవి కాకపోతే, తెలివైన అల్గారిథంలు వాటి పరిమాణంపై ఆధారపడిన సమయంలో నడుస్తాయి. 1957లో బెల్‌మన్ రూపొందించిన సంప్రదాయ పద్ధతి సంఖ్యల లెక్క n, లక్ష్యం t ల లబ్ధానికి అనులోమానుపాతంలో సమయం తీసుకుంటుంది. అప్పటి నుంచి, అల్గారిథంలు మెరుగుపడుతూనే ఉన్నాయి:

• పిసింగర్ (1999): n × N కు అనులోమానుపాతంలో, ఇక్కడ N అతిపెద్ద సంఖ్య;
• బ్రింగ్‌మన్ (2017): సుమారు n + t;
• అనేక బృందాలు (2021–2024): సుమారు n + N^(5/3), తర్వాత n + N^(3/2).

అంతిమ లక్ష్యం సుమారు n + N సమయం — ఇన్‌పుట్‌ను చదవడం కంటే పెద్దగా ఎక్కువ కాదు. ఈ రంగంలోని పరిశోధకులు దాన్ని ఈ పని ధోరణిలో “అత్యంత కీలకమైన అపరిష్కృత సమస్య” అన్నారు.

లక్ష్యానికి వెంట్రుకవాసి దూరంలో

చైనాలోని ఝెజియాంగ్ విశ్వవిద్యాలయానికి చెందిన లిన్ చెన్ (Lin Chen), యుచెన్ మావో (Yuchen Mao), గువోచువాన్ ఝాంగ్ (Guochuan Zhang) n + N^(1+ε) సమయంలో నడిచే ఒక అల్గారిథంను ఇస్తారు, ఇక్కడ ε ముందుగానే స్థిరపరిచిన ఏదైనా చిన్న ధన సంఖ్య కావచ్చు — 0.1, 0.01, 0.001. ఇది నిర్ణయాత్మకమైనది (deterministic), ఋణ సంఖ్యలను, పునరావృత విలువలను అంగీకరిస్తుంది, ఒక గణిత నిరూపణతో వస్తుంది. రచయితలు ఈ సమయాన్ని దాదాపు సరైనది (near-optimal) అంటారు.

ఫలితం సదిశలకు విస్తరిస్తుంది: అనేక మొత్తాలు ఒకేసారి తమ లక్ష్యాలను చేరేలా అంశాలను ఎంచుకోవడం, d నిరూపకాలకు N^(d+ε) సమయంతో. అది, క్రమంగా, పూర్ణాంక ప్రోగ్రామింగ్ (integer programming) గురించి అనేక బృందాలు లేవనెత్తిన ఒక ప్రశ్నలో కొంత భాగానికి సమాధానమిస్తుంది — చరరాశులు పరిమితమైన సమీకరణాల వ్యవస్థలకు పూర్ణ సంఖ్యా పరిష్కారాలను కనుగొనడం. రెండు పర్యవసానాలను స్పష్టంగా రూపొందించారు: సంఖ్యల సమితిని రెండు సమాన సగాలుగా విభజించడం, రెండు ఒకేలాంటి యంత్రాల మధ్య పనులను సాధ్యమైనంత సమానంగా పంచడం.

సంఖ్యలను ఉన్నత కొలతలోకి ఎత్తడం

కీలక ఆలోచన జ్యామితీయమైనది. సంఖ్యలు దట్టంగా ఉండి, లక్ష్యం సాధ్యమైన మొత్తాల పరిధికి బాగా లోపల ఉన్నప్పుడు సమస్య సులభమని ఇప్పటికే తెలుసు. రచయితల పరిశీలన: సంఖ్యల ఒక పలుచని సమితిని ఉన్నత కొలత నుంచి చూసినప్పుడు దట్టంగా కనిపించవచ్చు.

వారి ఉదాహరణ {11, 12, 22, 24} సమితి. 11, 22 లను మొదటి అక్షం వెంట ఒక అడుగు, రెండు అడుగులుగా, 12, 24 లను రెండవ అక్షం వెంట ఒక అడుగు, రెండు అడుగులుగా రాయండి. అప్పుడు సాధ్యమైన మొత్తాలు ఒక చిన్న 4-బై-4 చతురస్రంలోని ప్రతి బిందువునూ నింపుతాయి. కానీ ఆ చతురస్రాన్ని తిరిగి ఒక రేఖపైకి అణచివేస్తే — 11x + 12y లెక్కించడం ద్వారా — మొత్తాలు 0, 69 మధ్య చెల్లాచెదురుగా, మధ్యలో ఖాళీలున్న ఏడు వేర్వేరు గుంపులుగా ఏర్పడతాయి. ఖాళీలు ప్రక్షేపణ యొక్క భ్రమ; రెండు కొలతల్లో, నిర్మాణం సరళమైనది.

అల్గారిథం సంకలన కాంబినేటారిక్స్ (additive combinatorics) ఫలితాలను ఉపయోగించి ఏ ఇన్‌పుట్‌కైనా అలాంటి ఉన్నత-కొలత నిరూపకాలను నిర్మిస్తుంది. “నిండిన” ప్రాంతం లోపల, సమాధానాలు ఉచితంగా వస్తాయి. అంచు దగ్గర ఉన్న ఒక పలుచని మండలానికి మాత్రమే నిజమైన పని అవసరం, అల్గారిథం దాన్ని చిన్న సమస్యలుగా విభజించి పునరావృతంగా (recursively) పరిష్కరిస్తుంది. ప్రతి రౌండ్ ఆ మండలాన్ని తీవ్రంగా కుదిస్తుంది, ఎప్పుడూ స్థిర సంఖ్యలో మాత్రమే కొత్త కొలతలు జోడించబడతాయి.

నిరూపణ ఎలా నిర్మించబడింది

పత్రం ఒక “AI నిరాకరణ ప్రకటన”తో మొదలవుతుంది. ఈ సమస్య యొక్క దట్టమైన, బహుళ-కొలత వెర్షన్లపై తమ ఇటీవలి పని ఆధారంగా, రచయితలు ప్రధాన నిరూపణ మార్గాన్ని స్వయంగా రూపొందించారు. తర్వాత ఈ ఆలోచనలను పూర్తి గణిత నిరూపణలుగా మార్చడానికి GPT Astra Ultra అనే AI మోడల్‌ను ఉపయోగించారు. అది అనేక ఉపసిద్ధాంతాల (lemmas) వద్ద చిక్కుకుపోయింది, వాటిని రచయితల ఆలోచనలతో పరిష్కరించారు; ఒక బహిరంగ పరిశోధనా గమనిక ఆ సంభాషణలను నమోదు చేస్తుంది. ప్రాథమిక యాదృచ్ఛిక (randomised) అల్గారిథం పూర్తయిన తర్వాత, మోడల్ దాన్ని నిర్ణయాత్మక, బహుళ-కొలత వెర్షన్లకు “రచయితల నుంచి ఎలాంటి మార్గదర్శనం లేకుండా” విస్తరించింది. మోడల్ పత్రం ముసాయిదాను కూడా రాసింది, రచయితలు రాసిన ప్రకారం, Lean 4 నిరూపణ సహాయకంలో ఒక నిరూపణతో దాని ప్రధాన ఫలితాలను ధృవీకరించింది. విషయానికి పూర్తి బాధ్యత రచయితలదే.

ఇంకా ముగింపు రేఖ కాదు

ఘాతాంకం సరిగ్గా 1 కాకుండా 1 + ε, ε తగ్గే కొద్దీ దాగిన స్థిరాంకాలు పెరుగుతాయి; కొలతల సంఖ్యపై ఆధారపడటం సరైనదిగా మెరుగుపరచబడలేదు. రచయితలే అల్గారిథంను “చాలా సంక్లిష్టమైనది” అని వర్ణిస్తారు. పత్రం సైద్ధాంతికమైనది: ఎలాంటి అమలు లేదా బెంచ్‌మార్క్‌ను నివేదించలేదు.