theory - Not-mathematical description of NL-complexity -

एनपी-जटिलता से संबंधित होना प्रतीत होता है, और मुझे एक गैर-गणितीय व्याख्या करना चाहिए (यह कि मेरे पास केवल पास है उस लेख में प्रयुक्त गणित के स्तर के साथ परिचित) कोई यह बता सकता है कि यह प्रोग्रामिंग और एनपी-जटिलता से कैसे संबंधित है?

एल्गोरिदम जो एनएल- जटिलता मेमोरी स्पेस में चला सकती है जो समस्या के आकार के साथ केवल लॉगरिदमिक (बहुत धीमे) बढ़ती है। Inotherwords, इन समस्याओं को आवश्यक स्मृति उपयोग के संबंध में बहुत अच्छी तरह से बढ़ाया जाएगा - समस्या का आकार दोहराए और आप को पूरा करने के लिए एल्गोरिदम चलाने के लिए शायद ही और अधिक स्मृति की आवश्यकता होगी। मुझे नहीं पता है कि क्या एनएल और एनपी जटिलता सेटों के बीच सिद्ध एक सैद्धांतिक संबंध है। एनपी जटिलता उस समय से संबंधित है जब इसे प्रोग्राम पूरा करने में लग जाता है - जबकि एनएल जटिलता प्रोग्राम को पूरा करने के लिए आवश्यक स्मृति स्थान की विशेषता है।

मैंने उस विकी लेख में नोटिस किया था जिसे आपने कहा था कि यह ज्ञात नहीं है कि क्या एनएल = पी यह असंभव लगता है क्योंकि इसका मतलब यह होगा कि सभी एल्गोरिदम जो बहुपद समय (w.r.t का आकार) में पूर्ण हो सकते हैं स्मृति अंतरिक्ष में भी समाप्त कर सकते हैं जो कि तराजू से लॉग-लिथ्मिक रूप से w.r.t. समस्या आकार काश, वो सही होता! अभी के लिए हम केवल जानते हैं कि एनएल पी में निहित है।

-पॉल