40 సంవత్సరాల తర్వాత క్లీక్లను కనుగొనే వేగ పరిమితి కూలింది
n మంది వ్యక్తులు గల ఒక సామాజిక జాలాన్ని (social network) ఊహించుకోండి. వారిలో అందరూ ఒకరికొకరు తెలిసిన k మంది గల సమూహం ఏదైనా ఉందా? కంప్యూటర్ శాస్త్రవేత్తలు అలాంటి సమూహాన్ని k-క్లీక్ (k-clique) అంటారు, దాన్ని కనుగొనడం లెక్కలేనన్ని అనువర్తనాలు గల ఒక సంప్రదాయ సమస్య. అమాయకమైన (naive) విధానం k మంది వ్యక్తుల సాధ్యమయ్యే ప్రతి సమూహాన్నీ తనిఖీ చేస్తుంది, అవి సుమారు n^k ఉంటాయి — పెద్ద జాలాలకు ఇది నిష్ఫలం.
1985 నాటి ఒక ఉపాయం, ఒక సుదీర్ఘ సవాలు
40 కంటే ఎక్కువ సంవత్సరాల క్రితం, యారోస్లావ్ నెషెత్రిల్ (Jaroslav Nešetřil), స్వాటోప్లుక్ పోల్యాక్ (Svatopluk Poljak) ఒక దగ్గరి దారిని కనుగొన్నారు. వారు k-క్లీక్ కోసం వెతుకులాటను ఒక పెద్ద గ్రాఫ్లో త్రిభుజం కోసం వెతుకులాటగా మార్చారు, దాన్ని క్రమంగా మాత్రికలను గుణించడం (multiplying matrices) ద్వారా — అంటే సంఖ్యల పెద్ద పట్టికలను — చేయవచ్చు. ఖర్చు మాత్రికా గుణకారపు ఘాతాంకం ω పై ఆధారపడి ఉంటుంది: వారి పద్ధతికి సుమారు n^(ωk/3) అడుగులు పడతాయి. ω ఖచ్చితంగా ఎంతో ఎవరికీ తెలియదు. అది కనీసం 2, పరిశోధనా పత్రం ఇటీవలి ఒక ఎగువ హద్దుగా 9/4 ను ఉదహరిస్తుంది.
1985 నాటి ఆ పద్ధతి యొక్క ఘాతాంకాన్ని ఎప్పుడూ ఎవరూ అధిగమించలేదు. 2004లో, ఏదో ఒక స్థిరమైన k కోసం ఇంకా మెరుగ్గా చేయమని గెర్హార్డ్ వోగింగర్ (Gerhard Woeginger) పరిశోధకులకు సవాలు విసిరారు; రెండు దశాబ్దాలకు పైగా గడిచిపోయాయి. ఈలోగా k-క్లీక్ పరికల్పన (k-Clique Hypothesis) — n^(ωk/3) దాదాపుగా సాధ్యమైనంత ఉత్తమమైనదనేది — “సూక్ష్మ-స్థాయి సంక్లిష్టత” (fine-grained complexity) కు ఒక పునాదిగా మారింది. వ్యాకరణాలను పార్స్ చేయడం (parsing) నుంచి సంపీడిత (compressed) డేటాను విశ్లేషించడం వరకు, అనేక ఇతర సమస్యలను కూడా ఇంకా వేగంగా పరిష్కరించలేమని వాదించడానికి పరిశోధకులు దాన్ని ఉపయోగించారు.
కదిలే లక్ష్యం
ఈ పరికల్పనను ఖండించడంలో ఒక ప్రత్యేక కష్టం ఉంది. దాని అంచనా వేసిన ఖర్చు ω పై ఆధారపడి ఉంటుంది, అది తెలియదు. ఈరోజు తెలిసిన ω యొక్క ఉత్తమ విలువను అధిగమించే ఒక అల్గారిథమ్, తర్వాత ఎవరైనా ఇంకా వేగవంతమైన మాత్రికా గుణకారాన్ని కనుగొంటే, పరికల్పనను అధిగమించడం మానేయవచ్చు.
MITకి చెందిన వర్జీనియా వసిలెవ్స్కా విలియమ్స్ (Virginia Vassilevska Williams), టెల్ అవీవ్ విశ్వవిద్యాలయానికి చెందిన ఓర్ జమీర్ (Or Zamir) ఈ సమస్యను పక్కదారిన దాటుతారు. తగినంత పెద్ద ప్రతి k కోసం, ఒక k-క్లీక్ను సుమారు n^((ω/3 − c)k) అడుగులలో కనుగొనవచ్చని — లెక్కించవచ్చు కూడా — వారు నిరూపిస్తారు, ఇక్కడ c అనేది k పై గానీ ω పై గానీ ఆధారపడని ఒక ధన స్థిరాంకం. ఈ ఆదా ω యొక్క నిజమైన విలువతో — అది ఏదైనా కావచ్చు — పోల్చి కొలవబడుతుంది. ω = 2 అయినా, ఊహించదగిన ఉత్తమ సందర్భంలో కూడా, అది నిలుస్తుంది.
ఒక చీలికను మడవడం
పద్ధతి యొక్క హృదయం తొమ్మిది శీర్షాల (vertices) నమూనాలకు సంబంధించినది. ప్రామాణిక విధానం వాటిని మూడేసి చొప్పున మూడు సమూహాలుగా విభజించి మూడు భారీ మాత్రికలను గుణిస్తుంది. రచయితలు ఒక చీలికను (wedge) — ఒక శీర్షాన్ని పంచుకునే రెండు అంచులు (edges) — పరిశీలించి, రెండు మాత్రికల మధ్య ఏమీ మార్చని ఒక పట్టికను చొప్పిస్తారు: తత్సమ మాత్రిక (identity). తర్వాత ఆ తత్సమ మాత్రికను కొన్ని “మార్పిడుల” (swaps) మొత్తంగా రాస్తారు — వాటిలో ప్రతి ఒక్కటీ చీలిక యొక్క రెండు అంచులను ఒకటిగా కలుపుతుంది — దానికి తోడు తక్కువ ర్యాంక్ (low rank) గల ఒక శేషం.
మార్పిడులు తక్కువ అంచులు గల సరళమైన నమూనాలను ఇస్తాయి, వాటిని మళ్లీ అదే పద్ధతితో నిర్వహిస్తారు; తొమ్మిది శీర్షాల నమూనాకు గరిష్ఠంగా 36 అంచులు ఉంటాయి, కాబట్టి పునరావృతం (recursion) ముగుస్తుంది. తక్కువ-ర్యాంక్ శేషం గుణించాల్సిన మాత్రికలను కుదిస్తుంది. ఈ ఉపాయాన్ని రెండు వేర్వేరు చీలికలకు ఒకేసారి వర్తింపజేయడమే ω = 2 అయినప్పుడు కూడా లాభాన్ని నిలిపి ఉంచుతుంది. తొమ్మిదికి గుణిజమైన ఏ k నైనా తర్వాత తొమ్మిది బ్లాకులుగా విభజించవచ్చు.
నిజమైనది, కానీ అతి చిన్నది
రచయితలు లాభానికి సంఖ్యలను ఇవ్వరు. స్థిరాంకాలు “ఆప్టిమైజేషన్ లేకుండా అతి సూక్ష్మం నుంచి గణనీయమైన ఆప్టిమైజేషన్లతో చిన్నది వరకు” ఉంటాయని వారు వర్ణిస్తారు. ఇక్కడ విషయం ఆచరణలో వేగం కాదు: దశాబ్దాలుగా నమ్మిన ఒక అవరోధం అసలు ఉనికిలోనే లేదనేది.
పర్యవసానాలు క్లీక్లను దాటి విస్తరిస్తాయి. n చరరాశులకు సుమారు 2^(ωn/3) అడుగులలో నడిచిన, Max-Cut, Max-2-SAT వంటి కఠినమైన ఆప్టిమైజేషన్ సమస్యల ఖచ్చితమైన అల్గారిథమ్లు కూడా ఇప్పుడు చిన్న ఘాతాంకాన్ని పొందుతాయి. ఏదైనా స్థిరమైన చిన్న గ్రాఫ్ ప్రతులను లెక్కించడానికి కూడా అదే వర్తిస్తుంది.
AI ఏమి చేసింది
ఒక ప్రత్యేక విభాగంలో, రచయితలు ChatGPT-6తో — దాని పబ్లిక్ వెబ్ ఇంటర్ఫేస్ ద్వారా ఉపయోగించి — ఎలా పనిచేశారో వర్ణిస్తారు. ఐదుగురు వ్యక్తుల క్లీక్ల కోసం తమ సొంత ఆలోచనల నుంచి, మరో ఊహను — ఘాతాంక సమయ పరికల్పనను (Exponential Time Hypothesis) — ఖండించిన OpenAI యొక్క ఇటీవలి ఒక ఫలితం నుంచి మొదలుపెట్టి, ఆ మోడల్ 5-క్లీక్లకు ఒక మొదటి, సంక్లిష్టమైన మెరుగుదలను కనుగొంది. ఆ తర్వాత రచయితలు, AI సహాయంతో, దాన్ని నిరూపణ యొక్క కేంద్రంలో ఉన్న బీజగణిత విభజనగా (algebraic decomposition) సారాంశీకరించారు, దాన్ని వారు “దాదాపు పూర్తిగా AI యొక్క సహకారం”గా భావిస్తారు. దాని చుట్టూ నిర్మించిన అల్గారిథమిక్ చట్రం ప్రధానంగా తమదేనని వారు చెబుతారు.
ఒక వ్యాఖ్య ప్రత్యేకంగా నిలుస్తుంది. AI సృష్టించిన అస్పష్టమైన నిరూపణలను మనుషులు చదవడం కష్టమని రచయితలు గమనిస్తారు — వారు “అవి స్వయంగా AIకి కూడా అర్థం చేసుకోవడం కష్టమని చూసి ఆశ్చర్యపోయారు”.
