गणित
क्या P बराबर NP है?
दूर क्षितिजयह क्यों महत्वपूर्ण है
यह पूछता है कि क्या हर वह समस्या, जिसका उत्तर जाँचना आसान है, हल करने में भी आसान है। अगर ऐसा है, तो परिवहन की सर्वोत्तम योजना बन सकेगी जिससे लोग और सामान तेज़ और सस्ते में पहुँचेंगे, लेकिन सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी असंभव हो जाएगी।
हम क्या जानते हैं
1971 में उठाया गया प्रश्न: यदि किसी समस्या का हल जाँचना आसान है, तो क्या उसे हल करना भी आसान है?
रुकावट क्या है
प्रमाण की कई प्रमुख तकनीकों के परिवार अपर्याप्त सिद्ध हो चुके हैं।
वर्तमान सुराग
ज्यामितीय जटिलता सिद्धांत, परिपथ निचली सीमाएँ।
उप-प्रश्न
- क्या कोई सिद्ध कर सकता है कि किसी स्पष्ट रूप से दी गई समस्या के लिए रैखिक से बड़े आकार के बूलियन परिपथ ज़रूरी हैं? सबसे अच्छी ज्ञात निचली सीमा केवल लगभग 4n है।
- क्या NP, co-NP से भिन्न है? समतुल्य रूप में, क्या ऐसा कोई प्रमाण तंत्र नहीं है जो हर पुनरुक्ति (टॉटोलॉजी) का छोटा प्रमाण दे?
- कौन-सी प्रमाण तकनीकें ‘सापेक्षीकरण’ और ‘प्राकृतिक प्रमाण’ की ज्ञात बाधाओं को पार कर सकती हैं?
संबंधित प्रश्न
स्रोत
अभी किसी विशेषज्ञ ने समीक्षा नहीं की है।
अंतिम जाँच: 2026-11-18
इस प्रश्न का इतिहास
नक्शे पर वापस →