Apakah "Memecahkan polinomial kuadrat dua variabel di atas Bilangan bulat" adalah Masalah NP-Lengkap?

Aug 17 2020

Di artikel Wikipedia ini , mereka mengklaim yang diberikan$A, B, C \geq 0, \; \in \mathbb{Z}$, memutuskan apakah ada $x, \,y \geq 0, \, \in \mathbb{Z}$ seperti yang $Ax^2+By-C=0$ itu NP-complete?

Diberikan oleh betapa mudahnya saya bisa menyelesaikan beberapa (hanya dengan Wolfram), sepertinya tidak benar. Saya yakin itu salah ditulis atau saya hanya salah paham.

Jawaban

9 plop Aug 18 2020 at 01:30

Seperti yang Anda catat, memecahkan persamaan Diophantine tidaklah rumit, secara matematis.

Yang dibutuhkan hanyalah menemukan sisa yang diperlukan $r$ dari $x$ modulo $B$ seperti yang $Ax^2-C$ adalah kelipatan dari $B$, maka semua solusi bilangan bulat adalah dalam bentuk $x=Bn+r$ dan $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.

Salah satu cara untuk menemukan sisanya $r$ adalah untuk

  1. faktor $B=\prod_i q_i^{a_i}$, dimana $q_i$ adalah bilangan prima yang berbeda,
  2. memecahkan kesesuaian$Ax^2-C\equiv 0\pmod{q_i}$, yang dalam kasus terburuk memiliki dua solusi $\pm t_i$,
  3. angkat solusi ini menjadi solusi$\pm\theta_i$ dari $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ dan
  4. rekatkan solusi ini, dengan menggunakan Teorema Sisa Cina untuk mendapatkan solusi$Ax^2-C\equiv0\pmod{B}$. Perhatikan semua$\pm$ pilihan.

Anjak $B$mungkin sulit, tetapi mungkin juga tidak. Pengetahuan saya yang ketinggalan zaman adalah tidak ada yang tahu. Mungkin juga mungkin untuk menemukan sisanya$r$ tanpa anjak piutang $B$. Apa bukti yang saya lihat eksploitasi untuk menyimpulkan bahwa masalah NP-complete adalah keputusan yang masih harus dibuat.

Masalah keputusan asli menjadi pemeriksaan jika salah satu pilihan $\pm$ sedemikian rupa sehingga intervalnya $x\geq0$, dengan kata lain $n\geq -r/B$, intersections (dan intersection berisi integer) interval dimana $n$ seperti itu $y\geq0$. Dibandingkan dengan ukuran bit$(A,B,C)$ masih banyak sisa $r$untuk menguji. Saya tidak akan mengukur klaim ini. Biarlah bukti kelengkapan NP-nya memberikan buktinya.

Dalam Moore dan Mertens ' The Nature of Computation , bagian 5.4.4 ada pengurangan (dengan bagian tersisa sebagai latihan) dari masalah keputusan SUM SUBSET untuk masalah keputusan ini (sebut saja QDE).


Izinkan saya membuat sketsa argumen mereka hanya untuk merasakan bagaimana input ke SUBSET SUM dikodekan dalam input ke QDE dan bagaimana pilihan $\pm$sesuai dengan subset yang dapat dipertimbangkan dalam SUBSET SUM. Mungkin saya atau orang lain dapat memperluas detailnya nanti.

SUBSET SUM mendapat satu set (atau mungkin multi-set) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ dan $t\in \mathbb{N}$ dan menanyakan apakah ada subset $Y\subset X$ sedemikian rupa sehingga jumlah elemennya $t$. Jika seseorang mendefinisikan$S=2t-\sum_{k=1}^{n}x_k$ maka SUBSET SUM setara dengan keberadaan $\sigma_i\in\{-1,1\}$ seperti yang $$S=\sum_{k=1}^{n}\sigma_kx_k$$

Di sini kita sudah memiliki pilihan subset yang dikodekan sebagai pilihan $\pm$.

Pengambilan $m$ seperti yang $2^m>\sum_{k=1}^{n}x_k$ persamaan ini setara dengan $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$ Jika kita memilih $q_1,q_2,...,q_n$ bilangan ganjil relatif prima (cukup dengan bilangan prima ganjil pertama), teorema Sisa Cina memastikan bahwa ada $\theta_1,\theta_2,\ldots,\theta_n$ seperti yang

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

Itu $\theta_i$ akan menjadi, untuk masalah QDE yang akan dibuat, solusinya $\theta_i$ yang kami sebutkan di awal.

Kelompok pertama dari kongruensi ini menyiratkan bahwa SUBSET SUM setara dengan $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

Sekarang mereka membangun persamaan kuadrat, yang kelarutannya setara dengan kelarutan kongruensi ini.

Mereka mendefinisikan $H=\sum_{k=1}^n\theta_k$ dan $K=\prod_{k=1}^{n}q_k^m$. Amati itu$x$ dari bentuk $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ memuaskan $$H^2-x^2\equiv0\pmod{K}$$

Kemudian, melalui sepasang latihan, mereka berdebat mengapa ada pilihan untuk memetik $q_i$ dan a $\lambda_1$ cukup besar seperti itu $2H<K$, dan $|t|<H$, dan memastikannya $(*)$memiliki solusi jika dan hanya jika Persamaan Diofantin Kuadratik

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

punya solusi $x,y\geq0$.

Perhatikan bagaimana persamaan ini ditulis ulang sebagai

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

Pilihan yang dibuat dalam detail teknis dibuat sedemikian rupa ketika ada solusi $x,y\geq0$ untuk persamaan ini selalu demikian $H^2-x^2$ sudah dikenal sebagai kelipatan $K$ dan $S^2-x^2=(S+x)(S-x)$ kelipatan $2^{m+1}$.