क्या "पूर्णांक पर द्वि-चर द्विघात बहुपद को हल करना" एनपी-पूर्ण समस्या है?

Question

इस विकिपीडिया लेख पर , वे दावा करते हैं कि दिया गया है$A, B, C \geq 0, \; \in \mathbb{Z}$, यह तय करना कि क्या मौजूद हैं $x, \,y \geq 0, \, \in \mathbb{Z}$ ऐसा है कि $Ax^2+By-C=0$ NP- पूर्ण है

यह देखते हुए कि मैं कितना आसान (कुछ नहीं बल्कि वुल्फराम के साथ) हल कर सकता हूं, यह सही नहीं लगता। मुझे यकीन है कि यह या तो गलत तरीके से लिखा गया है या मैं केवल कुछ गलत समझ रहा हूं।

Answer 1

जैसा कि आपने उल्लेख किया है कि डायोफैंटाइन समीकरण को हल करना जटिल, गणितीय नहीं है।

आवश्यक अवशेषों को खोजने के लिए सभी की आवश्यकता है $r$ का $x$ सापेक्ष $B$ ऐसा है कि $Ax^2-C$ का एक बहु है $B$, तो सभी पूर्णांक समाधान फार्म के होते हैं $x=Bn+r$ तथा $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$।

अवशेष खोजने का एक तरीका $r$ को है

1. फ़ैक्टर $B=\prod_i q_i^{a_i}$, कहां है $q_i$ अलग-अलग primes हैं,
2. बधाई को हल करें$Ax^2-C\equiv 0\pmod{q_i}$, जो सबसे खराब स्थिति में दो समाधान हैं $\pm t_i$,
3. समाधान के लिए इन उपायों को उठाएं$\pm\theta_i$ का $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ तथा
4. चीनी समाधान प्रमेय का उपयोग करके इन समाधानों को गोंद करें$Ax^2-C\equiv0\pmod{B}$। सभी नोट करें$\pm$ विकल्प।

फैक्टरिंग $B$संभवतः कठिन है, लेकिन शायद यह नहीं है। मेरा पुराना ज्ञान है कि किसी को पता नहीं है। इसके अलावा शायद यह भी संभव है खोजने के लिए$r$ बिना तथ्य के $B$। मैंने जो सबूत देखे कि यह निष्कर्ष निकाला जाए कि समस्या एनपी-पूर्ण है वह निर्णय है जो अभी भी बना हुआ है।

मूल निर्णय समस्या अगर जाँच में से एक हो जाती है $\pm$ ऐसा है कि अंतराल $x\geq0$, दूसरे शब्दों में $n\geq -r/B$, चौराहों (और चौराहे में एक पूर्णांक होता है) जहां अंतराल होता है $n$ इस प्रकार कि $y\geq0$। के बिट आकार की तुलना में$(A,B,C)$ कई अवशेष हो सकते हैं $r$मापना। मैं यह दावा नहीं करूंगा। इसकी एनपी-पूर्णता का प्रमाण दें।

मूर एंड मेर्टेंस की प्रकृति की गणना , खंड 5.4.4 में इस निर्णय की समस्या के लिए SUBSET SUM निर्णय की समस्या को कम करने (व्यायाम के रूप में शेष भागों के साथ) (इसे QDE कहते हैं)।

---

मुझे उनके तर्क को स्केच करने के लिए कहना चाहिए कि QDE के इनपुट में SUBSET SUM का इनपुट कैसे एनकोड किया गया है और कैसे विकल्प $\pm$SUBSET SUM में विचार कर सकने वाले सबसेट के अनुरूप। शायद मैं या कोई और बाद में विवरण का विस्तार कर सकता है।

SUBSET SUM को एक सेट मिलता है (या शायद एक बहु-सेट) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ तथा $t\in \mathbb{N}$ और पूछता है कि क्या कोई उपसमुच्चय है $Y\subset X$ ऐसा है कि इसके तत्वों का योग है $t$। अगर कोई परिभाषित करता है$S=2t-\sum_{k=1}^{n}x_k$ तब SUBSET SUM के अस्तित्व के बराबर है $\sigma_i\in\{-1,1\}$ ऐसा है कि $$S=\sum_{k=1}^{n}\sigma_kx_k$$

यहाँ हम पहले से ही पसंद के रूप में एन्कोडेड सबसेट के विकल्प हैं $\pm$।

ले रहा $m$ ऐसा है कि $2^m>\sum_{k=1}^{n}x_k$ इस समीकरण के बराबर है $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$ अगर हम चुनते हैं $q_1,q_2,...,q_n$ अपेक्षाकृत प्रमुख विषम संख्याएँ (पहली विषम गति पर्याप्त), चीनी रेमिनेडर प्रमेय सुनिश्चित करता है कि वहाँ हैं $\theta_1,\theta_2,\ldots,\theta_n$ ऐसा है कि

$$ \begin{align} \theta_k&\equiv x_k\pmod{2^m}\\\ \theta_i&\equiv0\pmod{\prod_{k=1,k\neq i}^{n}q_k^m}\\\ \theta_k&\not\equiv0\pmod{q_k} \end{align} $$

$\theta_i$ QDE समस्या के समाधान के लिए बनाया जाएगा $\theta_i$ कि हम शुरुआत में उल्लेख किया है।

इन बधाई के पहले समूह का अर्थ है कि SUBSET SUM के बराबर है $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

अब वे द्विघात समीकरण का निर्माण करते हैं, जो घुलनशीलता इस अनुरूपता की विलेयता के बराबर है।

वे परिभाषित करते हैं $H=\sum_{k=1}^n\theta_k$ तथा $K=\prod_{k=1}^{n}q_k^m$। कि किसी भी निरीक्षण करें$x$ फार्म का $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ संतुष्ट $$H^2-x^2\equiv0\pmod{K}$$

फिर, एक जोड़ी अभ्यास के माध्यम से, वे तर्क देते हैं कि चुनने के लिए विकल्प क्यों हैं $q_i$ और एक $\lambda_1$ बहुत बड़ा ऐसा है $2H<K$, तथा $|t|<H$और यह सुनिश्चित करना $(*)$एक समाधान है अगर और केवल अगर द्विध्रुवीय Diophantine समीकरण

$$\underbrace{(\lambda_12^{m+1}+K)}_{A}x^2+\underbrace{2^{m+1}K}_{B}y-\underbrace{(\lambda_12^{m+1}H^2-KS^2)}_C=0$$

एक समाधान है $x,y\geq0$।

ध्यान दें कि यह समीकरण कैसे फिर से लिखता है

$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$

तकनीकी विवरण में किए गए विकल्प ऐसे हैं जब कोई समाधान होता है $x,y\geq0$ इस समीकरण के लिए हमेशा ऐसा ही होता है $H^2-x^2$ पहले से ही एक से अधिक होने के लिए जाना जाता है $K$ तथा $S^2-x^2=(S+x)(S-x)$ के एक से अधिक $2^{m+1}$।