त्वरित कम्प्यूटिंग ट्यूटोरियल

कंप्यूटर के लिए क्या करना आसान है और क्या लगभग असंभव है? ये प्रश्न कम्प्यूटेशनल जटिलता के मुद्दे पर हैं। हम आपको इस परिदृश्य का एक नक्शा प्रस्तुत करते हैं।

विभिन्न जटिलता कक्षाएं एक पदानुक्रमित रूप में कार्यों को सॉर्ट करती हैं। एक वर्ग में दूसरे के सभी कार्यों को शामिल किया जा सकता है, साथ ही ऐसे कार्यों के लिए जिन्हें अतिरिक्त कंप्यूटिंग संसाधनों की आवश्यकता होती है।

कार्य की मूलभूत कठिनाई क्या है? यह कंप्यूटर वैज्ञानिकों के मूल कार्य का सूत्रीकरण है जो तथाकथित के अनुसार कार्यों को क्रमबद्ध करने की कोशिश कर रहे हैं। कठिनाई कक्षाएं । ये सभी कम्प्यूटेशनल कार्यों वाले समूह हैं जिनके लिए कम्प्यूटेशनल संसाधनों की एक निश्चित राशि से अधिक की आवश्यकता नहीं है - जैसे समय या मेमोरी। आइए 123 456 789 001 जैसी बड़ी संख्या के साथ एक सरल उदाहरण लेते हैं। एक पूछ सकता है: क्या यह एक प्रमुख संख्या है - एक जो केवल 1 से विभाजित होती है और स्वयं? कंप्यूटर वैज्ञानिक तेजी से एल्गोरिदम के साथ इसका जवाब दे सकते हैं - जैसे कि वे मनमाने ढंग से बड़ी संख्या में धीमा करना शुरू नहीं करते हैं। हमारे मामले में, यह पता चला है कि यह संख्या अभाज्य नहीं है। तब हम प्रश्न पूछ सकते हैं: इसके प्रमुख कारक क्या हैं? लेकिन इसका जवाब देने के लिए कोई त्वरित एल्गोरिदम नहीं है - केवल अगर आप क्वांटम कंप्यूटर का उपयोग करते हैं। इसलिए, कंप्यूटर वैज्ञानिकों का मानना ​​है कि ये दो कार्य विभिन्न जटिलता वर्गों के हैं।

कठिनाई के कई अलग-अलग वर्ग हैं, हालांकि ज्यादातर मामलों में शोधकर्ता यह साबित करने में असमर्थ थे कि एक वर्ग दूसरों से स्पष्ट रूप से अलग है। वर्गों के बीच मतभेद का साक्ष्य इस क्षेत्र में सबसे कठिन और महत्वपूर्ण कार्यों में से एक है।

कक्षाओं के बीच का अंतर मुश्किल से अलग या स्पष्ट हो सकता है, और सभी वर्गों को अच्छी तरह से समझना काफी मुश्किल है। इसलिए, हमने इस गाइड को सात सबसे मौलिक कठिनाई वर्गों के लिए संकलित किया है। और हाँ, अब आप BPP और BQP को भ्रमित नहीं करेंगे।

पी

संकेत : बहुपद समय

संक्षिप्त विवरण : सभी कार्य जिन्हें एक शास्त्रीय (गैर-क्वांटम) कंप्यूटर आसानी से हल कर सकता है।

सटीक विवरण : क्लास पी एल्गोरिदम काम करना बंद कर देना चाहिए और समय से अधिक नहीं n में सही उत्तर देना चाहिए ^c , जहां n इनपुट डेटा की लंबाई है, c एक स्थिर है।

विशिष्ट कार्य :

• क्या संख्या प्रधान है?
• दो बिंदुओं के बीच सबसे छोटा रास्ता कौन सा है?

शोधकर्ता क्या जानना चाहेंगे : क्या P, NP के साथ मेल खाता है? संयोग कंप्यूटर विज्ञान में क्रांति लाएगा और अधिकांश क्रिप्टोग्राफिक सिस्टम को अर्थहीन बना देगा (लेकिन लगभग कोई भी इस पर विश्वास नहीं करता है)।

एनपी

निरूपित : गैर-नियतात्मक बहुपद समय

संक्षिप्त विवरण : सभी कार्य जो एक क्लासिक कंप्यूटर आसानी से जांच सकते हैं कि क्या कोई समाधान है।

सटीक विवरण : समस्या वर्ग में गिरती है, जब उत्तर हां होता है, तो उत्तर की शुद्धता का संक्षिप्त प्रमाण होता है। यदि इनपुट एक स्ट्रिंग एक्स है, और आपको यह तय करने की आवश्यकता है कि क्या उत्तर "हां" से मेल खाता है, तो एक संक्षिप्त प्रमाण एक और स्ट्रिंग, वाई होगा, जिसका उपयोग बहुपद समय में सही उत्तर "हां" को सत्यापित करने के लिए किया जा सकता है। (वाई को कभी-कभी "संक्षिप्त गवाह" कहा जाता है - एनपी के सभी कार्यों में छोटे गवाह होते हैं, जिसके लिए उन्हें जांचा जा सकता है)।

विशिष्ट कार्य :

• क्लिक करने का कार्य । किनारों और कोने के साथ एक ग्राफ की कल्पना करें - उदाहरण के लिए, कोने सामाजिक नेटवर्क के उपयोगकर्ताओं को इंगित करते हैं, और किनारे से संकेत मिलता है कि वे "मित्र" हैं। एक क्लिप इस ग्राफ का एक सबसेट है जिसमें सभी लोग एक दूसरे के दोस्त हैं। आप ग्राफ के बारे में निम्नलिखित प्रश्न पूछ सकते हैं: क्या इसमें 20 लोगों का क्लिक है? 50 लोग? 100? एक गुट को खोजना एक एनपी-पूर्ण कार्य है , अर्थात इसकी जटिलता सभी एनपी-कार्यों में सबसे अधिक है। लेकिन, एक संभावित उत्तर - 50 नोड्स का सबसेट जो एक क्लिक हो सकता है या नहीं - सत्यापित करना आसान है।
• सेल्समैन का काम । किसी भी दो जोड़े के बीच की दूरी वाले शहरों के एक सेट को देखते हुए - क्या सभी शहरों के आसपास जाने का एक रास्ता है, एक निश्चित दूरी से कम ड्राइविंग? उदाहरण के लिए, क्या कोई विक्रेता 11,000 मील से कम की सभी अमेरिकी राजधानियों की यात्रा कर सकता है?

शोधकर्ता क्या जानना चाहेंगे: पी = एनपी? कंप्यूटर विज्ञान के विशेषज्ञ और इस समस्या को हल करने के करीब नहीं आए।

शारीरिक रूप से विकलांग

निरूपित : बहुपद पदानुक्रम

संक्षिप्त विवरण : PH, NP का सामान्यीकरण है। इसमें वे सभी कार्य शामिल हैं, जिन्हें NP के किसी कार्य से शुरू करके, और अतिरिक्त स्तरों को लागू करने से प्राप्त किया जा सकता है।

सटीक विवरण : PH में विभिन्न "क्वांटिफायर" वाले कार्य होते हैं जो इन कार्यों को जटिल बनाते हैं। विभिन्न क्वांटिफायर के साथ एक समस्या का एक उदाहरण: अगर हमें X दिया जाता है, तो क्या Y का अस्तित्व ऐसा है कि हर Z के लिए W मौजूद है, जिसके लिए R संतुष्ट है? समस्या में जितने अधिक मात्रा में, उतना ही अधिक जटिल और बहुपद पदानुक्रम।

एक विशिष्ट कार्य यह निर्धारित करना है कि क्या वास्तव में आकार 50 का एक क्लिक है, और आकार 51 का कोई क्लिक नहीं है।

शोधकर्ता क्या जानना चाहेंगे : कोई भी अभी तक यह साबित नहीं कर पाया है कि PH, P से अलग है। यह समस्या P और NP की समानता के बराबर है, क्योंकि अगर यह अचानक पता चला कि P = NP, तो सभी PH कम होकर P (P = PH) हो जाएगा।

PSPACE

Denotes : बहुपद स्थान की कमी

संक्षिप्त विवरण : PSPACE में सभी कार्य शामिल हैं जिन्हें उचित मात्रा में मेमोरी का उपयोग करके हल किया जा सकता है।

सटीक विवरण : PSPACE कार्यों को हल करते समय, आप अब समय के बारे में चिंता नहीं करते हैं, आप केवल उस मेमोरी के बारे में चिंता करते हैं जो एल्गोरिदम के काम करने के लिए आवश्यक है। कंप्यूटर वैज्ञानिकों ने यह साबित किया है कि PSPACE में PH होता है जिसमें NP होता है जिसमें P होता है।

विशिष्ट कार्य : पी, एनपी और पीएच से सभी कार्य PSPACE में निहित हैं।

शोधकर्ता क्या जानना चाहेंगे : क्या पी पी से अलग है?

BQP

संकेत : त्रुटि संभाव्यता सीमा के साथ क्वांटम बहुपद समय

संक्षिप्त विवरण : सभी कार्य जो आसानी से एक क्वांटम कंप्यूटर पर हल किए जा सकते हैं।

सटीक विवरण : सभी कार्य जिन्हें बहुपद समय में एक क्वांटम कंप्यूटर पर हल किया जा सकता है।

विशिष्ट समस्या : पूर्णांक के प्रमुख कारक ज्ञात कीजिए।

शोधकर्ता क्या जानना चाहेंगे : अब तक, यह साबित हो चुका है कि BQP PSPACE में समाहित है, और BQP में P. शोधकर्ता शामिल हैं, यह नहीं जानते कि BQP NP में निहित है या नहीं, लेकिन उनका मानना ​​है कि इन दो वर्गों की तुलना नहीं की जा सकती है - ऐसे कार्य हैं जो NP के भाग होते हैं लेकिन BQP में नहीं, और इसके विपरीत।

EXPTIME

Denotes : घातीय समय

संक्षिप्त विवरण : सभी कार्य जिन्हें शास्त्रीय कंप्यूटर पर घातीय समय में हल किया जा सकता है।

सटीक विवरण : EXP में पिछले सभी वर्ग - P, NP, PH, PSPACE और BQP शामिल हैं। शोधकर्ताओं ने साबित किया कि यह P से अलग है - उन्होंने ऐसे कार्यों की खोज की जो EXP का हिस्सा हैं और P का हिस्सा नहीं हैं।

विशिष्ट कार्य : शतरंज और चेकर्स जैसे खेलों का सामान्यीकरण। यदि कोई बिसात किसी भी आकार की हो सकती है, तो यह निर्धारित करने का कार्य कि क्या खिलाड़ियों में से किसी एक को फायदा है, EXP का कार्य बन जाता है।

शोधकर्ता क्या जानना चाहेंगे : वे यह साबित करना चाहेंगे कि PSPACE में EXP नहीं है। उनका मानना ​​है कि ऐसे कार्य हैं जो EXP का हिस्सा हैं लेकिन PSPACE का हिस्सा नहीं हैं, क्योंकि कभी-कभी EXP से किसी कार्य को हल करने में बहुत समय लगता है। शोधकर्ता जानते हैं कि EXP और P को कैसे अलग किया जाए।

बीपीपी

संकेत : त्रुटि संभावना सीमा के साथ बहुपद समय

संक्षिप्त विवरण : ऐसे कार्य जिन्हें यादृच्छिकता का उपयोग करने वाले एल्गोरिदम का उपयोग करके जल्दी से हल किया जा सकता है।

सटीक विवरण : बीपीपी पी के समान है, इस अंतर के साथ कि एल्गोरिथ्म में ऐसे चरण शामिल हो सकते हैं जिनमें निर्णय यादृच्छिक रूप से किए जाते हैं। BPP में एल्गोरिदम को 1 के करीब संभावना के साथ सही उत्तर देने की आवश्यकता है।

विशिष्ट कार्य : आपके पास दो भिन्न सूत्र हैं जो कई चर के साथ बहुपद देते हैं। क्या ये सूत्र एक ही बहुपद की गणना करते हैं? यह बहुपद पहचान की जाँच का कार्य है।

शोधकर्ता क्या जानना चाहेंगे : क्या बीपीपी और पी बराबर हैं। यदि वे समान हैं, तो यादृच्छिकता वाले किसी भी एल्गोरिदम को यादृच्छिकता से समाप्त किया जा सकता है। उनका मानना ​​है कि यह है - कि हर समस्या के लिए जिसके लिए एक प्रभावी यादृच्छिक एल्गोरिदम है, एक प्रभावी नियतात्मक एल्गोरिथ्म है - लेकिन वे अभी तक यह साबित नहीं कर पाए हैं।