కంప్యూటర్ సైన్స్‌లో 1962 నాటి అవరోధం కూలింది

హామిల్టోనియన్ వలయం (Hamiltonian cycle) అంటే ఒక జాలంలోని ప్రతి బిందువునూ సరిగ్గా ఒక్కసారి సందర్శించి ప్రారంభ స్థానానికి తిరిగి వచ్చే పర్యటన. దిశాత్మక (directed) జాలంలో, ప్రతి లింకు ఒకవైపు వీధిలాగా ఒకే దిశలో అనుసరించగల బాణం. ఈ సమస్య యొక్క భారిత (weighted) రూపమే అసౌష్ఠవ ప్రయాణ విక్రేత సమస్య (asymmetric travelling salesman problem).

అలాంటి వలయం ఉందో లేదో నిర్ణయించడం పాఠ్యపుస్తకాల్లోని ఒక కఠిన సమస్య. 1962లో రిచర్డ్ బెల్‌మన్, అలాగే స్వతంత్రంగా మైకేల్ హెల్డ్, రిచర్డ్ కార్ప్ — n బిందువుల జాలానికి దీన్ని సుమారు 2ⁿ కాలంలో (బహుపది వేగంతో మాత్రమే పెరిగే కారకాలను మినహాయించి) పరిష్కరించే డైనమిక్ ప్రోగ్రామింగ్ అల్గారిథంలను ఇచ్చారు. అరవై ఏళ్లకు పైగా, సాధారణ దిశాత్మక జాలాలపై ఎవరూ దీని కంటే మౌలికంగా మెరుగ్గా చేయలేకపోయారు.

దిశారహిత దాయాది ఇప్పటికే కూలిపోయింది

రెండువైపుల లింకులు ఉన్న జాలాలకు, ఆండ్రియాస్ బ్యోర్క్‌లుండ్ 2014లో 1.657ⁿలో నడిచే యాదృచ్ఛిక అల్గారిథంతో ఈ అవరోధాన్ని ఛేదించారు; పత్రం ప్రకారం, ఈ కృషికి ఆయనకు 2016 EATCS–IPEC నెరోడ్ బహుమతి లభించింది. సాధారణ దిశారహిత జాలాలకు ఇప్పటికీ అదే అత్యంత వేగవంతమైనదిగా తెలిసిన అల్గారిథం. దిశాత్మక జాలాలకు పురోగతి ప్రత్యేక సందర్భాల్లో మాత్రమే వచ్చింది — ద్విభాగ జాలాలు, ఒక్కో బిందువుకు కొద్ది లింకులే ఉన్న జాలాలు — లేదా నిరూపించని ఒక ఊహ కింద, స్ట్రాసెన్ యొక్క అనంతస్పర్శి ర్యాంక్ ఊహ (asymptotic rank conjecture) కింద.

కొత్త హద్దు

టోక్యో విశ్వవిద్యాలయానికి చెందిన టొమొహిరో కోఆనా, టోక్యో సంస్థ CyberAgentకు చెందిన సో కుమాబే ఇప్పుడు దిశాత్మక సమస్యను

O((375/196)ⁿ) = O(1.9133ⁿ)**

కాలంలో నిర్ణయించే యాదృచ్ఛిక అల్గారిథంను ఇస్తున్నారు.

సాధారణ దిశాత్మక జాలాలకు, 1962 తర్వాత ఘాతాంక భూమిలో ఇదే మొదటి మెరుగుదల.

బేసి, సరి లెక్కింపు

కష్టం సూక్ష్మమైనది. వలయాలను 2 మాడ్యులోలో లెక్కించడం — అంటే వాటి సంఖ్య బేసా సరా అని మాత్రమే తెలుసుకోవడం — 2ⁿ కంటే తక్కువలో ఇప్పటికే సాధ్యమైంది. కానీ సున్నా కాని సరి సంఖ్యలో వలయాలు ఉంటే అది సరిగ్గా సున్నాలాగే కనిపిస్తుంది. దీనికి సంప్రదాయ పరిష్కారం లింకులకు యాదృచ్ఛిక భారాలు ఇవ్వడం, తద్వారా ఏదో ఒక మొత్తం భారం వద్ద పరిష్కారం ఏకైకమవుతుంది (వేరుచేత ఉపసిద్ధాంతం, isolation lemma); కానీ సమత్వాన్ని వేగంగా లెక్కించే పద్ధతి భారాలను నిర్వహించలేకపోయింది.

రచయితల వంటకం, సరళమైన మాటల్లో:

1. వలయంలోని ఒక బాణాన్ని ఊహించి, దానికి బదులుగా ఆ బాణం ఒక చివరి నుంచి మరో చివరి వరకు ప్రతి బిందువు గుండా వెళ్లే మార్గం కోసం వెతకండి.
2. ప్రతి బాణాన్ని 1/50 సంభావ్యతతో యాదృచ్ఛికంగా తొలగించండి.
3. ప్రతి బిందువు వద్ద లోపలికి వచ్చే బాణాల మూడు సమూహాలను సృష్టించి, మిగిలిన ప్రతి బాణాన్ని సమూహాల యొక్క యాదృచ్ఛిక, ఖాళీ కాని సమితిలోకి నకలు చేయండి.
4. పర్యటన ఉంటే, కనీసం (49/50)ⁿ⁻¹ సంభావ్యతతో ప్రతి బిందువుకు ఒక సమూహాన్ని ఎంచుకుని, చెల్లుబాటు అయ్యే మార్గాల సంఖ్యను బేసిగా చేయవచ్చు.
5. ప్రతి బాణానికి కాకుండా, ప్రతి సమూహానికి యాదృచ్ఛిక భారం ఇవ్వండి. ఇప్పుడు వేరుచేత కిటుకు పనిచేస్తుంది, సుమారు (50/49)ⁿ పునరావృతాలు సరిపోతాయి.
6. ప్రతి పునరావృతం, బ్యోర్క్‌లుండ్, కాస్కి, కౌటిస్‌ల మాత్రికా నిర్ధారకాల మొత్తాలను, అరవింద్, గురుస్వామి కూడా ఉపయోగించిన యాదృచ్ఛిక “రేఖీకరణ”ను వాడి, ప్రతి మొత్తం భారం వద్ద బేసి-సరి లెక్కలను (15/8)ⁿ కాలంలో లెక్కిస్తుంది.

రెండింటినీ గుణించండి: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.

యంత్రం సృష్టించిన నిరూపణ

పత్రం చివర్లో జనరేటివ్ AI గురించి ఒక ప్రకటన ఉంది: ప్రధాన సిద్ధాంతం యొక్క నిరూపణను ChatGPT 6 Astra సృష్టించింది, వ్రాతప్రతిని తయారు చేయడంలోనూ సహాయపడింది. రచయితలు మధ్యంతర ప్రతిపాదనల ప్రకటనలను అందించారు — అవి నమూనా యొక్క అసలు పరిష్కారానికి సంయోజనాత్మక వివరణను ఇస్తాయి — ఆ తర్వాత అన్నింటినీ తనిఖీ చేసి, సవరించి, పూర్తి బాధ్యత తీసుకున్నారు.

ఈ ఫలితం సైద్ధాంతికమైనది — ఏ ప్రోగ్రామూ నడపలేదు — అల్గారిథం యాదృచ్ఛికమైనది, రెండు వైపులా పొరపాటు జరిగే చిన్న అవకాశం ఉంది. ఒకవైపు వీధులకు 1.9133, రెండువైపుల వీధులకు 1.657 — వీటి మధ్య ఇంకా విశాలమైన అంతరం తెరిచే ఉంది.