EITC/IS/CCTF కంప్యూటేషనల్ కాంప్లెక్సిటీ థియరీ ఫండమెంటల్స్ అనేది కంప్యూటర్ సైన్స్ యొక్క పునాదుల యొక్క సైద్ధాంతిక అంశాలపై యూరోపియన్ IT సర్టిఫికేషన్ ప్రోగ్రామ్, ఇది ఇంటర్నెట్లో ఎక్కువగా ఉపయోగించే క్లాసికల్ అసమాన పబ్లిక్-కీ క్రిప్టోగ్రఫీకి కూడా ఆధారం.
EITC/IS/CCTF కంప్యూటేషనల్ కాంప్లెక్సిటీ థియరీ ఫండమెంటల్స్ యొక్క పాఠ్యాంశాలు కంప్యూటర్ సైన్స్ యొక్క పునాదులపై సైద్ధాంతిక పరిజ్ఞానాన్ని కలిగి ఉంటాయి మరియు నిర్ణయాత్మక మరియు నాన్డెటర్మినిస్టిక్ పరిమిత రాష్ట్ర యంత్రాలు, సాధారణ భాషలు, సందర్భ రహిత గ్రామర్లు మరియు భాషల సిద్ధాంతం, ఆటోమాటా థియరీ, ట్యూరింగ్ వంటి ప్రాథమిక భావనలపై గణన నమూనాలు ఉంటాయి. ఈ EITC సర్టిఫికేషన్కు సూచనగా సమగ్ర వీడియో సందేశాత్మక కంటెంట్ని కలిగి ఉన్న మెషీన్లు, సమస్యల నిర్ధారణ, పునరావృతం, తర్కం మరియు అల్గారిథమిక్ల సంక్లిష్టత క్రింది నిర్మాణంలో ప్రాథమిక భద్రతా అనువర్తనాల కోసం.
అల్గారిథమ్ యొక్క గణన సంక్లిష్టత అనేది దానిని ఆపరేట్ చేయడానికి అవసరమైన వనరుల మొత్తం. సమయం మరియు జ్ఞాపకశక్తి వనరులకు ప్రత్యేక శ్రద్ధ ఇవ్వబడుతుంది. సమస్య యొక్క సంక్లిష్టత దానిని పరిష్కరించడానికి ఉత్తమమైన అల్గారిథమ్ల సంక్లిష్టతగా నిర్వచించబడింది. అల్గారిథమ్ల విశ్లేషణ అనేది స్పష్టంగా ఇవ్వబడిన అల్గారిథమ్ల సంక్లిష్టత యొక్క అధ్యయనం, అయితే గణన సంక్లిష్టత సిద్ధాంతం అనేది బాగా తెలిసిన అల్గారిథమ్లతో సమస్యల పరిష్కారాల సంక్లిష్టతను అధ్యయనం చేస్తుంది. రెండు డొమైన్లు ఒకదానితో ఒకటి ముడిపడి ఉన్నాయి, ఎందుకంటే అల్గారిథమ్ యొక్క సంక్లిష్టత అది పరిష్కరించే సమస్య యొక్క సంక్లిష్టతపై ఎల్లప్పుడూ ఎగువ పరిమితిగా ఉంటుంది. ఇంకా, సమర్థవంతమైన అల్గారిథమ్లను నిర్మించేటప్పుడు పరిష్కరించాల్సిన సమస్య యొక్క సంక్లిష్టతతో నిర్దిష్ట అల్గారిథమ్ యొక్క సంక్లిష్టతను పోల్చడం తరచుగా అవసరం. చాలా సందర్భాలలో, సమస్య యొక్క క్లిష్టతకు సంబంధించి అందుబాటులో ఉన్న ఏకైక సమాచారం ఏమిటంటే ఇది అత్యంత సమర్థవంతమైన తెలిసిన సాంకేతికతల సంక్లిష్టత కంటే తక్కువగా ఉంటుంది. ఫలితంగా, అల్గోరిథం విశ్లేషణ మరియు సంక్లిష్టత సిద్ధాంతం మధ్య చాలా అతివ్యాప్తి ఉంది.
సంక్లిష్టత సిద్ధాంతం కంప్యూటర్ సైన్స్కు ప్రాతిపదికగా గణన నమూనాల పునాదులలో మాత్రమే కాకుండా ఆధునిక నెట్వర్క్లలో, ప్రత్యేకించి ఇంటర్నెట్లో విస్తృతంగా వ్యాపించే క్లాసికల్ అసిమెట్రిక్ క్రిప్టోగ్రఫీ (పబ్లిక్-కీ క్రిప్టోగ్రఫీ అని పిలుస్తారు) యొక్క పునాదులలో కూడా ముఖ్యమైనది. పబ్లిక్-కీ ఎన్క్రిప్షన్ అనేది నిర్దిష్ట అసమాన గణిత సమస్యల యొక్క గణన కష్టాలపై ఆధారపడి ఉంటుంది, ఉదాహరణకు పెద్ద సంఖ్యలను దాని ప్రధాన కారకాల్లోకి కారకం చేయడం (ఈ ఆపరేషన్ సంక్లిష్టత సిద్ధాంత వర్గీకరణలో ఒక కఠినమైన సమస్య, ఎందుకంటే పరిష్కరించడానికి సమర్థవంతమైన క్లాసికల్ అల్గారిథమ్లు లేవు. ఇది సమస్య యొక్క ఇన్పుట్ పరిమాణం పెరుగుదలతో విపరీతంగా కాకుండా బహుపదంగా స్కేలింగ్ చేయబడే వనరులతో, ఇది అసలైన పెద్ద సంఖ్యను ఇవ్వడానికి తెలిసిన ప్రధాన కారకాలకు గుణించడం యొక్క చాలా సులభమైన రివర్స్ ఆపరేషన్కు విరుద్ధంగా ఉంటుంది). పబ్లిక్-కీ క్రిప్టోగ్రఫీ ఆర్కిటెక్చర్లో ఈ అసమానతను ఉపయోగించడం (పబ్లిక్ కీ మధ్య గణనపరంగా అసమాన సంబంధాన్ని నిర్వచించడం ద్వారా, అది ప్రైవేట్ కీ నుండి సులభంగా గణించబడుతుంది, అయితే ప్రైవేట్ కీ పబ్లిక్ కీ నుండి సులభంగా కంప్యూటర్గా మారదు, పబ్లిక్గా పబ్లిక్ కీని ప్రకటించండి మరియు డేటా యొక్క అసమాన ఎన్క్రిప్షన్ కోసం ఇతర కమ్యూనికేషన్ సైడ్లను ఉపయోగించడాన్ని ప్రారంభించండి, ఇది కపుల్డ్ ప్రైవేట్ కీతో మాత్రమే డీక్రిప్ట్ చేయబడుతుంది, మూడవ పక్షాలకు గణనపరంగా అందుబాటులో ఉండదు, తద్వారా కమ్యూనికేషన్ సురక్షితంగా ఉంటుంది).
గణన సంక్లిష్టత సిద్ధాంతం ప్రధానంగా కంప్యూటర్ సైన్స్ మరియు అల్గారిథమిక్స్ మార్గదర్శకుల విజయాలపై అభివృద్ధి చేయబడింది, అలాన్ ట్యూరింగ్ వంటి వారి పని, నాజీ జర్మనీ యొక్క ఎనిగ్మా సాంకేతికలిపిని విచ్ఛిన్నం చేయడంలో కీలకమైనది, ఇది రెండవ ప్రపంచ యుద్ధంలో మిత్రపక్షాలు గెలుపొందడంలో తీవ్ర పాత్ర పోషించింది. దాచిన సమాచారాన్ని వెలికితీసేందుకు డేటాను (ప్రధానంగా ఎన్క్రిప్టెడ్ కమ్యూనికేషన్) విశ్లేషించే గణన ప్రక్రియలను రూపొందించడం మరియు స్వయంచాలకంగా మార్చడం లక్ష్యంగా క్రిప్టానాలసిస్ క్రిప్టోగ్రాఫిక్ సిస్టమ్లను ఉల్లంఘించడానికి మరియు సాధారణంగా వ్యూహాత్మక సైనిక ప్రాముఖ్యత కలిగిన ఎన్క్రిప్టెడ్ కమ్యూనికేషన్లోని కంటెంట్లను యాక్సెస్ చేయడానికి ఉపయోగించబడింది. ఇది క్రిప్టానాలసిస్, ఇది మొదటి ఆధునిక కంప్యూటర్ల అభివృద్ధిని ఉత్ప్రేరకపరిచింది (ఇవి మొదట్లో కోడ్బ్రేకింగ్ యొక్క వ్యూహాత్మక లక్ష్యానికి వర్తింపజేయబడ్డాయి). బ్రిటిష్ కొలోసస్ (మొదటి ఆధునిక ఎలక్ట్రానిక్ మరియు ప్రోగ్రామ్ కంప్యూటర్గా పరిగణించబడుతుంది) ముందు పోలిష్ "బాంబ్" ఉంది, ఇది ఎనిగ్మా సైఫర్లను విచ్ఛిన్నం చేయడంలో సహాయపడటానికి మరియన్ రెజెవ్స్కీ రూపొందించిన ఎలక్ట్రానిక్ గణన పరికరం మరియు పోలిష్ ఇంటెలిజెన్స్ ద్వారా గ్రేట్ బ్రిటన్కు అప్పగించబడింది. 1939లో పోలాండ్ జర్మనీచే ఆక్రమించబడిన తర్వాత స్వాధీనం చేసుకున్న జర్మన్ ఎనిగ్మా ఎన్క్రిప్షన్ మెషీన్. ఈ పరికరం ఆధారంగా అలాన్ ట్యూరింగ్ జర్మన్ ఎన్క్రిప్టెడ్ కమ్యూనికేషన్ను విజయవంతంగా విచ్ఛిన్నం చేయడానికి దాని మరింత అధునాతన ప్రతిరూపాన్ని అభివృద్ధి చేసింది, ఇది తరువాత ఆధునిక కంప్యూటర్లుగా అభివృద్ధి చేయబడింది.
అల్గారిథమ్ను అమలు చేయడానికి అవసరమైన వనరుల మొత్తం ఇన్పుట్ పరిమాణంతో మారుతూ ఉంటుంది కాబట్టి, సంక్లిష్టత సాధారణంగా f(n) ఫంక్షన్గా వ్యక్తీకరించబడుతుంది, ఇక్కడ n అనేది ఇన్పుట్ పరిమాణం మరియు f(n) అనేది చెత్త-కేస్ సంక్లిష్టత ( పరిమాణం n యొక్క అన్ని ఇన్పుట్లలో అవసరమైన గరిష్ట వనరుల మొత్తం) లేదా సగటు-కేస్ సంక్లిష్టత (n పరిమాణంలోని అన్ని ఇన్పుట్లపై వనరుల మొత్తం సగటు). పరిమాణం n యొక్క ఇన్పుట్పై అవసరమైన ప్రాథమిక కార్యకలాపాల సంఖ్య సాధారణంగా సమయ సంక్లిష్టతగా పేర్కొనబడుతుంది, ఇక్కడ ప్రాథమిక కార్యకలాపాలు నిర్దిష్ట కంప్యూటర్లో స్థిరమైన సమయాన్ని తీసుకుంటాయని మరియు వేరొక మెషీన్లో అమలు చేసినప్పుడు స్థిరమైన కారకం ద్వారా మాత్రమే మారుతుందని నమ్ముతారు. పరిమాణం n ఇన్పుట్పై అల్గారిథమ్కి అవసరమైన మెమరీ మొత్తాన్ని స్పేస్ కాంప్లెక్సిటీ అంటారు.
సమయం అనేది సాధారణంగా పరిగణించబడే వనరు. "సంక్లిష్టత" అనే పదాన్ని క్వాలిఫైయర్ లేకుండా ఉపయోగించినప్పుడు, ఇది సాధారణంగా సమయం యొక్క సంక్లిష్టతను సూచిస్తుంది.
సమయం యొక్క సాంప్రదాయ యూనిట్లు (సెకన్లు, నిమిషాలు మరియు మొదలైనవి) సంక్లిష్టత సిద్ధాంతంలో ఉపయోగించబడవు ఎందుకంటే అవి ఎంచుకున్న కంప్యూటర్ మరియు సాంకేతికత యొక్క పురోగతిపై చాలా ఆధారపడతాయి. ఉదాహరణకు, ఈరోజు కంప్యూటర్ 1960ల నుండి కంప్యూటర్ కంటే చాలా వేగంగా అల్గారిథమ్ని అమలు చేయగలదు, అయినప్పటికీ, ఇది అల్గారిథమ్ యొక్క స్వాభావిక నాణ్యత కంటే కంప్యూటర్ హార్డ్వేర్లో సాంకేతిక పురోగతుల కారణంగా జరిగింది. సంక్లిష్టత సిద్ధాంతం యొక్క లక్ష్యం అల్గారిథమ్ల యొక్క స్వాభావిక సమయ అవసరాలను లేదా అల్గారిథమ్ ఏదైనా కంప్యూటర్పై విధించే ప్రాథమిక సమయ పరిమితులను లెక్కించడం. గణన సమయంలో ఎన్ని ప్రాథమిక కార్యకలాపాలు నిర్వహించబడుతున్నాయో లెక్కించడం ద్వారా ఇది సాధించబడుతుంది. ఈ విధానాలను సాధారణంగా దశలుగా సూచిస్తారు, ఎందుకంటే అవి నిర్దిష్ట మెషీన్లో స్థిరమైన సమయాన్ని తీసుకుంటాయి (అనగా, ఇన్పుట్ మొత్తంతో అవి ప్రభావితం కావు).
అల్గారిథమ్లను నిర్వహించడానికి అవసరమైన కంప్యూటర్ మెమరీ మొత్తం మరొక కీలకమైన వనరు.
మరొక తరచుగా ఉపయోగించే వనరు అంకగణిత కార్యకలాపాల మొత్తం. ఈ దృష్టాంతంలో, "అంకగణిత సంక్లిష్టత" అనే పదం ఉపయోగించబడుతుంది. గణన సమయంలో సంభవించే సంఖ్యల బైనరీ ప్రాతినిధ్య పరిమాణంపై ఎగువ పరిమితి తెలిసినట్లయితే, సమయ సంక్లిష్టత అనేది స్థిరమైన కారకం ద్వారా అంకగణిత సంక్లిష్టత యొక్క ఉత్పత్తి.
గణన సమయంలో ఉపయోగించే పూర్ణాంకాల పరిమాణం అనేక పద్ధతులకు పరిమితం కాదు మరియు అంకగణిత కార్యకలాపాలకు నిర్ణీత సమయం అవసరమని భావించడం అవాస్తవం. ఫలితంగా, బిట్ సంక్లిష్టత అని కూడా పిలువబడే సమయ సంక్లిష్టత, అంకగణిత సంక్లిష్టత కంటే గణనీయంగా ఎక్కువగా ఉండవచ్చు. ఒక nn పూర్ణాంక మాతృక యొక్క డిటర్మినెంట్ని గణించడంలో అంకగణిత కష్టం, ఉదాహరణకు, ప్రామాణిక సాంకేతికతలకు (గాస్సియన్ ఎలిమినేషన్) O(n^3). గణన సమయంలో గుణకాల పరిమాణం విపరీతంగా విస్తరించవచ్చు కాబట్టి, అదే పద్ధతుల యొక్క బిట్ సంక్లిష్టత nలో ఘాతాంకంగా ఉంటుంది. ఈ సాంకేతికతలను బహుళ-మాడ్యులర్ అంకగణితంతో కలిపి ఉపయోగించినట్లయితే, బిట్ సంక్లిష్టతను O(n^4)కి తగ్గించవచ్చు.
బిట్ సంక్లిష్టత, అధికారిక పరంగా, అల్గారిథమ్ను అమలు చేయడానికి అవసరమైన బిట్లపై ఆపరేషన్ల సంఖ్యను సూచిస్తుంది. ఇది చాలా గణన నమూనాలలో స్థిరమైన కారకం వరకు తాత్కాలిక సంక్లిష్టతకు సమానం. కంప్యూటర్లకు అవసరమైన యంత్ర పదాలపై కార్యకలాపాల సంఖ్య బిట్ సంక్లిష్టతకు అనులోమానుపాతంలో ఉంటుంది. గణన యొక్క వాస్తవిక నమూనాల కోసం, సమయ సంక్లిష్టత మరియు బిట్ సంక్లిష్టత ఒకేలా ఉంటాయి.
క్రమబద్ధీకరించడం మరియు శోధించడంలో తరచుగా పరిగణించబడే వనరు ఎంట్రీల పోలికల మొత్తం. డేటా బాగా అమర్చబడి ఉంటే, ఇది సమయ సంక్లిష్టతకు మంచి సూచిక.
అన్ని సంభావ్య ఇన్పుట్లలో, అల్గోరిథంలో దశల సంఖ్యను లెక్కించడం అసాధ్యం. ఇన్పుట్ యొక్క సంక్లిష్టత దాని పరిమాణంతో పెరుగుతుంది కాబట్టి, ఇది సాధారణంగా ఇన్పుట్ పరిమాణం n (బిట్స్లో) యొక్క ఫంక్షన్గా సూచించబడుతుంది మరియు కాబట్టి సంక్లిష్టత n యొక్క ఫంక్షన్. అయితే, అదే-పరిమాణ ఇన్పుట్ల కోసం, అల్గోరిథం యొక్క సంక్లిష్టత గణనీయంగా మారవచ్చు. ఫలితంగా, వివిధ రకాల సంక్లిష్టత విధులు మామూలుగా ఉపయోగించబడతాయి.
చెత్త-కేస్ సంక్లిష్టత అనేది అన్ని పరిమాణం n ఇన్పుట్ల కోసం అన్ని సంక్లిష్టత యొక్క మొత్తం, అయితే సగటు-కేస్ సంక్లిష్టత అనేది అన్ని పరిమాణం n ఇన్పుట్ల కోసం మొత్తం సంక్లిష్టత యొక్క మొత్తం (ఇచ్చిన పరిమాణంలో సాధ్యమయ్యే ఇన్పుట్ల సంఖ్య కాబట్టి ఇది అర్ధమే. పరిమిత). "సంక్లిష్టత" అనే పదాన్ని మరింత నిర్వచించకుండా ఉపయోగించినప్పుడు, చెత్త సమయ సంక్లిష్టత పరిగణనలోకి తీసుకోబడుతుంది.
చెత్త-కేస్ మరియు సగటు-కేస్ సంక్లిష్టతను సరిగ్గా లెక్కించడం చాలా కష్టం. ఇంకా, ఈ ఖచ్చితమైన విలువలు తక్కువ ఆచరణాత్మక అనువర్తనాన్ని కలిగి ఉంటాయి ఎందుకంటే యంత్రం లేదా గణన నమూనాలో ఏదైనా మార్పు సంక్లిష్టతను కొద్దిగా మారుస్తుంది. ఇంకా, n యొక్క చిన్న విలువలకు వనరుల వినియోగం కీలకం కాదు, కాబట్టి చిన్న n కోసం తక్కువ సంక్లిష్టత కంటే అమలులో సౌలభ్యం తరచుగా ఆకర్షణీయంగా ఉంటుంది.
ఈ కారణాల వల్ల, అధిక n కోసం సంక్లిష్టత యొక్క ప్రవర్తనపై ఎక్కువ శ్రద్ధ చూపబడుతుంది, అంటే, n అనంతానికి చేరుకునేటప్పుడు దాని లక్షణం లేని ప్రవర్తన. ఫలితంగా, సంక్లిష్టతను సూచించడానికి పెద్ద O సంజ్ఞామానం సాధారణంగా ఉపయోగించబడుతుంది.
గణన నమూనాలు
గణన నమూనా ఎంపిక, ఇది సమయ యూనిట్లో నిర్వహించబడే ముఖ్యమైన కార్యకలాపాలను పేర్కొనడం, సంక్లిష్టతను నిర్ణయించడంలో కీలకమైనది. గణన నమూనా ప్రత్యేకంగా వివరించబడనప్పుడు దీనిని కొన్నిసార్లు మల్టీటేప్ ట్యూరింగ్ మెషీన్గా సూచిస్తారు.
గణన యొక్క నిర్ణయాత్మక నమూనా అనేది యంత్రం యొక్క తదుపరి స్థితులు మరియు నిర్వహించాల్సిన కార్యకలాపాలు పూర్తిగా మునుపటి స్థితిచే నిర్వచించబడతాయి. రికర్సివ్ ఫంక్షన్లు, లాంబ్డా కాలిక్యులస్ మరియు ట్యూరింగ్ మెషీన్లు మొదటి నిర్ణయాత్మక నమూనాలు. యాదృచ్ఛిక-యాక్సెస్ మెషీన్లు (దీనిని RAM-మెషీన్లు అని కూడా పిలుస్తారు) వాస్తవ-ప్రపంచ కంప్యూటర్లను అనుకరించడానికి ఒక ప్రసిద్ధ నమూనా.
గణన నమూనా నిర్వచించబడనప్పుడు, మల్టీటేప్ ట్యూరింగ్ మెషిన్ సాధారణంగా భావించబడుతుంది. మల్టీటేప్ ట్యూరింగ్ మెషీన్లలో, సమయ సంక్లిష్టత చాలా అల్గారిథమ్ల కోసం RAM మెషీన్ల మాదిరిగానే ఉంటుంది, అయితే ఈ సమానత్వాన్ని సాధించడానికి మెమరీలో డేటా ఎలా నిల్వ చేయబడుతుందనే దానిపై గణనీయమైన శ్రద్ధ అవసరం.
నాన్-డిటర్మినిస్టిక్ ట్యూరింగ్ మెషీన్ల వంటి నాన్-డిటర్మినిస్టిక్ మోడల్ కంప్యూటింగ్లో గణన యొక్క కొన్ని దశల్లో వివిధ ఎంపికలు చేయవచ్చు. సంక్లిష్టత సిద్ధాంతంలో, అన్ని సాధ్యమయ్యే ఎంపికలు ఒకే సమయంలో పరిగణించబడతాయి మరియు నిర్ణయాత్మక సమయ సంక్లిష్టత అనేది ఎల్లప్పుడూ ఉత్తమ ఎంపికలు చేసినప్పుడు అవసరమైన సమయం. మరో విధంగా చెప్పాలంటే, గణన అవసరమైనన్ని (ఒకేలా) ప్రాసెసర్లపై ఏకకాలంలో జరుగుతుంది మరియు గణనను పూర్తి చేయడానికి మొదటి ప్రాసెసర్కి పట్టే సమయం నాన్-డిటర్మినిస్టిక్ గణన సమయం. ఈ సమాంతరతను క్వాంటం కంప్యూటింగ్లో ప్రత్యేక క్వాంటం అల్గారిథమ్లను అమలు చేస్తున్నప్పుడు సూపర్పోజ్డ్ ఎంటాంగిల్డ్ స్టేట్లను ఉపయోగించడం ద్వారా ఉపయోగించవచ్చు, ఉదాహరణకు చిన్న పూర్ణాంకాల యొక్క షోర్ యొక్క కారకం.
అటువంటి గణన నమూనా ప్రస్తుతం ఆచరణ సాధ్యం కానప్పటికీ, ఇది సైద్ధాంతిక ప్రాముఖ్యతను కలిగి ఉంది, ముఖ్యంగా P = NP సమస్యకు సంబంధించి, ఇది "బహుపది సమయం" మరియు "నిర్ధారణ కాని బహుపది సమయం"ని ఉపయోగించి ఉత్పత్తి చేయబడిన సంక్లిష్టత తరగతులు అని అడుగుతుంది. హద్దులు ఒకే విధంగా ఉంటాయి. నిర్ణయాత్మక కంప్యూటర్లో, NP-అల్గారిథమ్ను అనుకరించడానికి “ఘాతాంక సమయం” అవసరం. నాన్-డిటర్మినిస్టిక్ సిస్టమ్లో ఒక పనిని బహుపది సమయంలో పరిష్కరించగలిగితే, అది NP కష్టతరమైన తరగతికి చెందినది. ఏదైనా సమస్య NPలో ఉంటే మరియు ఇతర NP సమస్య కంటే సులభంగా లేనట్లయితే, అది NP-పూర్తిగా చెప్పబడుతుంది. నాప్సాక్ సమస్య, ట్రావెలింగ్ సేల్స్మ్యాన్ సమస్య మరియు బూలియన్ సంతృప్తి సమస్య అన్నీ NP-పూర్తి కాంబినేటోరియల్ సమస్యలు. అత్యంత ప్రసిద్ధ అల్గోరిథం ఈ సమస్యలన్నింటికీ ఘాతాంక సంక్లిష్టతను కలిగి ఉంది. ఈ సమస్యలలో దేనినైనా నిర్ణయాత్మక యంత్రంలో బహుపది సమయంలో పరిష్కరించగలిగితే, అన్ని NP సమస్యలను బహుపది సమయంలో కూడా పరిష్కరించవచ్చు మరియు P = NP స్థాపించబడుతుంది. 2017 నాటికి, P NP, NP సమస్యల యొక్క అధ్వాన్నమైన పరిస్థితులను పరిష్కరించడానికి ప్రాథమికంగా కష్టతరమైనదని సూచిస్తుంది, అనగా, ఆసక్తికరమైన ఇన్పుట్ పొడవులు ఇచ్చిన ఏదైనా సాధ్యమయ్యే సమయ వ్యవధి (దశాబ్దాలు) కంటే చాలా ఎక్కువ సమయం పడుతుంది.
సమాంతర మరియు పంపిణీ చేయబడిన కంప్యూటింగ్
సమాంతర మరియు పంపిణీ చేయబడిన కంప్యూటింగ్లో ఒకే సమయంలో పనిచేసే బహుళ ప్రాసెసర్లలో ప్రాసెసింగ్ను విభజించడం ఉంటుంది. వివిధ మోడళ్ల మధ్య ప్రాథమిక వ్యత్యాసం ప్రాసెసర్ల మధ్య డేటాను పంపే పద్ధతి. ప్రాసెసర్ల మధ్య డేటా ట్రాన్స్మిషన్ సాధారణంగా సమాంతర కంప్యూటింగ్లో చాలా త్వరగా జరుగుతుంది, అయితే పంపిణీ చేయబడిన కంప్యూటింగ్లో ప్రాసెసర్ల మధ్య డేటా బదిలీ నెట్వర్క్లో జరుగుతుంది మరియు తద్వారా గణనీయంగా నెమ్మదిగా ఉంటుంది.
N ప్రాసెసర్లపై గణన అనేది ఒక ప్రాసెసర్పై తీసుకునే సమయానికి కనీసం N ద్వారా కోషెంట్ని తీసుకుంటుంది. వాస్తవానికి, కొన్ని సబ్టాస్క్లను సమాంతరంగా ఉంచడం సాధ్యం కాదు మరియు కొన్ని ప్రాసెసర్లు మరొక ప్రాసెసర్ నుండి ఫలితం కోసం వేచి ఉండవలసి ఉంటుంది కాబట్టి, ఈ సిద్ధాంతపరంగా ఆదర్శ బంధం ఎప్పటికీ సాధించబడదు.
ప్రాసెసర్ల సంఖ్య ద్వారా గణన సమయం యొక్క ఉత్పత్తి ఒకే ప్రాసెసర్లో ఒకే గణనను నిర్వహించడానికి అవసరమైన సమయానికి సాధ్యమైనంత దగ్గరగా ఉండేలా అల్గారిథమ్లను అభివృద్ధి చేయడం కీలకమైన సంక్లిష్టత సమస్య.
క్వాంటం గణన
క్వాంటం కంప్యూటర్ అనేది క్వాంటం మెకానిక్స్-ఆధారిత గణన నమూనాతో కూడిన కంప్యూటర్. చర్చ్-ట్యూరింగ్ థీసిస్ క్వాంటం కంప్యూటర్లకు నిజమైనది, క్వాంటం కంప్యూటర్ పరిష్కరించగల ఏదైనా సమస్యను ట్యూరింగ్ మెషీన్ ద్వారా కూడా పరిష్కరించవచ్చని సూచిస్తుంది. అయినప్పటికీ, కొన్ని పనులు సైద్ధాంతికంగా తక్కువ తాత్కాలిక సంక్లిష్టతతో క్లాసికల్ కంప్యూటర్ కాకుండా క్వాంటం కంప్యూటర్ని ఉపయోగించి పరిష్కరించబడతాయి. ప్రస్తుతానికి, ఇది ఖచ్చితంగా సైద్ధాంతికమైనది, ఎందుకంటే ఆచరణాత్మక క్వాంటం కంప్యూటర్ను ఎలా అభివృద్ధి చేయాలో ఎవరికీ తెలియదు.
క్వాంటం కంప్యూటర్ల ద్వారా పరిష్కరించగల వివిధ రకాల సమస్యలను పరిశోధించడానికి క్వాంటం సంక్లిష్టత సిద్ధాంతం సృష్టించబడింది. ఇది క్వాంటం కంప్యూటర్ దాడులకు నిరోధకంగా ఉండే క్రిప్టోగ్రాఫిక్ ప్రోటోకాల్లను రూపొందించే ప్రక్రియ అయిన పోస్ట్-క్వాంటం క్రిప్టోగ్రఫీలో ఉపయోగించబడుతుంది.
సమస్య యొక్క సంక్లిష్టత (తక్కువ హద్దులు)
కనుగొనబడని సాంకేతికతలతో సహా సమస్యను పరిష్కరించగల అల్గారిథమ్ల సంక్లిష్టత సమస్య యొక్క సంక్లిష్టత. ఫలితంగా, సమస్య యొక్క సంక్లిష్టత దానిని పరిష్కరించే ఏదైనా అల్గోరిథం యొక్క సంక్లిష్టతకు సమానంగా ఉంటుంది.
ఫలితంగా, పెద్ద O సంజ్ఞామానంలో ఇవ్వబడిన ఏదైనా సంక్లిష్టత అల్గోరిథం మరియు దానితో కూడిన సమస్య రెండింటి యొక్క సంక్లిష్టతను సూచిస్తుంది.
మరోవైపు, సమస్య సంక్లిష్టతపై నాన్ట్రివియల్ తక్కువ హద్దులను పొందడం చాలా కష్టం, మరియు అలా చేయడానికి కొన్ని వ్యూహాలు ఉన్నాయి.
చాలా సమస్యలను పరిష్కరించడానికి, అన్ని ఇన్పుట్ డేటాను తప్పనిసరిగా చదవాలి, ఇది డేటా పరిమాణానికి అనులోమానుపాతంలో సమయం పడుతుంది. ఫలితంగా, ఇటువంటి సమస్యలు కనీసం సరళ సంక్లిష్టతను కలిగి ఉంటాయి లేదా పెద్ద ఒమేగా సంజ్ఞామానంలో Ω(n) యొక్క సంక్లిష్టతను కలిగి ఉంటాయి.
కంప్యూటర్ బీజగణితం మరియు గణన బీజగణిత జ్యామితి వంటి కొన్ని సమస్యలు చాలా పెద్ద పరిష్కారాలను కలిగి ఉంటాయి. అవుట్పుట్ తప్పనిసరిగా వ్రాయబడినందున, సంక్లిష్టత అవుట్పుట్ యొక్క గరిష్ట పరిమాణంతో నిర్బంధించబడుతుంది.
క్రమబద్ధీకరణ అల్గోరిథం కోసం అవసరమైన పోలికల సంఖ్య Ω(nlogn) యొక్క నాన్ లీనియర్ తక్కువ బౌండ్ని కలిగి ఉంటుంది. ఫలితంగా, వాటి సంక్లిష్టత O(nlogn) అయినందున ఉత్తమ సార్టింగ్ అల్గారిథమ్లు అత్యంత ప్రభావవంతంగా ఉంటాయి. n ఉన్నాయి వాస్తవం! n విషయాలను నిర్వహించడానికి మార్గాలు ఈ దిగువ పరిమితికి దారితీస్తాయి. ఎందుకంటే ప్రతి పోలిక ఈ n సేకరణను విభజిస్తుంది! ఆర్డర్లను రెండు ముక్కలుగా చేసి, అన్ని ఆర్డర్లను వేరు చేయడానికి అవసరమైన N పోలికల సంఖ్య తప్పనిసరిగా 2N > n!, స్టిర్లింగ్ సూత్రం ద్వారా O(nlogn)ని సూచిస్తుంది.
తగ్గిన సంక్లిష్టత పరిమితులను పొందడం కోసం సమస్యను మరొక సమస్యగా తగ్గించడం అనేది ఒక సాధారణ వ్యూహం.
అల్గోరిథం అభివృద్ధి
అల్గారిథమ్ యొక్క సంక్లిష్టతను మూల్యాంకనం చేయడం అనేది డిజైన్ ప్రక్రియలో ఒక ముఖ్యమైన అంశం, ఎందుకంటే ఇది ఊహించిన పనితీరు గురించి ఉపయోగకరమైన సమాచారాన్ని అందిస్తుంది.
ఆధునిక కంప్యూటర్ శక్తి యొక్క ఘాతాంక పెరుగుదలను అంచనా వేసే మూర్ యొక్క చట్టం ఫలితంగా, అల్గారిథమ్ల సంక్లిష్టతను మూల్యాంకనం చేయడం తక్కువ సందర్భోచితంగా మారుతుందని తరచుగా అపార్థం ఏర్పడుతుంది. ఇది సరికాదు ఎందుకంటే పెరిగిన శక్తి భారీ మొత్తంలో డేటాను (పెద్ద డేటా) ప్రాసెస్ చేయడానికి అనుమతిస్తుంది. ఉదాహరణకు, పుస్తకం యొక్క గ్రంథ పట్టిక వంటి కొన్ని వందల ఎంట్రీల జాబితాను అక్షర క్రమంలో క్రమబద్ధీకరించేటప్పుడు ఏదైనా అల్గోరిథం సెకను కంటే తక్కువ వ్యవధిలో బాగా పని చేస్తుంది. మరోవైపు, ఒక మిలియన్ ఎంట్రీల కోసం (ఉదాహరణకు, పెద్ద నగరం యొక్క ఫోన్ నంబర్లు), O(n2) పోలికలు అవసరమయ్యే ప్రాథమిక అల్గారిథమ్లు ట్రిలియన్ పోలికలను నిర్వహించాలి, దీనికి 10 వేగంతో మూడు గంటలు పడుతుంది. సెకనుకు మిలియన్ పోలికలు. మరోవైపు, క్విక్సార్ట్ మరియు విలీన క్రమానికి nlogn పోలికలు మాత్రమే అవసరం (పూర్వానికి సగటు-కేస్ సంక్లిష్టత వలె, తరువాతి వాటికి చెత్త-కేస్ సంక్లిష్టత వలె). ఇది n = 30,000,000 కోసం దాదాపు 1,000,000 పోలికలను ఉత్పత్తి చేస్తుంది, ఇది సెకనుకు 3 మిలియన్ పోలికలకు 10 సెకన్లు మాత్రమే పడుతుంది.
ఫలితంగా, సంక్లిష్టతను అంచనా వేయడం అమలుకు ముందు అనేక అసమర్థమైన అల్గారిథమ్లను తొలగించడానికి అనుమతించవచ్చు. సాధ్యమయ్యే అన్ని వేరియంట్లను పరీక్షించకుండానే సంక్లిష్ట అల్గారిథమ్లను చక్కగా ట్యూన్ చేయడానికి కూడా ఇది ఉపయోగించబడుతుంది. సంక్లిష్టత యొక్క అధ్యయనం సంక్లిష్ట అల్గోరిథం యొక్క అత్యంత ఖరీదైన దశలను నిర్ణయించడం ద్వారా అమలు యొక్క సామర్థ్యాన్ని పెంచే ప్రయత్నాన్ని కేంద్రీకరించడానికి అనుమతిస్తుంది.
సర్టిఫికేషన్ పాఠ్యాంశాలతో మిమ్మల్ని మీరు వివరంగా తెలుసుకునేందుకు మీరు దిగువ పట్టికను విస్తరించవచ్చు మరియు విశ్లేషించవచ్చు.
EITC/IS/CCTF కంప్యూటేషనల్ కాంప్లెక్సిటీ థియరీ ఫండమెంటల్స్ సర్టిఫికేషన్ కరికులం వీడియో రూపంలో ఓపెన్-యాక్సెస్ డిడాక్టిక్ మెటీరియల్లను సూచిస్తుంది. అభ్యాస ప్రక్రియ దశల వారీగా విభజించబడింది (కార్యక్రమాలు -> పాఠాలు -> అంశాలు) సంబంధిత పాఠ్యాంశాలను కవర్ చేస్తుంది. డొమైన్ నిపుణులతో అపరిమిత కన్సల్టెన్సీ కూడా అందించబడుతుంది.
ధృవీకరణ ప్రక్రియపై వివరాల కోసం తనిఖీ చేయండి ఇది ఎలా పని చేస్తుంది.
ప్రాథమిక సహాయక పాఠ్య ప్రణాళిక పఠన సామగ్రి
S. అరోరా, B. బరాక్, కంప్యూటేషనల్ కాంప్లెక్సిటీ: ఎ మోడరన్ అప్రోచ్
https://theory.cs.princeton.edu/complexity/book.pdf
సెకండరీ సపోర్టివ్ కరికులమ్ రీడింగ్ మెటీరియల్స్
O. గోల్డ్రీచ్, సంక్లిష్టత సిద్ధాంతానికి పరిచయం:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
వివిక్త గణితంపై సపోర్టివ్ కరికులమ్ రీడింగ్ మెటీరియల్స్
J. Aspnes, వివిక్త గణితంపై గమనికలు:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
గ్రాఫ్ థియరీపై సపోర్టివ్ కరికులమ్ రీడింగ్ మెటీరియల్స్
R. డీస్టెల్, గ్రాఫ్ థియరీ:
https://diestel-graph-theory.com/
EITC/IS/CCTF కంప్యూటేషనల్ కాంప్లెక్సిటీ థియరీ ఫండమెంటల్స్ ప్రోగ్రామ్ కోసం పూర్తి ఆఫ్లైన్ స్వీయ-అభ్యాస సన్నాహక సామగ్రిని PDF ఫైల్లో డౌన్లోడ్ చేయండి
EITC/IS/CCTF సన్నాహక పదార్థాలు - ప్రామాణిక వెర్షన్
EITC/IS/CCTF ప్రిపరేటరీ మెటీరియల్స్ - సమీక్ష ప్రశ్నలతో పొడిగించిన వెర్షన్