కంప్యూటింగ్ & ఏఐప్రీప్రింట్సిద్ధాంతంచదవడానికి 3 నిమిషాలు

కొన్ని పోలికలు నిషిద్ధమైనా, దాదాపు అంతే వేగంగా క్రమీకరణ

n అంశాలను రెండేసి చొప్పున పోలుస్తూ క్రమంలో పెట్టడానికి, సుమారు n log n పోలికలు అవసరం, అవి సరిపోతాయి కూడా. కానీ అది ఏ రెండు అంశాలనైనా పోల్చవచ్చని ఊహిస్తుంది.

తరచుగా అది సాధ్యం కాదు. రచయితలు 2011 నాటి ఒక పరిశోధనా పత్రం నుంచి ఒక ఉదాహరణను తీసుకుంటారు: అనేక మంది అభ్యర్థులు ఒకే ఉద్యోగానికి దరఖాస్తు చేస్తారు, ప్రతి ఒక్కరికీ సిఫారసుదారులు ఉంటారు. ఏదో ఒక సిఫారసుదారుకు ఇద్దరు అభ్యర్థులూ తెలిసి ఉంటేనే వారిని పోల్చగలం. అనుమతించిన పోలికలు ఒక జాలాన్ని (network), ఒక గ్రాఫ్‌ను (graph) ఏర్పరుస్తాయి: ప్రతి అంశం ఒక బిందువు, అనుమతించిన ప్రతి పోలిక ఒక లంకె. నిజమైన క్రమం దాగి ఉంటుంది, కానీ గ్రాఫ్‌లో అది తప్పకుండా ఉంటుంది, ప్రతి అంశాన్ని తర్వాతి దానితో కలిపే ఒక మార్గంగా. ప్రశ్న: ఆ క్రమాన్ని తిరిగి పొందడానికి ఎన్ని పోలికలు పడతాయి? ఇదే సాధారణీకృత క్రమీకరణ (generalized sorting).

సాధారణ ఉపాయాలు ఎందుకు విఫలమవుతాయి

సంప్రదాయ అల్గారిథమ్‌లు ఎంపిక స్వేచ్ఛపై ఆధారపడతాయి. QuickSort ఒక “పివట్‌ను” (pivot) ఎంచుకుని దాన్ని చాలా ఇతర అంశాలతో పోలుస్తుంది, కానీ ఏదో ఒక సాధారణ (arbitrary) గ్రాఫ్‌లో చాలా ఇతర అంశాలతో అనుసంధానమైన అంశం ఏదీ ఉండకపోవచ్చు. MergeSort అంశాలను సమూహాలుగా విభజించి ప్రతి దాన్నీ క్రమీకరిస్తుంది, కానీ ఒక సమూహాన్ని దానికదే క్రమీకరించడం సాధ్యం కాకపోవచ్చు: తుది క్రమంలో పొరుగున ఉండే రెండు అంశాలు ఆ సమూహంలో అనుసంధానమై ఉండాల్సిన అవసరం లేదు. మరింత ప్రాథమికంగా, సాధారణ క్రమీకరణలో, సాధ్యమయ్యే క్రమాల్లో గణనీయమైన భాగాన్ని తోసిపుచ్చే ఒక పోలిక ఎల్లప్పుడూ అందుబాటులో ఉంటుంది; పరిమిత పోలికలతో, అలాంటిది ఏదీ ఉండకపోవచ్చు.

పురోగతి నెమ్మదిగా సాగింది. 2011లో, జీయీ హువాంగ్ (Zhiyi Huang), సంపత్ కన్నన్ (Sampath Kannan), సంజీవ్ ఖన్నా (Sanjeev Khanna) సుమారు n¹·⁵ పోలికలు — లాగరిథమిక్ కారకాల వరకు — వాడే ఒక పద్ధతిని కనుగొన్నారు, అప్పటి నుంచి ఏ గ్రాఫ్‌కైనా ఆ హద్దే నిలిచింది. ఈ సమస్య సాధారణ క్రమీకరణ కంటే ప్రాథమికంగా కష్టమైనదేమో, 1 కంటే ఎక్కువ ఘాతానికి పెంచిన n అవసరమవుతుందేమో అని కూడా వారు అడిగారు.

ముందు ఊహించు, తర్వాత సరిచేయి

న్యూయార్క్ విశ్వవిద్యాలయానికి చెందిన సంజీవ్ ఖన్నా, హార్వర్డ్ విశ్వవిద్యాలయానికి చెందిన ఆరన్ పుటర్‌మన్ (Aaron Putterman), న్యూయార్క్ విశ్వవిద్యాలయానికే చెందిన జున్‌కై సాంగ్ (Junkai Song) ఇప్పుడు ఆ ప్రశ్నకు సమాధానం ఇస్తున్నారు: కాదు. వారి యాదృచ్ఛిక (randomised) అల్గారిథమ్ ఏ గ్రాఫ్‌పైనైనా సగటున సుమారు n log⁴ n పోలికలతో క్రమీకరిస్తుంది — సాధారణ క్రమీకరణ కంటే కొన్ని లాగరిథమిక్ కారకాలు మాత్రమే ఎక్కువ. అంతేకాదు, అది “సాపేక్షంగా సరళమైనది” అని వారు రాశారు. అయితే, ఈ లాభం సైద్ధాంతికమైనది: నిరూపణలోని స్థిరాంకాలు అపారమైనవి (2³² వంటి కారకాలు), కాబట్టి n చాలా పెద్దదైనప్పుడు మాత్రమే ఆధిక్యం కనిపిస్తుంది.

ఇది తెలిసిన ఒక ఫలితంపై ఆధారపడుతుంది: ఎవరైనా మీకు ప్రతి లంకె దిశ గురించి ఒక ఊహను ఇస్తే, అది w లంకెలపై తప్పైతే, సుమారు n log n + w పోలికలతో క్రమాన్ని తిరిగి పొందవచ్చు. కాబట్టి పని ఇలా మారుతుంది: కొన్ని పోలికలతోనే, కొన్ని తప్పులు మాత్రమే ఉన్న ఒక ఊహను తయారుచేయడం. కీలక దశలు:

  • ఒక స్థూలమైన మొదటి ఊహ. అనుసంధానమైన జతల నుంచి ఒక యాదృచ్ఛిక నమూనాను పోల్చి, సమాధానాలకు అనుగుణంగా ఉండే ఏదో ఒక క్రమాన్ని ఎంచుకోవాలి. దానిలో చాలా తప్పులు ఉంటాయి, కానీ మరీ ఎక్కువ కాదు.
  • తప్పులను సరిచేయడం కాదు, వేరుచేయడం. తప్పుడు ఊహలను సరిదిద్దే బదులు, అల్గారిథమ్ సగటు కంటే తప్పులు దట్టంగా ఉన్న గ్రాఫ్ భాగాలను కనుగొని వాటిని పక్కన పెడుతుంది. ప్రతి రౌండ్ మిగిలిన తప్పులను, అంచనా విలువ (expectation) పరంగా, నాలుగో వంతుకు తగ్గిస్తుంది.
  • తర్వాత తిరిగి రావడం. పక్కన పెట్టిన లంకెలను తర్వాతి దశలో పరిష్కరిస్తారు. ప్రతి దశ ఇంకా మిగిలి ఉన్న లంకెలలో కనీసం సగాన్ని తేలుస్తుంది, కాబట్టి ఒక మిలియన్ లంకెలకు సుమారు ఇరవై దశలు సరిపోతాయి.

యంత్రాలతో కనుగొన్న ఒక నిరూపణ

పరిశోధనా పత్రంలోని AI వెల్లడి అసాధారణంగా వివరంగా ఉంది. ChatGPT 6-Astra “మెరుగైన హద్దులను నిరూపించడంలో అనివార్యమైనది” అని అది పేర్కొంటుంది. ఒక మోడల్ మొదట సుమారు n¹·³³ పోలికలు వాడే ఒక అల్గారిథమ్‌ను కనుగొంది, తర్వాత నిలిచిపోయింది. రచయితలు దాన్ని n¹·² వరకు తీసుకెళ్లారు; తర్వాత, అనేక వారాల పాటు డజన్ల కొద్దీ సార్లు ప్రాంప్ట్ చేసినప్పుడు, మోడళ్లు వరుస మెరుగుదలలను కనుగొన్నాయి — n^(10/9), n^(17/16), n^(19/18) — చివరకు దాదాపు-రేఖీయ (near-linear) అల్గారిథమ్‌ను చేరుకున్నాయి. ఆ తుది ఆవిష్కరణకు తమ సొంత మధ్యంతర దశ అనివార్యమైనదా అనేది స్పష్టంగా లేదని రచయితలు జోడిస్తారు.

ఇంకా తెరిచి ఉన్న ప్రశ్నలు

ఫలితం పోలికలను లెక్కిస్తుంది, గణన సమయాన్ని కాదు: ప్రస్తుత రూపంలో, అల్గారిథమ్ బహుపది సమయంలో (polynomial time) నడవదు, 2011 పద్ధతి మాత్రం నడిచేది. రచయితలు మూడు తెరిచి ఉన్న ప్రశ్నలను పేర్కొంటారు: మిగిలిన లాగరిథమిక్ కారకాలను తొలగించగలమా, యాదృచ్ఛికత లేని అల్గారిథమ్ అంతే బాగా చేయగలదా, ఒక సమర్థవంతమైన అల్గారిథమ్ అదే సంఖ్యలో పోలికలను చేరుకోగలదా — లేదా కనీసం n¹·⁵ ను అధిగమించగలదా.