“ การแก้พหุนามกำลังสองตัวแปรสองตัวบนจำนวนเต็ม” เป็นปัญหา NP-Complete หรือไม่

Aug 17 2020

ในบทความ Wikipedia นี้พวกเขาอ้างว่าได้รับ$A, B, C \geq 0, \; \in \mathbb{Z}$ตัดสินใจว่ามีอยู่จริงหรือไม่ $x, \,y \geq 0, \, \in \mathbb{Z}$ ดังนั้น $Ax^2+By-C=0$ NP สมบูรณ์หรือไม่

ด้วยความง่ายที่ฉันสามารถแก้ปัญหาบางอย่างได้ (โดยไม่มีอะไรเลยนอกจาก Wolfram) ดูเหมือนจะไม่ถูกต้อง ฉันแน่ใจว่ามันเขียนไม่ถูกต้องหรือฉันแค่เข้าใจผิด

คำตอบ

9 plop Aug 18 2020 at 01:30

ดังที่คุณสังเกตการแก้สมการไดโอแฟนไทน์นั้นไม่ซับซ้อนในทางคณิตศาสตร์

สิ่งที่จำเป็นทั้งหมดคือการหาเศษเหลือที่จำเป็น $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$ เป็นช่วงเวลาที่แตกต่างกัน
  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$. สิ่งที่พิสูจน์ได้ว่าฉันเห็นการหาประโยชน์เพื่อสรุปว่าปัญหาคือ NP-complete คือการตัดสินใจที่ยังคงต้องทำ

ปัญหาการตัดสินใจเดิมจะเป็นการตรวจสอบว่าหนึ่งในตัวเลือก $\pm$ เป็นเช่นนั้นช่วงเวลา $x\geq0$กล่าวอีกนัยหนึ่ง $n\geq -r/B$ตัดกัน (และจุดตัดประกอบด้วยจำนวนเต็ม) ช่วงเวลาที่ $n$ เป็นเช่นนั้น $y\geq0$. เมื่อเทียบกับขนาดบิตของ$(A,B,C)$ อาจมีเศษเหลืออยู่มากมาย $r$ทดสอบ. ฉันจะไม่นับจำนวนการอ้างสิทธิ์นี้ ให้หลักฐานความสมบูรณ์ของ NP เป็นหลักฐาน

ในThe Nature of Computation ของ Moore and Mertens ส่วนที่ 5.4.4 มีการลด (โดยมีส่วนที่เหลือเป็นแบบฝึกหัด) ของปัญหาการตัดสินใจ SUBSET SUM สำหรับปัญหาการตัดสินใจนี้ (ขอเรียกว่า QDE)


ให้ฉันร่างอาร์กิวเมนต์ของพวกเขาเพียงเพื่อให้เข้าใจว่าอินพุตไปยัง SUBSET SUM ถูกเข้ารหัสในอินพุตไปยัง QDE อย่างไรและตัวเลือกของ $\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$และมั่นใจว่า $(*)$มีทางแก้ก็ต่อเมื่อสมการกำลังสองไดโอแฟนไทน์

$$\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}$.