“İki değişkenli kuadratik polinomları Tamsayılar Üzerinden Çözmek” NP-Tam bir Problem midir?
Bu Wikipedia makalesinde , verilmiş olduğunu iddia ediyorlar$A, B, C \geq 0, \; \in \mathbb{Z}$var olup olmadığına karar vermek $x, \,y \geq 0, \, \in \mathbb{Z}$ öyle ki $Ax^2+By-C=0$ NP tamamlandı mı?
Bazılarını ne kadar kolay çözebileceğime göre (Wolfram dışında hiçbir şey olmadan), bu doğru görünmüyor. Eminim ya yanlış yazılmış ya da bir şeyi yanlış anlıyorum.
Yanıtlar
Sizin de belirttiğiniz gibi, Diophantine denklemini çözmek matematiksel olarak karmaşık değildir.
Gereken tek şey gerekli artıkları bulmaktır $r$ nın-nin $x$ modulo $B$ öyle ki $Ax^2-C$ katları $B$, tüm tamsayı çözümleri formdadır $x=Bn+r$ ve $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.
Kalanları bulmanın bir yolu $r$ için
- faktör $B=\prod_i q_i^{a_i}$, nerede $q_i$ farklı asallardır
- bağları çöz$Ax^2-C\equiv 0\pmod{q_i}$, en kötü durumda iki çözümü olan $\pm t_i$,
- bu çözümleri çözümlere taşıyın$\pm\theta_i$ nın-nin $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ ve
- bir çözüm elde etmek için Çin Kalan Teoremini kullanarak bu çözümleri yapıştırın .$Ax^2-C\equiv0\pmod{B}$. Tüm$\pm$ seçimler.
Faktoring $B$muhtemelen zor, ama belki de değil. Benim eski bilginin kimse bilmiyor olmasıdır. Kalanları da bulmak mümkün olabilir$r$ faktoring olmadan $B$. Sorunun NP-tam olduğu sonucuna varmak için istismar gördüğümün kanıtı, hala verilmesi gereken karardır.
Orijinal karar problemi, aşağıdaki seçeneklerden birinin kontrol edilmesine dönüşür: $\pm$ öyle mi ki aralık $x\geq0$, Diğer bir deyişle $n\geq -r/B$, aralık ile kesişir (ve kesişim bir tamsayı içerir) burada $n$ şekildedir $y\geq0$. Bit boyutuna kıyasla$(A,B,C)$ birçok kalıntı olabilir $r$test etmek için. Bu iddianın miktarını belirtmeyeceğim. NP-bütünlüğünün kanıtı bunun kanıtını versin.
Moore ve Mertens'in Hesaplamanın Doğası , bölüm 5.4.4'te SUBSET SUM karar probleminin bu karar problemine indirgenmesi (alıştırma olarak bırakılan kısımlar) vardır (buna QDE diyelim).
Sadece SUBSET SUM girdisinin QDE girdisinde nasıl kodlandığını ve seçimlerinin nasıl $\pm$SUBSET SUM'da dikkate alınabilecek alt kümelere karşılık gelir. Belki ben veya bir başkası ayrıntıları daha sonra genişletebilir.
ALT Küme Toplamı bir küme (veya belki bir çoklu küme) alır $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ ve $t\in \mathbb{N}$ ve bir alt küme olup olmadığını sorar $Y\subset X$ öyle ki öğelerinin toplamı $t$. Biri tanımlarsa$S=2t-\sum_{k=1}^{n}x_k$ SUBSET SUM şunun varlığına eşdeğerdir: $\sigma_i\in\{-1,1\}$ öyle ki $$S=\sum_{k=1}^{n}\sigma_kx_k$$
Burada halihazırda seçimler olarak kodlanmış alt kümeler için $\pm$.
Alma $m$ öyle ki $2^m>\sum_{k=1}^{n}x_k$ bu denklem eşdeğerdir $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$ Eğer seçersek $q_1,q_2,...,q_n$ Nispeten asal tek sayılar (ilk tek asal sayılar yeterlidir), Chinese Remainder teoremi, $\theta_1,\theta_2,\ldots,\theta_n$ öyle ki
$$ \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$ yaratılacak QDE problemi için çözümler $\theta_i$ başında bahsettiğimiz.
Bu uyumların ilk grubu, ALT Küme Toplamının eşdeğer olduğunu ima eder. $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$
Şimdi, çözünürlüğün bu uyumun çözünürlüğüne eşdeğer olduğu ikinci dereceden denklemi oluşturuyorlar.
Tanımlarlar $H=\sum_{k=1}^n\theta_k$ ve $K=\prod_{k=1}^{n}q_k^m$. Herhangi birini gözlemleyin$x$ şeklinde $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ tatmin eder $$H^2-x^2\equiv0\pmod{K}$$
Sonra, bir çift alıştırma yoluyla, neden seçme seçenekleri olduğunu tartışırlar. $q_i$ ve bir $\lambda_1$ yeterince büyük $2H<K$, ve $|t|<H$ve bunu sağlamak $(*)$bir çözümü vardır ancak ve ancak Kuadratik Diofant denkleminin
$$\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$$
bir çözümü var $x,y\geq0$.
Bu denklemin nasıl yeniden yazıldığına dikkat edin
$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$
Teknik detaylarda yapılan seçimler, çözüm olduğunda $x,y\geq0$ bu denklem için her zaman $H^2-x^2$ halihazırda birden çok olduğu biliniyor $K$ ve $S^2-x^2=(S+x)(S-x)$ birden fazla $2^{m+1}$.